article

Free access

Lower Bounds for Distributed Maximum-Finding Algorithms

Authors:

Jan K. Pachl,

E. Korach,

D. RotemAuthors Info & Claims

Journal of the ACM (JACM), Volume 31, Issue 4

Pages 905 - 918

https://doi.org/10.1145/1634.1889

Published: 20 September 1984 Publication History

PDF eReader

References

[1]

BtJ~Ns, J E,A formal model for message passing systems. Tech. Rep. No. 91, Computer Science Dept., Indiana Umv., Bloomington, Ind., 1980.

Google Scholar

[2]

CHANG, E., AND ROBERTS R. An improved algomhm for decentmhzed extrema-finding in circular configurations of processes. Commun ACM 22, 5 (May 1979), 281-283.

Crossref

Google Scholar

[3]

DOLEV, D., KLAWE, M., AND RODE{J, M.An O(nlogn) unidirectional distributed algorithm for extrema finding in a circle. J Algortthms 3, 3 (Sept. 1982), 245-260.

Google Scholar

[4]

FRANKLIN, W. R.On an improved algorithm for decentrahzed extrema finding in circular configurations of processors. Commun ACM 25, 5 (May 1982), 336-337.

Crossref

Google Scholar

[5]

GALLAGER, R. G.Finding a leader in a network with O(E) + O(N log N) messages. M. I. T. Internal Memorandum, Massachusetts Institute of Technology, Cambridge, Mass.

Google Scholar

[6]

HIRSCHBERG, D S., AND SINCLAIR, J. B. Decentrahzed extrema-fin&ng in circular configurations of processors. Commun ACM 23, 11 (Nov. 1980), 627-628.

Crossref

Google Scholar

[7]

ITAI, A., AND RODEH, M.Symmetry breaking m dismbutive networks. In Proceedings of the 22nd Annual Sympostum on Foundauons of Computer Scwnce. (Nashvdle, Tenn., Oct. 28-30). IEEE, New York, 1981, pp 150-158.

Google Scholar

[8]

KNUTH, D. E.The Art of Computer Programmtng Vol. 1, Fundamental Algorithms 2nd ed. Addison-Wesley, Reading, Mass., 1973

Crossref

Google Scholar

[9]

KORACH, E, ROTEM, D., AND SANTORO, N A probabilisUc algorithm for decentrahzed extremafinding in a circular configuration of processors. Res. Rep. CS-81-19, Dept. of Computer Science, Umv. of Waterloo, Waterloo, Ontario, Canada, 198 l.

Google Scholar

[10]

KORACH, E., ROTEM, D., AND SANTORO, N. Distributed eleet~on in a circle wathout a global sense of orientation, lnt J. Comput Math To be pubhshed.

Google Scholar

[11]

LE LANN, G.Distributed systems--Towards a formal approach. In lnformatton Processmg 77, B. Gllchrist, Ed. Elsevier North-Holland, New York, 1977, pp. 155-160.

Google Scholar

[12]

PETERSON, G. L.An O(nlogn) unidlreeuonal algorithm for the circular extrema problem. ACM Trans Program Lang Syst 4, 4 (Oct. 1982), 758-762.

Crossref

Google Scholar

[13]

TANENBAUM, A. S.Computer Networks Prentice-Hall, New York, 1981.

Crossref

Google Scholar

Cited By

View all

Attiya Hvan Leeuwen JSantoro NZaks S(2023)Efficient elections in chordal ring networksAlgorithmica10.1007/BF015539004:1-4(437-446)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01553900
Delporte-Gallet CFauconnier HTran-The H(2014)Leader Election in Rings with HomonymsNetworked Systems10.1007/978-3-319-09581-3_2(9-24)Online publication date: 3-Aug-2014
https://doi.org/10.1007/978-3-319-09581-3_2
Raynal MRaynal M(2013)Leader Election AlgorithmsDistributed Algorithms for Message-Passing Systems10.1007/978-3-642-38123-2_4(77-92)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38123-2_4
Show More Cited By

Index Terms

Lower Bounds for Distributed Maximum-Finding Algorithms

Recommendations

Finding Worst-Case Instances of, and Lower Bounds for, Online Algorithms Using Genetic Algorithms
AI '02: Proceedings of the 15th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence

This paper presents a novel application of Genetic Algorithms, as an empirical method in the analysis of algorithms. Online Algorithms are designed for the case in which the problem input does not arrive in its totality, as in Offline Algorithms, but ...
Adversary lower bounds for nonadaptive quantum algorithms

We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and ...
Correlation lower bounds from correlation upper bounds

Study limitations of correlation as asked by Green-Roy-Straubing.First lower bound on correlation for composite moduli.New two-step (lift and reduce) technique for proving correlation lower bounds.New circuit lower bound for circuits: MAJ ANY o ( n ) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 31, Issue 4

Oct. 1984

238 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1634

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 September 1984

Published in JACM Volume 31, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
628
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)14

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Attiya Hvan Leeuwen JSantoro NZaks S(2023)Efficient elections in chordal ring networksAlgorithmica10.1007/BF015539004:1-4(437-446)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01553900
Delporte-Gallet CFauconnier HTran-The H(2014)Leader Election in Rings with HomonymsNetworked Systems10.1007/978-3-319-09581-3_2(9-24)Online publication date: 3-Aug-2014
https://doi.org/10.1007/978-3-319-09581-3_2
Raynal MRaynal M(2013)Leader Election AlgorithmsDistributed Algorithms for Message-Passing Systems10.1007/978-3-642-38123-2_4(77-92)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38123-2_4
Helary JMaddi ARaynal M(2011)Calcul réparti d'un extrémum et du routage associé dans un réseau quelconqueRAIRO - Theoretical Informatics and Applications10.1051/ita/198721030223121:3(223-244)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1987210302231
Bakhshi REndrullis JFokkink WPang J(2011)Fast leader election in anonymous rings with bounded expected delayInformation Processing Letters10.1016/j.ipl.2011.06.003111:17(864-870)Online publication date: Sep-2011
https://doi.org/10.1016/j.ipl.2011.06.003
Ikegawa YYamashita MAe T(2007)An experimental evaluation of leader election algorithms for ring networksSystems and Computers in Japan10.1002/scj.469022030222:3(10-18)Online publication date: 21-Mar-2007
https://doi.org/10.1002/scj.4690220302
Moran S(2006)Message complexity versus space complexity in fault tolerant broadcast protocolsNetworks10.1002/net.323019050319:5(505-519)Online publication date: 11-Oct-2006
https://doi.org/10.1002/net.3230190503
Kranakis EKrizanc Dvan den Berg J(2005)Computing boolean functions on anonymous networksAutomata, Languages and Programming10.1007/BFb0032037(254-267)Online publication date: 27-Jun-2005
https://doi.org/10.1007/BFb0032037
Allenberg-Navony NItai AMoran S(2005)Average and randomized complexity of distributed problemsDistributed Algorithms10.1007/BFb0020442(311-325)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0020442
Alimonti PFlocchini PSantoro N(2005)Finding the extrema of a distributed multisetDistributed Algorithms10.1007/BFb0020432(164-178)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0020432
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Finding Worst-Case Instances of, and Lower Bounds for, Online Algorithms Using Genetic Algorithms

Adversary lower bounds for nonadaptive quantum algorithms

Correlation lower bounds from correlation upper bounds

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations