Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: James Aspnes. Lower bounds for distributed coin-flipping and randomized consensus. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 559-568, El Paso, Texas, 4-6 May 1997.

Categories and Subject Descriptors: B.3.2 [Memory Structures]: Design Styles -- shared memory; B.4.3 [Input/Output and Data Communications]: Interconnections (subsystems) -- asynchronous/synchronous operation; C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); D.1.3 [Programming Techniques]: Concurrent Programming -- distributed programming; D.4.1 [Operating Systems]: Process Management; D.4.7 [Operating Systems]: Organization and Design -- distributed systems; F.2.m [Analysis of Algorithms and Problem Complexity]: Miscellaneous -- miscellaneous

General Terms: Reliability, Theory

Additional Key Words and Phrases: Consensus, impossibility, randomization

Selected references

• Karl R. Abrahamson. On achieving consensus using a shared memory. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pages 291-302, Toronto, Ontario, Canada, 15-17 August 1988.

• Noga Alon and Moni Naor. Coin-flipping games immune against linear-sized coalitions (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 46-54, St. Louis, Missouri, 22-24 October 1990. IEEE.

• Rajeev Alur, Hagit Attiya, and Gadi Taubenfeld. Time-adaptive algorithms for synchronization. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 800-809, Montréal, Québec, Canada, 23-25 May 1994.

• James Aspnes. Time- and space-efficient randomized consensus. Journal of Algorithms, 14(3):414-431, May 1993.

• James Aspnes. Lower bounds for distributed coin-flipping and randomized consensus. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 559-568, El Paso, Texas, 4-6 May 1997.

• James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441-461, September 1990.

• James Aspnes and Orli Waarts. Randomized consensus in expected O(N log^2 N) operations per processor. SIAM Journal on Computing, 25(5):1024-1044, October 1996.

• Hagit Attiya, Danny Dolev, and Nir Shavit. Bounded polynomial randomized consensus. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, pages 281-293, Edmonton, Alberta, Canada, 14-16 August 1989.

• Yonatan Aumann. Efficient asynchronous consensus with the weak adversary scheduler. In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pages 209-218, Santa Barbara, California, 21-24 August 1997.

• Yonatan Aumann and Michael A. Bender. Efficient asynchronous consensus with the value-oblivious adversary scheduler. In Friedhelm Meyer auf der Heide and Burkhard Monien, editors, Automata, Languages and Programming, 23rd International Colloquium, volume 1099 of Lecture Notes in Computer Science, pages 622-633, Paderborn, Germany, 8-12 July 1996. Springer-Verlag.

• Tushar Deepak Chandra. Polylog randomized wait-free consensus. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 166-175, Philadelphia, Pennsylvania, USA, 23-26 May 1996.

• Benny Chor, Amos Israeli, and Ming Li. On processor coordination using asynchronous hardware. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 86-97, Vancouver, British Columbia, Canada, 10-12 August 1987.

• Jason Cooper and Nathan Linial. Fast perfect-information leader-election protocol with linear immunity. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 662-671, San Diego, California, 16-18 May 1993.

• Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77-97, January 1987.

• Faith Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, pages 241-249, Ithaca, New York, USA, 15-18 August 1993.

• Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985.

• Joel Friedman. On the bit extraction problem. In 33rd Annual Symposium on Foundations of Computer Science, pages 314-319, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, January 1991.

• Michael Saks, Nir Shavit, and Heather Woll. Optimal time randomized consensus -- making resilient algorithms fast in practice. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 351-362, San Francisco, California, 28-30 January 1991.

• Umesh V. Vazirani. Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources (extended abstract). In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 366-378, Providence, Rhode Island, 6-8 May 1985.

Shortcuts: