A steady state analysis of diffracting trees (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A steady state analysis of diffracting trees (extended abstract)

Full text

Pdf (950 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures table of contents

Padua, Italy

Pages: 33 - 41

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Nir Shavit	Tel-Aviv University and MIT
Eli Upfal	The Weizmann Institute, Israel, and IBM Almaden Research Center, California
Asaph Zemach	Tel-Aviv University

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 7

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/237502.237505 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.

	1	A. Agarwal , M. Cherian, Adaptive backoff synchronization techniques, Proceedings of the 16th annual international symposium on Computer architecture, p.396-406, April 1989, Jerusalem, Israel
	2	A. Agarwal , D. Chaiken , K. Johnson , D. Kranz , J. Kubiatowicz , K. Kurihara , B. H. Lim , G. Maa , D. Nussbaum , M. Parkin , D. Yeung, THE MIT ALEWIFE MACHINE: A LARGE-SCALE DISTRIBUTED-MEMORY MULTIPROCESSOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
	3	B. Aiello, R. Venkatesan and M. Yung. Optimal Depth Counting Networks. personal communication.
	4	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994 [doi>10.1145/185675.185815]
	5	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks and multi-processor coordination, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.348-358, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103421]
	6	E.A. Brewer, C.N. Dellarocas. PROTEUS User Documentatzon. MIT, 545 Technology Square, Cambridge, MA 02139, 0.5 edition, December 1992.
	7	E. A. Brewer , C. N. Dellarocas , A. Colbrook , W. E. Weihl, PROTEUS: A HIGH-PERFORMANCE PARALLEL-ARCHITECTURE SIMULATOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
	8	David F. Carta, Two fast implementations of the “minimal standard” random number generator, Communications of the ACM, v.33 n.1, p.87-88, Jan. 1990 [doi>10.1145/76372.76379]
	9	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.174-183, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167145]
	10	James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
	11	V.F. Kolchin, B.A. Senast'yanov, and V.P. Chistyakov. Random Allocation. V.H. Winston & Sons, Washington D.C. 1978.
	12	Nir Shavit , Asaph Zemach, Diffracting trees (preliminary version), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.167-176, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181326]
	13	Nir Shavit , Dan Touitou, Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215419]
	14	J. M. Mellor-Crummey , M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiproceessors, University of Rochester, Rochester, NY, 1990
	15	S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
	16	Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
	17	S. Kahan - TERA Computer Company. Personal communication, May 1995.
	18	D. Touitou - Tel-Aviv University. Personal communication, October 1994.

CITED BY 7

	Leonidas Hadjimitsis , Marios Mavronicolas, Contention in balancing networks resolved (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.41-50, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Nir Shavit , Asaph Zemach, Scalable concurrent priority queue algorithms, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.113-122, May 04-06, 1999, Atlanta, Georgia, United States
	Giovanni Della-Libera , Nir Shavit, Reactive diffracting trees, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.24-32, June 23-25, 1997, Newport, Rhode Island, United States
	Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
	Phillip B. Gibbons , John L. Bruno , Steven Phillips, Post-mortem black-box correctness tests for basic parallel data structures, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.44-53, June 27-30, 1999, Saint Malo, France
	Roger Wattenhofer , Peter Widmayer, An inherent bottleneck in distributed counting, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.159-167, August 21-24, 1997, Santa Barbara, California, United States
	Guy E. Blelloch , Phillip B. Gibbons , Girija J. Narlikar , Yossi Matias, Space-efficient scheduling of parallelism with synchronization variables, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.12-23, June 23-25, 1997, Newport, Rhode Island, United States