Fast deterministic consensus in a noisy environment

ABSTRACT

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 [16] 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.

REFERENCES

• 1: Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
• 2: Yehuda Afek , Dalia Dauber , Dan Touitou, Wait-free made fast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.538-547, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225271]
• 3: Rajeev Alur , Hagit Attiya , Gadi Taubenfeld, Time-Adaptive Algorithms for Synchronization, SIAM Journal on Computing, v.26 n.2, p.539-556, April 1997 [doi>10.1137/S0097539794265244]
• 4: James H. Anderson , Rohit Jain , David Ott, Wait-Free Synchronization in Quantum-Based Multiprogrammed Systems, Proceedings of the 12th International Symposium on Distributed Computing, p.34-48, September 24-26, 1998
• 5: James H. Anderson , Mark Moir, Wait-free synchronization in multiprogrammed systems: integrating priority-based and quantum-based scheduling, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.123-132, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301341]
• 6: James Aspnes, Time- and space-efficient randomized consensus, Journal of Algorithms, v.14 n.3, p.414-431, May 1993 [doi>10.1006/jagm.1993.1022]
• 7: James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998 [doi>10.1145/278298.278304]
• 8: James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
• 9: James Aspnes , Orli Waarts, Randomized Consensus in Expected O(n log^ 2 n) Operations Per Processor, SIAM Journal on Computing, v.25 n.5, p.1024-1044, Oct. 1996 [doi>10.1137/S0097539792240881]
• 10: H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73001]
• 11: Hagit Attiya , Arie Fouren, Adaptive wait-free algorithms for lattice agreement and renaming (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.277-286, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277749]
• 12: Yonatan Aumann, Efficient asynchronous consensus with the weak adversary scheduler, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.209-218, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259441]
• 13: Yonatan Aumann , Michael A. Bender, Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.622-633, July 08-12, 1996
• 14: Patrick Billingsley. Probability and Measure. John Wiley and Sons, second edition, 1986.
• 15: Gabriel Bracha , Ophir Rachman, Randomized Consensus in Expected O(n²log n) Operations, Proceedings of the 5th International Workshop on Distributed Algorithms, p.143-150, October 07-09, 1991
• 16: Tushar Deepak Chandra, Polylog randomized wait-free consensus, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.166-175, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248083]
• 17: Benny Chor , Amos Israeli , Ming Li, Wait-Free Consensus Using Asynchronous Hardware, SIAM Journal on Computing, v.23 n.4, p.701-712, Aug. 1994 [doi>10.1137/S0097539790192635]
• 18: Andrew Chou , Jeremy Cooperstock , Ran El-Yaniv , Michael Klugerman , Tom Leighton, The statistical adversary allows optimal money-making trading strategies, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.467-476, January 22-24, 1995, San Francisco, California, United States
• 19: Richard Cole , Ofer Zajicek, The expected advantage of asynchrony, Journal of Computer and System Sciences, v.51 n.2, p.286-300, Oct. 1995 [doi>10.1006/jcss.1995.1067]
• 20: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 21: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 22: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 23: Eli Gafni , Michael Mitzenmacher, Analysis of timing-based mutual exclusion with random times, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.13-21, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301318]
• 24: Elias Koutsoupiaa and Christos H. Papadimitriou. Beyond competitive analysis. In 35th Annual Symposium on Foundations of Computer Science, pages 394-400, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
• 25: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 26: Michael C. Loui and Hosame H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. In Franco P. Preparata, editor, Advances in Computing Research, volume 4. JAI Press, 1987.
• 27: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 28: Srikanth Ramamurthy , Mark Moir , James H. Anderson, Real-time object sharing with minimal system support, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.233-242, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248098]
• 29: Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Design, Theory, Verification