Link: ACM Portal
Summary
The problem of resolving conflicts between processes in distributed systems is of practical importance. A conflict can be resolved only if there is some property by which one process in the set of conflicting processes can be distinguished and selected for favorable treatment. In order to guarantee fairness, the distinguishing property must be such that the process selected for favorable treatment is not always the same.Two paradigms are presented to make the problem concrete: the well-known distributed dining philosophers problem and a generalization of it, the distributed drinking philosophers problem, which captures the essence of conflict resolution problems in distributed systems.
In order to come up with deterministic conflict resolution strategy, we must ensure that these two properties hold; (1) distinguishability and (2) fairness. A distributed system is represented by an undirected graph G with a one-to-one correspondence between vertices of G and the processes in the system. An edge between two vertices means that a conflict between those two vertices can happen. Precedences between pairs of potentially conflicting processes are represented by a directed precedence graph H. H is identical to G except that each edge in H has a direction such that the edge is directed away from the process with greater precedence toward the one with lower precedence.
Starting with an acyclic H, our requirements are that (1) H remains acyclic at all times, (2) H changes in such a way that every conflicting process eventually rises to top in H, and (3) each change to H is done locally at a process. In order to achieve these requirements, we use the following rules:
- Acyclicity: All edges incident on a process may be atomically redirected toward p. (This transformation preserves acyclicity).
- Fairness: Within finite time after a conflict is resolved in favor of a process, that process must yield precedence to all its neighbors.
Two philosophers are neighbors if and only if there is an edge between them in G. Neighbors may send messages to one another. Messages are delivered in arbitrary but finite time. Resources, such as bottles, are also encoded and transmitted as messages. The problem is to devise a nonprobabilistic solution that (1) fairly treats all philosophers, (2) is symmetric between all philosophers, (3) is economical in terms of messages sent/received between state transitions for a philosopher, (4) allows concurrent drinking by different philosophers from different bottles, and (5) keeps the number of messages in transit at any time and the size of messages bounded.
The Dining Philosophers Problem: It is a special case of the drinkers problem in which every thirsty philosopher needs bottles associated with all its incident edges for all drinking sessions. A solution with all the properties mentioned above is presented. However, in order to distinguish between the two problems, the following terms have been used for the diners problem, with the corresponding term for the drinkers problem in parenthesis: thinking (tranquil), hungry (thirsty), eating (drinking), fork (bottle).
