EVENTUAL DETERMINISM: USING PROBABILISTIC MEANS TO ACHIEVE DETERMINISTIC ENDS
Josyula R. Rao · International Journal of Parallel Emergent and Distributed Systems · 1996
We introduce a new paradigm For Ihc design of parallel algorithms called eventual determinism. In an eventualfy-determinizing algorithm, all processes execute identical programs from identical starting states. A program has two parts (also called modes) —probabilistic and deterministic. A process begins execution in the probabilistic mode and eventually (with probability one) switches to a deterministic mode. The decision to switch is taken independently by each process. This means that it is possible for different processes to be executing in different modes at the same time. It is possible that a process may change back to the probabilistic mode but it is required that eventually, each process should switch and stay in the deterministic mode. Thus determinacy pervades the system. Evcntually-determinizing algorithms arc designed to combine the advantages of probabilistic and deterministic algorithms. Typically, the probabilistic mode is used for a task that either can be done more efficiently probabilistically or cannot be accomplished deterministically (c.g. breaking symmetry). Once this has been accomplished, a process can switch modes to take advantage of determinacy (e.g. the worst case complexities bounded). We emphasize two features of our method. First, the switchover point is not a bottleneck for the system. Second, the specification of the component modes can be used to construct a compositional proof of the specification of the eventually-dcterminizing algorithm. We illustrate the design of cvcntually-dclcrminizing algorithms with two examples. First, we address the problem of conflict-resolution for distributed systems. We construct an algorithm for a ring of dining philosophers by combining a modified version of the probabilistic Lehmann-Rabin's Free Philosopher algorithm (which only ensures deadlock-freedom) with the deterministic Chandy-Misra algorithm. The resulting system is proved to be starvation-free. Our second example is drawn from the field of self-stabilization. We construct a simple probabilistic algorithm for a ring of odd number of processes. Using this algorithm as a basis, we develop an eventually-determinizing algorithm for self-stabilization. Compared to deterministic algorithms which require a minimum number of three shared states per process, the eventually determining algorithm uses only two states per process.