Polylog randomized wait-free consensus. (English) Zbl 1321.68066
Proceedings of the 15th annual ACM symposium on principles of distributed computing, PODC ’96, Philadelphia, PA, USA, May 23–26, 1996. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-800-2). 166-175 (1996).
For the entire collection see [Zbl 1323.68006].
MSC:
| 68M14 | Distributed systems |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68W15 | Distributed algorithms |
References:
| [1] | Yonatan Aumann and Micheal Bender. Efficient asynchronous consensus with a value-oblivious adversary scheduler. In Proceedings of the 23rd International Conference on Automata, Languages, and Programming, July 1996. |
| [2] | Karl Abrahamson. On achieving consensus using a shared memory. In Proceedings of ihe 7th Annual Symposium on Principles of Distributed Computing, pages 291- 302, August 1988. 10.1145/62546.62594 |
| [3] | Yonatan Aumann, Micheal Bender, and L. H. Zhang. Asynchronous consensus with an oblivious adversary scheduler. Unpublished manuscript, November 1994. |
| [4] | Yehuda Afek, Eli Gafni, John Tromp, and Paul M.B. Vitanyi. Wait-free test-andset. In Proceedings of the Sixth International Workshop on Disiributed Algorithms, pages 85-94, November 1992. |
| [5] | James Aspnes and M.P. Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11:441-461, 1990. 10.1016/0196-6774(90)90021-6 · Zbl 0705.68016 |
| [6] | James Aspnes. Time- and space-efficient randomized consensus. Journal of Algorithms, 14(3):414-431, 1993. An earlier version appeared in 9th ACM SIGACT- SIGOPS Symposium on Principles of Distributed Computing, August 1990, pp. 325-331. 10.1006/jagm.1993.1022 · Zbl 0825.68186 |
| [7] | James Aspnes and Orli Waarts. Randomized consensus in expected O(n log2 n) operations per processor. In Proceedings of the Thirty-Third Symposium on Foundations of Computer Science, pages 137- 146. IEEE Computer Society Press, October 1992. · Zbl 0919.68070 |
| [8] | Tushar D. Chandra and Cynthia Dwork. Personal communication. In this, we give a randomized implementation of test&set from multi reader multi writer register for a strong adversary with O(log n) expected running time., October 1992. |
| [9] | P.J. Courtois, F. Heymans, and D.L. Parnas. Concurrent control with readers and writers. Communications of the ACM, 14(10):667-668, 1971. 10.1145/362759.362813 |
| [10] | Benny Chor, Amos Israeli, and Ming Li. On processor coordination using asynchronous hardware. In Proceedings of the Sixth ACM Symposium on Principles of Distributed Computing, pages 222-231, August 1987. 10.1145/41840.41848 |
| [11] | M.P. Herlihy and J.M. Wing. Linearizability: A correctness condition for concurrent objects. ACM TOPLAS, 12(3):463- 492, 1990. 10.1145/78969.78972 |
| [12] | M.C. Loui and Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in computing research, 4:163-183, 1987. |
| [13] | Leslie Lamport. On interprocess communication, parts i and ii. Distributed Computing, 1:77-101, 1986. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
