Eventual determinism: Using probabilistic means to achieve deterministic ends

Abstract

Introduces a new paradigm for the design of parallel algorithms called eventual determinism. Eventually-determinizing algorithms are designed to combine the advantages of probabilistic and deterministic algorithms. Typically, a probabilistic algorithm is used for a task that either can be done more efficiently probabilistically or cannot be accomplished deterministically (e.g. breaking symmetry). Once this has been accomplished, a process can start executing a deterministic algorithm for the same problem to take advantage of determinacy (e.g. the worst case complexities bounded). We illustrate the design of eventually-determinizing algorithms with examples from conflict resolution and self-stabilization.