More Web Proxy on the site http://driver.im/

article

Sorting and election in anonymous asynchronous rings

Authors:

Paola Flocchini,

Evangelos Kranakis,

Flaminia L. Luccio,

Nicola SantoroAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 64, Issue 2

Pages 254 - 265

https://doi.org/10.1016/j.jpdc.2003.11.007

Published: 01 February 2004 Publication History

Abstract

In an anonymous ring of n processors, all processors are totally indistinguishable except for their input values. These values are not necessarily distinct, i.e., they form a multiset, and this makes many problems particularly difficult. We consider the problem of distributively sorting such a multiset on the ring, and we give a complete characterization of the relationship with the problems of leader election for vertices and edges. For Boolean input values and prime n, we also establish a lower bound, and a reasonably close upper bound on the message complexity valid for sorting and leader election.

References

[1]

{1} P. Alimonti, P. Flocchini, N. Santoro, Finding the extrema of a distributed multiset, J. Parallel Distrib. Comput. 37 (2) (1996) 123-133.

Digital Library

[2]

{2} D. Angluin, Local and global properties in networks of processors, in: Proceedings of the 12th ACM Symposium on Theory of Computing, Las Angeles, CA, 1980, pp. 82-93.

Digital Library

[3]

{3} H. Attiya, M. Snir, Better computing on the anonymous ring, J. Algorithms 12 (2) (1991) 204-238.

Digital Library

[4]

{4} H. Attiya, M. Suir, M. Warmuth, Computing on an anonymous ring, J. ACM 35 (4) (1988) 845-875.

Digital Library

[5]

{5} H.L. Bodlaender, S. Moran, M.K. Warmuth, The distributed bit complexity of the ring: from the anonymous to the non-anonymous case, Inform. Comput. 108 (1) (1994) 34-50.

Digital Library

[6]

{6} P. Ferragina, A. Monti, A. Roncato, Trade-off between computation power and common knowledge in anonymous rings, in: Proceedings of the First Colloquium on Structural Information and Communication Complexity, Ottowa, Canada, 1994, pp. 35-48.

[7]

{7} P. Flocchini, E. Kranakis, D. Krizanc, F.L. Luccio, N. Santoro, Sorting multisets in anonymous rings, in: Proceedings of the 14th IEEE International Parallel and Distributed Processing Symposium, Cancun, Mexico, 2000, pp. 275-280.

Digital Library

[8]

{8} O. Gerstel, S, Zaks, The bit complexity of distributed sorting, Algorithmica 18 (1997) 405-416.

[9]

{9} E. Kranakis, D. Krizanc, F.L. Luccio, On recognizing a string on an anonymous ring, Theory Comput. Systems 34 (1) (2001) 3-12.

[10]

{10} M.C. Loui, The complexity of sorting on distributed systems, Inform. Control 60 (1-3) (1984) 70-85.

Digital Library

[11]

{11} N. Lynch, Distributed Algorithms, Morgan-Kaufmann, San Mateo, CA, 1996.

Digital Library

[12]

{12} S. Moran, M.K. Warmuth, Gap theorems for distributed computation, SIAM J. Comput. 22 (2) (1993) 379-394.

Digital Library

[13]

{13} D. Rotem, N. Santoro, J.B. Sidney, Distributed sorting, IEEE Trans. Comput. 34 (4) (1985) 372-376.

Digital Library

[14]

{14} N. Sakamoto, Comparison of initial conditions for distributed algorithms on anonymous networks, in: Proceedings of the 18th Annual ACM Symposium on Distributed Computing, Atlanta, GA, USA, 1999, pp. 173-179.

Digital Library

[15]

{15} M. Yamashita, T. Kameda, Computing on anonymous networks, Part I: characterizing the solvable cases, IEEE Trans. Parallel Distrib. Systems 7 (1) (1996) 69-89.

Digital Library

[16]

{16} M. Yamashita, T. Kameda, Leader election problem on networks in which processor identity numbers are not distinct, IEEE Trans. Parallel Distrib. Systems 9 (10) (1999) 878-887.

Digital Library

Cited By

Frei FGelles RGhazy ANolin AKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Content-Oblivious Leader Election on RingsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662785(549-552)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662785
Gorain B Miller APelc A(2023)Four shades of deterministic leader election in anonymous networksDistributed Computing10.1007/s00446-023-00451-336:4(419-449)Online publication date: 31-May-2023
https://dl.acm.org/doi/10.1007/s00446-023-00451-3
Miller APelc AYadav R(2022)Deterministic Leader Election in Anonymous Radio NetworksACM Transactions on Algorithms10.1145/352717118:3(1-33)Online publication date: 11-Oct-2022
https://dl.acm.org/doi/10.1145/3527171
Show More Cited By

Index Terms

Sorting and election in anonymous asynchronous rings

Recommendations

Sorting Multisets in Anonymous Rings
IPDPS '00: Proceedings of the 14th International Symposium on Parallel and Distributed Processing

An anonymous ring network is a ring where all processors (vertices) are indistinguishable except for their input value. Initially, to each vertex of the ring is associated a value from a totally ordered set; thus, forming a multiset.In this paper, we ...
Tighter upper bound for sorting permutations with prefix transpositions

Permutations are sequences where each symbol in the given alphabet Σ appears exactly once. A transposition is an operation that exchanges two adjacent sublists in a permutation; if one of these sublists is restricted to be a prefix then one obtains a ...
Improved upper bound for sorting permutations by prefix transpositions
Abstract
Modelling of chromosomes with permutations has triggered the research of sorting permutations using global rearrangement operations in computational molecular biology. One such rearrangement is transposition which swaps two adjacent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 64, Issue 2

February 2004

135 pages

ISSN:0743-7315

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Frei FGelles RGhazy ANolin AKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Content-Oblivious Leader Election on RingsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662785(549-552)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662785
Gorain B Miller APelc A(2023)Four shades of deterministic leader election in anonymous networksDistributed Computing10.1007/s00446-023-00451-336:4(419-449)Online publication date: 31-May-2023
https://dl.acm.org/doi/10.1007/s00446-023-00451-3
Miller APelc AYadav R(2022)Deterministic Leader Election in Anonymous Radio NetworksACM Transactions on Algorithms10.1145/352717118:3(1-33)Online publication date: 11-Oct-2022
https://dl.acm.org/doi/10.1145/3527171
Gorain BMiller APelc AAgrawal KAzar Y(2021)Four Shades of Deterministic Leader Election in Anonymous NetworksProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461794(265-274)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461794
Gąsieniec LStachowiak G(2020)Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader ElectionJournal of the ACM10.1145/342465968:1(1-21)Online publication date: 17-Nov-2020
https://dl.acm.org/doi/10.1145/3424659
Miller APelc AYadav RScheideler CSpear M(2020)Deterministic Leader Election in Anonymous Radio NetworksProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400276(407-417)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400276
Gąsieniec LStachowiak GUznanski PScheideler CBerenbrink P(2019)Almost Logarithmic-Time Space Optimal Leader Election in Population ProtocolsThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323178(93-102)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323178
Dieudonné YPelc A(2019)Impact of Knowledge on Election Time in Anonymous NetworksAlgorithmica10.1007/s00453-018-0444-381:1(238-288)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s00453-018-0444-3
Gαsieniec LStachowiak GCzumaj A(2018)Fast space optimal leader election in population protocolsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175286(265-266)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175286
Dieudonné YPelc AScheideler CHajiaghayi M(2017)Impact of Knowledge on Election Time in Anonymous NetworksProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3087556.3087563(207-215)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3087556.3087563
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents