Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A simple, efficient algorithm for maximum finding on rings

  • Conference paper
  • First Online:
Distributed Algorithms (WDAG 1993)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 725))

Included in the following conference series:

Abstract

The maximum finding problem is: given a network of processors with distinct identifiers, find that processor with the maximum identifier. We present a new deterministic algorithm for maximum finding on asynchronous unidirectional rings. For the past decade, the record for the lowest worst case message complexity (1.356n log n+O(n)) for maximum finding for this model has been held by an involved algorithm with a complicated analysis. Our algorithm is simple, has a very much simpler analysis and achieves a lower worst case message complexity (less than 1.271n log n+O(n) messages). An additional contribution of this paper is a new perspective on this problem that exhibits its structure thus permitting a better understanding of various message saving mechanisms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. Chang and R. Roberts. An improved algorithm for decentralized extrema-finding in circular configurations of processes. Communications of the ACM, 22(5):281–283, 1979.

    Google Scholar 

  2. D. Dolev, M. Klawe, and M. Rodeh. An O(n log n) unidirectional distributed algorithm for extrema finding in a circle. J. Algorithms, 3(3):245–260, 1982.

    Google Scholar 

  3. L. Higham and T. Przytycka. A simple, efficient algorithm for maximum finding on rings. Technical Report 92/494/32, University of Calgary, 1992. submitted for publication.

    Google Scholar 

  4. D. Hirschberg and J. B. Sinclair. Decentralized extrema-finding in circular configurations of processes. Communications of the ACM, 23(11):627–628, 1980.

    Google Scholar 

  5. G. LeLann. Distributed systems — towards a formal approach. In Information Processing 77, pages 155–160, New York, 1977. Elsevier Science.

    Google Scholar 

  6. G. Peterson. An O(n log n) algorithm for the circular extrema problem. ACM Trans. on Prog. Lang. and Systems, 4(4):758–752, 1982.

    Google Scholar 

  7. J. van Leeuwen and R. B. Tan. An improved upperbound for distributed election in bidirectional rings of processors. Technical Report RUU-CS-85-23, Rijksuniversiteit Utrecht, 1986.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of Calgary, T2N-1N4, Calgary, Alberta, Canada

    Lisa Higham

  2. Dept. of Math. and Computer Science, Odense University, DK-5230, Odense M, Denmark

    Teresa Przytycka

Authors
  1. Lisa Higham
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Teresa Przytycka
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

André Schiper

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Higham, L., Przytycka, T. (1993). A simple, efficient algorithm for maximum finding on rings. In: Schiper, A. (eds) Distributed Algorithms. WDAG 1993. Lecture Notes in Computer Science, vol 725. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57271-6_40

Download citation

  • DOI: https://doi.org/10.1007/3-540-57271-6_40

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-57271-8

  • Online ISBN: 978-3-540-48029-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation