Symmetry in Distributed Systems
Johnson, Ralph E.
A distributed computing system can be considered to be symmetric because of its topology or because of its behavior. Unfortunately, these different definitions can categorize the same system differently. The choice of definition becomes important when one is trying to prove that certain problems, such as the Dining Philosophers problem, cannot be solved on symmetric distributed computing systems. Since the behavioral definitions are based on the possible patterns of computation, it is much easier to use them for these proofs. However, behavioral definitions admit straightforward decision procedures. This thesis presents a new definition for symmetry, called similarity, that, while based on behavior of processes, is decidable given the initial configuration of the system. The decision procedure for similarity depends partly on the model of computation being used, but a way to discover these decision procedures is given and is used to find decision procedures for a wide range of models of distributed computation. Distributed versions of these decision procedures form the basis of solutions to the problem of selecting a process as the leader. The thesis also shows how to use similarity to compare the relative power of different models of computation, including models with shared variables with and without locking, models using synchronous and asynchronous message-passing, models making different assumptions about fairness, and models based on probabilistic techniques.
computer science; technical report
Previously Published As