Narrow Results

A system of asynchronous parallel processes is represented by an exclusion graph in which a vertex is a process and an edge is a pair of mutually excluding processes. The mutual exclusion problem can be managed by simple entrance and exit protocols using PV_chunk operations on a single shared variable when the graph is a threshold one. Ordman wonders if an efficient way exists for managing mutual exclusion situations modeled by more complex graphs than the threshold ones. A start is made on that here: we present a solution of the problem when the model is in the class of matrogenic graphs, which properly contains the threshold graphs.

In this paper, we consider arbitrary tree networks where every processor, except one, called the root, executes the same program. We show that, to design a depth-first token circulation protocol in such networks, it is necessary to have at least configurations, where n is the number of processors in the network and Δ_i is the degree of processor p_i.

We then propose a depth-first token circulation algorithm which matches the above minimal number of configurations. We show that the proposed algorithm is self-stabilizing, i.e., the system eventually recovers itself to a legitimate state after any perturbation modifying the state of the processors. Hence, the proposed algorithm is optimal in terms of the number of configurations and no extra cost is involved in making it stabilizing.

For bidirectional rings, there have been proposed self-stabilizing mutual exclusion protocols, which are either time-adaptive (i.e., efficient in recovery) or 1-latent (i.e., efficient in legal execution) but not both. This paper proposes a randomized self-stabilizing mutual exclusion protocol that inherits both of the advantages from them: It is 1-latent in the sense that the privilege is circulated in a linear round (i.e., very intuitively, the privilege is transferred from a process to another by a "step"), provided that the system always stays in legitimate configurations, and is weakly time-adaptive in the sense that the system stabilizes from any configuration c in O(f) steps with a high probability, where f is the number of corrupted processes in c. It also guarantees with a high probability that there is at most one privilege even while converging to a legitimate configuration.

The asynchronous group mutual exclusion (GME) problem [5] is a generalization of the (ordinary) mutual exclusion problem. Each process requests a forum. When a process is in the critical section (CS), we say its forum is held. The GME problem (i) allows at most one forum to be held at any time and, (ii) when a forum is held, encourages any number of processes requesting that forum to participate in that forum, that is, to be in the CS simultaneously. An extension of this problem, called the group mutual l-exclusion with multiple forum requests (GMLE-M) problem [8], allows each process to request multiple forums and up to l forums to be held simultaneously. In this paper, we give a simple GMLE-M algorithm that facilitates a highly concurrent participation of processes in forums. The algorithm uses a new technique, called automatic joining, that enables processes to enter the CS directly when their forums are being held. This technique can be used in other extensions of the GME problem also, to increase concurrency.

We present a very simple new distributed algorithm for the classical Dining Philosophers problem.

Our algorithm is the first algorithm with the following important properties:

(1) It is fully distributed; i.e., there is no central memory or central process to which every other process may have access.

(2) It is symmetric; i.e., all processes behave identically, and do not use any process identifiers.

(3) It has a response time ≤ 3ℓ, independent of the size of the ring, where ℓ is an upper bound on the time a resource may be used by a process. Moreover, we establish the optimality of our algorithm with respect to this last measure by proving that no distributed algorithm can guarantee a response time less than 3ℓ.

Michael Fischer has proposed a mutual exclusion algorithm that ingeniously exploits real time. We prove this algorithm using the time-honored technique of establishing an appropriate invariant.

In this paper, we consider arbitrary tree networks where every processor, except one, called the root, executes the same program. We show that, to design a depth-first token circulation protocol in such networks, it is necessary to have at least configurations, where n is the number of processors in the network and Δ_i is the degree of processor p_i.

We then propose a depth-first token circulation algorithm which matches the above minimal number of configurations. We show that the proposed algorithm is self-stabilizing, i.e., the system eventually recovers itself to a legitimate state after any perturbation modifying the state of the processors. Hence, the proposed algorithm is optimal in terms of the number of configurations and no extra cost is involved in making it stabilizing.

We propose two modifications of the n-process mutual exclusion algorithm by Peterson for the asynchronous multi-writer/reader shared memory model. By any of the modifications we can speed up the original n-process algorithm. The running times for the trying regions of the first modified algorithm and the second modified algorithm are (2n - 3)c + O(n³ l) and (n - 1)c + O(n³ l), respectively, where n is the number of processes, l is an upper bound on the time between two steps, and c is an upper bound on the time that any user spends in the critical region. These running times are improvements on the running time, O(n²c + n⁴ l) of the original n-process algorithm for the same asynchronous shared memory model.