2002/06/07 by James Aspnes, Aspnes, James
Chemistry · Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Radioactive element chemistry and processing #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0206012
Typographical errors fixed
openalex publication_date 2002/06/07 · arxiv created 2002/07/17 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy scheduling, in which an adversarial schedule is perturbed randomly, and show that in this model randomness in the environment can substitute for randomness in the algorithm. In particular, we show that a simplified, deterministic version of Chandra's wait-free shared-memory consensus algorithm (PODC, 1996, pp. 166-175) solves consensus in time at most logarithmic in the number of active processes. The proof of termination is based on showing that a race between independent delayed renewal processes produces a winner quickly. In addition, we show that the protocol finishes in constant time using quantum and priority-based scheduling on a uniprocessor, suggesting that it is robust against the choice of model over a wide range.