How to distribute a dictionary in a complete network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How to distribute a dictionary in a complete network

Full text

Pdf (1.01 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 117 - 127

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

M. Dietzfelbinger	Fachbereich 17 Mathematik, Informatik, Universität-GH Paderborn, D-4790 Paderborn, Fed. Rep. of Germany
F. Meyer auf der Heide	Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel 32000 and Computer Science Program, University of Texas at Dallas, Richardson, TX

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/100216.100229 What is a DOI?

REFERENCES

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.

	DKM88	Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E., Dynamic perfect hashing: Upper and lower bounds, Proc. of the 29th IEEE FOCS, 1988, pp. 524-531; also: Tech. Report No. 282, Fachbereich Informatik, Universit/it Dortmund, 1988.
	DM89	M. Dietzfelbinger , F. Meyer auf der Heide, An optimal parallel dictionary, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.360-368, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72974]
	DM90	M. Dietzfelbinger , Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.6-19, July 1990, Warwick University, England
	FKS84	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	Han89	Yijie Han, Parallel algorithms for computing linked list prefix, Journal of Parallel and Distributed Computing, v.6 n.3, p.537-557, June 1989 [doi>10.1016/0743-7315(89)90005-1]
	Hof87	Micha Hofri, Probabilistic analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1987
	KU86	A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
	KRS88	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A Complexity Theory of Efficient Parallel Algorithms (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.333-346, July 11-15, 1988
	MV84	Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
	Ran87	Ranade, A. G., How to emulate shared memory, Proc. of the 28th IEEE FOCS, 1987, pp. 185- 194.
	Sie89	Siegel, A., On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications, Proc. of the 30th IEEE FOCS, 1989, pp. 20-25.
	Upf84	Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]

CITED BY 9

	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Petra Berenbrink , Friedhelm Meyer auf der Heide , Klaus Schröder, Allocating weighted jobs in parallel, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.302-310, June 23-25, 1997, Newport, Rhode Island, United States
	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
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	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
	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
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
	Karni Gilon , David Peleg, Compact deterministic distributed dictionaries (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.81-94, August 19-21, 1991, Montreal, Quebec, Canada
	J. Gil , F. Meyer auf der Heide , A. Wigderson, Not all keys can be hashed in constant time, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.244-253, May 13-17, 1990, Baltimore, Maryland, United States