Preliminary versionA preliminary version of these results was presented in: P. D. MacKenzie, C. G. Plaxton, and R. Rajaraman. On contention resolution protocols and associated probabilistic phenomena. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 153-162, Montréal, Québec, Canada, 23-25 May 1994.
Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism and concurrency; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Parallel computation, hash functions, emulation protocols
Selected references
- Noga Alon, Amotz Bar-Noy, Nathan Linial, and David Peleg. A lower bound for radio broadcast. Journal of Computer and System Sciences, 43(2):290-298, October 1991.
- J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, April 1979.
- Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. Simple, efficient shared memory simulations. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 110-119, Velen, Germany, June 1993. ACM Press.
- M. Gereb-Graus and T. Tsantilas. Efficient optical communication in parallel computers. In Proceedings of the 4th Annual Symposium on Parallel Algorithms and Architectures, pages 41-49, San Diego, California, USA, June 1992. ACM Press.
- Leslie Ann Goldberg, Mark Jerrum, and Tom Leighton. A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 300-309, Velen, Germany, June 1993. ACM Press.
- L. A. Goldberg, Y. Matias, and S. Rao. An optical shared memory simulation. In Proceedings of the 6th Annual Symposium on Parallel Algorithms and Architectures, pages 257-267, Cape May, New Jersey, USA, June 1994. ACM Press.
- Albert G. Greenberg, Philippe Flajolet, and Richard E. Ladner. Estimating the multiplicities of conflicts to speed their resolution in multiple access channels. Journal of the ACM, 34(2):289-325, April 1987.
- Ronald I. Greenberg and Charles E. Leiserson. Randomized routing on fat-trees (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, pages 241-249, Portland, Oregon, 21-23 October 1985. IEEE.
- Albert G. Greenberg and Shmuel Winograd. A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. Journal of the ACM, 32(3):589-596, July 1985.
- Friedhelm Meyer auf der Heide, Christian Scheideler, and Volker Stemann. Exploiting storage redundancy to speed up randomized shared memory simulations. In 12th Annual Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 267-278, Munich, Germany, 2-4 March 1995. Springer.
- Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 318-326, 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.
- Alan Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 20-25, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Eli Upfal and Avi Wigderson. How to share memory in a distributed system. Journal of the ACM, 34(1):116-127, January 1987.
- Andrew C. Yao. Lower bounds by probabilistic arguments (extended abstract). In 24th Annual Symposium on Foundations of Computer Science, pages 420-428, Tucson, Arizona, 7-9 November 1983. IEEE.