Decentralized extrema-finding in circular configurations of processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Decentralized extrema-finding in circular configurations of processors

Full text

Pdf (215 KB)

Source

Communications of the ACM archive
Volume 23 , Issue 11 (November 1980) table of contents

Pages: 627 - 628

Year of Publication: 1980

ISSN:0001-0782

Authors

D. S. Hirschberg	Rice Univ., Houston, TX
J. B. Sinclair	Rice Univ., Houston, TX

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 52, Citation Count: 34

Additional Information:

abstract 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/359024.359029 What is a DOI?

ABSTRACT

This note presents an efficient algorithm, requiring O(n log n) message passes, for finding the largest (or smallest) of a set of n uniquely numbered processors arranged in a circle, in which no central controller exists and the number of processors is not known a priori.

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	Ernest Chang , Rosemary Roberts, An improved algorithm for decentralized extrema-finding in circular configurations of processes, Communications of the ACM, v.22 n.5, p.281-283, May 1979 [doi>10.1145/359104.359108]
	2	LeLann, G. Distributed systems--Towards a formal approach. Inform. Proc. 77, North-Holland Pub. Co., 1977, Amsterdam, pp. 155-160.
	3	Bums, J.E. A formal model for message passing systems. Tech. Rep. No. 91, Comptr. Sci. Dept., Indiana Univ., May 1980.

CITED BY 34

	Eli Gafni, Improvements in the time complexity of two message-optimal election algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.175-185, August 1985, Minaki, Ontario, Canada
	Randolph Franklin, On an improved algorithm for decentralized extrema finding in circular configurations of processors, Communications of the ACM, v.25 n.5, p.336-337, May 1982
	E. Korach , S. Moran , S. Zaks, Tight lower and upper bounds for some distributed algorithms for a complete network of processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.199-207, August 27-29, 1984, Vancouver, British Columbia, Canada
	Steven P. Levitan , Caxton C. Foster, Finding an extremum in a network, ACM SIGARCH Computer Architecture News, v.10 n.3, p.321-325, April 1982
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.265-274, May 01-04, 1999, Atlanta, Georgia, United States
	Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984
	Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987
	M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States
	Ernest Chang, Technical correspondence: on message passes in computer networks., Communications of the ACM, v.24 n.7, p.468, July 1981
	Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985
	Jan K. Pachl , E. Korach , D. Rotem, A technique for proving lower bounds for distributed maximum-finding algorithms (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.378-382, May 05-07, 1982, San Francisco, California, United States
	Hagit Attiya , Marc Snir , Manfred K. Warmuth, Computing on an anonymous ring, Journal of the ACM (JACM), v.35 n.4, p.845-875, Oct. 1988
	Jan K. Pachl , E. Korach , D. Rotem, Lower Bounds for Distributed Maximum-Finding Algorithms, Journal of the ACM (JACM), v.31 n.4, p.905-918, Oct. 1984
	Oded Goldreich , Liuba Shrira, The effects of link failures on computations in asynchronous rings, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.174-185, August 11-13, 1986, Calgary, Alberta, Canada
	E. Korach , S. Kutten , S. Moran, A modular technique for the design of efficient distributed leader finding algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.84-101, Jan. 1990
	E. Korach , S. Kutten , S. Moran, A modular technique for the design of efficient distributed leader finding algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.163-174, August 1985, Minaki, Ontario, Canada
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Exact communication costs for consensus and leader in a tree, Journal of Discrete Algorithms, v.1 n.2, p.167-183, April 2003
	Nicola Santoro, Sense of direction, topological awareness and communication complexity, ACM SIGACT News, v.16 n.2, p.50-56, Summer 1984
	G. C. Roman , J. Y. Plun , C. D. Wilcox , S. Varma, Dynamic Synchrony Among Atomic Actions, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.677-685, June 1993
	M. Y. Chan , F. Y. L. Chin, Optimal Resilient Distributed Algorithms for Ring Election, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.475-480, April 1993
	Gary L. Peterson, An O(nlog n) Unidirectional Algorithm for the Circular Extrema Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.758-762, Oct. 1982
	Mukesh Singhal, A Heuristically-Aided Algorithm for Mutual Exclusion in Distributed Systems, IEEE Transactions on Computers, v.38 n.5, p.651-662, May 1989
	Stefan Dobrev , Andrzej Pelc, Leader election in rings with nonunique labels, Fundamenta Informaticae, v.59 n.4, p.333-347, March 2004
	Paul M.B. Vitányi, Distributed elections in an archimedean ring of processors, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.542-547, December 1984
	Oded Goldreich , Liuba Shrira, On the complexity of computation in the presence of link failures: the case of a ring, Distributed Computing, v.5 n.3, p.121-131, December 1991
	S. Nishio , K. F. Li , E. G. Manning, A Resilient Mutual Exclusion Algorithm for Computer Networks, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.344-356, July 1990
	M. S. Kordafshari , M. Gholipour , M. Jahanshahi , A. T. Haghighat, Two novel algorithms for electing coordinator in distributed systems basedon bully algorithm, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-6, February 13-15, 2005, Salzburg, Austria
	Glenn Ricart, technical correspondence: on message passes in computer networks. author's response, Communications of the ACM, v.24 n.7, p.468-469, July 1981
	David Pritchard , Santosh Vempala, Symmetric network computation, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Wei-Mei Chen, Cost distribution of the Chang-Roberts leader election algorithm and related problems, Theoretical Computer Science, v.369 n.1, p.442-447, 15 December 2006
	Kay A. Robbins , Neal R. Wagner , Dennis J. Wenzel, Virtual rings: an introduction to concurrency, ACM SIGCSE Bulletin, v.21 n.2, p.23-28, June 1989
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings, Journal of the ACM (JACM), v.55 n.1, p.1-28, February 2008
	Andrey Ermolinskiy , Daekyeong Moon , Byung-Gon Chun , Scott Shenker, Minuet: rethinking concurrency control in storage area networks, Proccedings of the 7th conference on File and stroage technologies, p.311-324, February 24-27, 2009, San Francisco, California
	Marios Mavronicolas , Loizos Michael , Paul Spirakis, Computing on a partially eponymous ring, Theoretical Computer Science, v.410 n.6-7, p.595-613, February, 2009

INDEX TERMS

Keywords:
decentralized algorithms, distributed system, operating systems

Collaborative Colleagues:

D. S. Hirschberg: colleagues

J. B. Sinclair: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player