Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Cynthia Dwork, Maurice Herlihy, and Orli Waarts. Contention in shared memory algorithms. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 174-183, San Diego, California, 16-18 May 1993.

Categories and Subject Descriptors: F.2.m [Analysis of Algorithms and Problem Complexity]: Miscellaneous

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Contention, counting networks, mutual exclusion

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.

• Eran Aharonson and Hagit Attiya. Counting networks with arbitrary fan-out. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 104-113, Orlando, Florida, 27-29 January 1992.

• William Aiello, Ramarathnam Venkatesan, and Moti Yung. Coins, weights and contention in balancing networks. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pages 193-205, Los Angeles, California, 14-17 August 1994.

• Miklos Ajtai, James Aspnes, Cynthia Dwork, and Orli Waarts. A theory of competitive analysis for distributed algorithms. In 35th Annual Symposium on Foundations of Computer Science, pages 401-411, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• James Aspnes. Time- and space-efficient randomized consensus. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, pages 325-331, Quebec City, Quebec, Canada, 22-24 August 1990.

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

• James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks and multi-processor coordination. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 348-358, New Orleans, Louisiana, 6-8 May 1991.

• James Aspnes and Orli Waarts. Randomized consensus in expected O(n log^2 n) operations per processor. In 33rd Annual Symposium on Foundations of Computer Science, pages 137-146, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• James Aspnes and Orli Waarts. Modular competitiveness for distributed algorithms. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 237-246, Philadelphia, Pennsylvania, 22-24 May 1996.

• Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In Proceedings of the Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 27-30, Montreal, Quebec, Canada, 17-19 August 1983.

• Costas Busch, Nikos Hardavellas, and Marios Mavronicolas. Contention in counting networks. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, page 404, Los Angeles, California, 14-17 August 1994.

• 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.

• Manhoi Choy and Ambuj K. Singh. Adaptive solutions to the mutual exclusion problem. Distributed Computing, 8(1):1-17, 1994.

• Stephen Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM Journal on Computing, 15(1):87-97, February 1986.

• David E. Culler, Rachard M. Karp, David Patterson, Abhijit Sahay, Eunice E. Santos, Klaus Erik Schauser, Ramesh Subramonian, and Thorsten von Eicken. LogP: A practical model of parallel computation. Communications of the ACM, 39(11):78-85, November 1996.

• 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.

• Martin Dowd, Yehoshua Perl, Larry Rudolph, and Michael Saks. The periodic balanced sorting network. Journal of the ACM, 36(4):738-757, October 1989.

• Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, April 1988.

• 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.

• Phillip B. Gibbons, Yossi Matias, and Vijaya Ramachandran. Efficient low-contention parallel algorithms. Journal of Computer and System Sciences, 53(3):417-442, December 1996.

• Allan Gottlieb, Boris D. Lubachevsky, and Larry Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. ACM Transactions on Programming Languages and Systems, 5(2):164-189, April 1983.

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

• M. Herlihy, B.-H. Lim, and N. Shavit. Low contention load balancing on large-scale multiprocessors. In Proceedings of the 4th Annual Symposium on Parallel Algorithms and Architectures, pages 219-228, San Diego, California, USA, June 1992. ACM Press.

• Maurice Herlihy, Nir Shavit, and Orli Waarts. Low contention linearizable counting. In 32nd Annual Symposium on Foundations of Computer Science, pages 526-535, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Michael Klugerman and C. Greg Plaxton. Small-depth counting networks. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 417-428, Victoria, British Columbia, Canada, 4-6 May 1992.

• Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395-404, July 1976.

• Michael O. Rabin. Randomized Byzantine generals. In 24th Annual Symposium on Foundations of Computer Science, pages 403-409, Tucson, Arizona, 7-9 November 1983. IEEE.

• Ambuj K. Singh, James H. Anderson, and Mohamed G. Gouda. The elusive atomic register revisited. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 206-221, Vancouver, British Columbia, Canada, 10-12 August 1987.

• Jae-Heon Yang and James H. Anderson. Fast, scalable synchronization with minimal hardware support (extended abstract). In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, pages 171-182, Ithaca, New York, USA, 15-18 August 1993.

Shortcuts: