Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Awerbuch, A.V. Goldberg, M. Luby, and S. Plotkin, Network decomposition and locality in distributed computing, in Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS 1989), pages 364-369, IEEE, Research Triangle Park, North Carolina.
	2	Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Fast network decomposition, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.169-177, August 10-12, 1992, Vancouver, British Columbia, Canada  [doi>10.1145/135419.135456]
	3	N. Alon, J. Spencer, and P. ErdSs, The Probabilistic Method, Wiley-Interscience Series, John Wiley & Sons, Inc., New York, 1992.
	4	B. BollobAs, Graph Theory, Springer Verlag, New York, 1979.
	5	B. BoUob~s, Chromatic number, girth, and maximal degree, Discrete Math.. 24 (1978), 311-314.
	6	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986  [doi>10.1016/S0019-9958(86)80023-7]
	7	Andrew V. Goldberg , Serge A. Plotkin , Gregory E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM Journal on Discrete Mathematics, v.1 n.4, p.434-446, Nov. 1988  [doi>10.1137/0401044]
	8	David A. Grable , Alessandro Panconesi, Nearly optimal distributed edge coloring in O(log log n) rounds, Random Structures & Algorithms, v.10 n.3, p.385-405, May 1997  [doi>10.1002/(SICI)1098-2418(199705)10:3<385::AID-RSA6>3.0.CO;2-S ]
	9	Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, On the distributed complexity of computing maximal matchings, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.219-225, January 25-27, 1998, San Francisco, California, United States
	10	Amos Israeli , Y. Shiloach, An improved parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.57-60, 1986  [doi>10.1016/0020-0190(86)90141-9 ]
	11	Howard J. Karloff , David B. Shmoys, Efficient parallel algorithms for edge coloring problems, Journal of Algorithms, v.8 n.1, p.39-52, March 1987  [doi>10.1016/0196-6774(87)90026-5]
	12	Richard M. Karp, Probabilistic recurrence relations, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.190-197, May 05-08, 1991, New Orleans, Louisiana, United States  [doi>10.1145/103418.103443]
	13	Shay Kutten , David Peleg, Fast distributed construction of k-dominating sets and applications, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.238-251, August 20-23, 1995, Ottowa, Ontario, Canada  [doi>10.1145/224964.224990]
	14	Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	15	Lecture Notes in Distributed Algorithms, Solution Sheet # 4,Available at http: // www.nada, kth.se/kurser/kth/2D5340.
	16	Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992  [doi>10.1137/0221015]
	17	N. Linial and M. Saks, Low diameter graph decomposition, Combinatorica (1993), Vol. 13 (4)
	18	M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States  [doi>10.1145/22145.22146]
	19	Michael Luby, Removing randomness in parallel computation without a processor penalty, Journal of Computer and System Sciences, v.47 n.2, p.250-286, Oct. 1993  [doi>10.1016/0022-0000(93)90033-S]
	20	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	21	Moni Naor, A lower bound on probabilistic algorithms for distributive ring coloring, SIAM J. Disc. Math., Vol. 4, No. 3, pp. 409-412, August 1991
	22	Moni Naor , Larry Stockmeyer, What Can Be Computed Locally?, SIAM Journal on Computing, v.24 n.6, p.1259-1277, Dec. 1995  [doi>10.1137/S0097539793254571]
	23	O. Johausson, personal communication.
	24	A. Panconesi, Lecture Notes in (Theoretical) Distributed Computing, KTn NADA Tech Reprt TRITA-NA-9$01
	25	A. Panc~nesi and A. Srinivasan, The Local Nature of A-coloring and Its Algorithmic Applications, Combinatorica 15 (2) 1995, 255-280.
	26	Alessandro Panconesi , Aravind Srinivasan, On the complexity of distributed network decomposition, Journal of Algorithms, v.20 n.2, p.356-374, March 1996  [doi>10.1006/jagm.1996.0017 ]

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski