On contention resolution protocols and associated probabilistic phenomena

ABSTRACT

Consider an on-line scheduling problem in which a set of abstract processes are competing for the use of a number of resources. Further assume that it is either prohibitively expensive or impossible for any two of the processes to directly communicate with one another. If several processes simultaneously attempt to allocate a particular resource (as may be expected to occur, since the processes cannot easily coordinate their allocations), then none succeed. In such a framework, it is a challenge to design efficient contention resolution protocols.Two recently-proposed approaches to the problem of PRAM emulation give rise to scheduling problems of the above kind. In one approach, the resources (in this case, the shared memory cells) are duplicated and distributed randomly. We analyze a simple and efficient deterministic algorithm for accessing some subset of the duplicated resources. In the other approach, we analyze how quickly we can access the given (nonduplicated) resource using a simple randomized strategy. We obtain precise bounds on the performance of both strategies. We anticipate that our results with find other applications.

REFERENCES

• 1: ABRAMSON, N. 1973. The ALOHA system. In Computer-Communication Networks. N. Abramson and F. Kuo, eds. Prentice-Hall, Englewood Cliffs, N.J.
• 2: ALON, N. 1990. Transversal numbers of uniform hypergraphs. Graphs Combin. 6, 1-4.
• 3: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 4: ALON, N., AND SPENCER, J.H. 1991. The Probabilistic Method. Wiley, New York.
• 5: ANDERSON, R. J., AND MILLER, G.L. 1988. Optical communication for pointer based algorithms. Tech. Rep. CRI-88-14, Computer Science Dept., Univ. Southern California.
• 6: CARTER, J. L., AND WEGMAN, M.N. 1979. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 143-154.
• 7: CHERNOFF, H. 1952. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493-509.
• 8: CHVATAL, V. 1979. The tail of the hypergeometric distribution. Disc. Math. 25, 285-287.
• 9: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
• 10: Mihály Geréb-Graus , Thanasis Tsantilas, Efficient optical communication in parallel computers, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.41-48, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140906]
• 11: GOLDBERG, L. A., AND JERRUM, M. 1992. A sub-logarithmic communication algorithm for the completely connected optical communication parallel computer. Tech. Rep. ECS-LFCS-92-234 (September), Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh, Edinburgh, Scotland.
• 12: Leslie Ann Goldberg , Mark Jerrum , Tom Leighton , Satish Rao, A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.300-309, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.166108]
• 13: Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181406]
• 14: Albert G. Greenberg , Philippe Flajolet , Richard E. Ladner, Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, Journal of the ACM (JACM), v.34 n.2, p.289-325, April 1987 [doi>10.1145/23005.23006]
• 15: Albert G. Greenberg , Schmuel Winograd, A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels, Journal of the ACM (JACM), v.32 n.3, p.589-596, July 1985 [doi>10.1145/3828.214125]
• 16: GREENBERG, R. I., AND LEISERSON, C.E. 1985. Randomized routing on fat-trees. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (Oct.), IEEE, New York, pp. 241-249.
• 17: HOEFFDING, W. 1963. Probability inequalities for sums of bounded random variables. JASA 58, 13-30.
• 18: Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
• 19: János Komlós , Albert G. Greenberg, Correction to "An asymptotically nonadaptive algorithm for conflict resolution i, IEEE Transactions on Information Theory, v.31 n.6, p.841-841, Nov. 1985
• 20: C. U. Martel , T. P. Vayda, The complexity of selection resolution, conflict resolution and maximum finding on multiple access channels, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• 21: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 22: MEYER AUF DER HEIDE, F., SCHEIDELER, C., AND STEMANN, V. 1995. Exploiting storage redundancy to speed up randomized shared memory simulations. In Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 900 (March), Springer-Verlag, New York, pp. 267-278.
• 23: SIEGEL, A. 1989. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Nov.). IEEE, New York, pp. 20-25. (Revised version).
• 24: Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987 [doi>10.1145/7531.7926]
• 25: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 26: YAO, A. C. 1983. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (Oct.). IEEE, New York, pp. 420-428.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory

Keywords:
emulation protocols, hash functions, parallel computation