An improved algorithm for decentralized extrema-finding in circular configurations of processes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An improved algorithm for decentralized extrema-finding in circular configurations of processes

Full text

Pdf (243 KB)

Source

Communications of the ACM archive
Volume 22 , Issue 5 (May 1979) table of contents

Pages: 281 - 283

Year of Publication: 1979

ISSN:0001-0782

Authors

Ernest Chang	Univ. of Toronto, Toronto, Ont., Canada
Rosemary Roberts	Univ. of Waterloo, Ontario, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 97, Citation Count: 43

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

ABSTRACT

This note presents an improvement to LeLann's algorithm for finding the largest (or smallest) of a set of uniquely numbered processes arranged in a circle, in which no central controller exists and the number of processes is not known a priori. This decentralized algorithm uses a technique of selective message extinction in order to achieve an average number of message passes of order (n log n) rather than O(n2).

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.

LeLann, G. Distributed systems-Towards a formal approach. Information Processing 77, North-Holland Pub. Co., Amsterdam, pp. 155-160.

CITED BY 43

	I. R. Forman, Design by decomposition of multiparty interactions in Raddle87, ACM SIGSOFT Software Engineering Notes, v.14 n.3, p.2-10, May 1989
	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
	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
	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
	Ernest Chang, Technical correspondence: on message passes in computer networks., Communications of the ACM, v.24 n.7, p.468, July 1981
	J. Nehmer , T. Becker, A fault tolerance approach for distributed ISDN control systems, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-4, September 03-05, 1990, Bologna, Italy
	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
	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
	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
	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
	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
	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
	Hubert Garavel , Radu Mateescu , Irina Smarandache, Parallel state space construction for model-checking, Proceedings of the 8th international SPIN workshop on Model checking of software, p.217-234, May 2001, Toronto, Ontario, Canada
	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
	D. S. Hirschberg , J. B. Sinclair, Decentralized extrema-finding in circular configurations of processors, Communications of the ACM, v.23 n.11, p.627-628, Nov. 1980
	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
	Bhargav R. Bellur , Galen H. Sasaki, A SAT-based network access scheme for fairness in high speed networks, IEEE/ACM Transactions on Networking (TON), v.5 n.3, p.371-381, June 1997
	Christof Fetzer , Flaviu Cristian, A Highly Available Local Leader Election Service, IEEE Transactions on Software Engineering, v.25 n.5, p.603-618, September 1999
	H. C. Cunningham , G. C. Roman, A UNITY-Style Programming Logic for Shared Dataspace Programs, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.365-376, July 1990
	Stefan Dobrev , Peter Ružička, On the communication complexity of strong time-optimal distributed algorithms, Nordic Journal of Computing, v.5 n.2, p.87-104, Summer 1998
	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
	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
	Edward E. Balkovich , Colin Whitby-Strevens, On the performance of decentralized software, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.173-180, Summer 1980
	Marco Carbone , Sergio Maffeis, On the expressive power of polyadic synchronisation in π-calculus, Nordic Journal of Computing, v.10 n.2, p.70-98, Summer 2003
	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
	Nicola Santoro, Sense of direction, topological awareness and communication complexity, ACM SIGACT News, v.16 n.2, p.50-56, Summer 1984
	Masafumi Yamashita , Tsunehiko Kameda, Leader Election Problem on Networks in which Processor Identity Numbers Are Not Distinct, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.878-887, September 1999
	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
	Jacob Brunekreef , Joost-Pieter Katoen , Ron Koymans , Sjouke Mauw, Design and analysis of dynamic leader election protocols in broadcast networks, Distributed Computing, v.9 n.4, p.157-171, February 1996
	Gruia-Catalin Roman , H. Conrad Cunningham, Mixed Programming Metaphors in a Shared Dataspace Model of Concurrency, IEEE Transactions on Software Engineering, v.16 n.12, p.1361-1373, December 1990
	Masafumi Yamashita , Tsunehiko Kameda, Computing on Anonymous Networks: Part I-Characterizing the Solvable Cases, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.69-89, January 1996
	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
	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
	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
	J. Nehmer , T. Becker, A fault tolerance approach for distributed ISDN control systems, ACM SIGOPS Operating Systems Review, v.25 n.2, p.126-129, April 1991
	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
	Kay Dörnemann , Jörg Prenzer , Bernd Freisleben, A peer-to-peer meta-scheduler for service-oriented grid environments, Proceedings of the first international conference on Networks for grid applications, October 17-19, 2007, Lyon, France
	Thomas Weise , Michael Zapf, Evolving distributed algorithms with genetic programming: election, Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, June 12-14, 2009, Shanghai, China

INDEX TERMS

Keywords:
decentralized algorithms, distributed systems, operating systems

Collaborative Colleagues:

Ernest Chang: colleagues

Rosemary Roberts: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player