research-article

Bit complexity of breaking and achieving symmetry in chains and rings

Authors:

Sergio RajsbaumAuthors Info & Claims

Journal of the ACM (JACM), Volume 55, Issue 1

Article No.: 3, Pages 1 - 28

https://doi.org/10.1145/1326554.1326557

Published: 22 February 2008 Publication History

Abstract

We consider a failure-free, asynchronous message passing network with n links, where the processors are arranged on a ring or a chain. The processors are identically programmed but have distinct identities, taken from {0, 1,…,M − 1}. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF (finding the maximum identity). We show that in chain and ring topologies, the message complexities of all three tasks are the same. Hence, we study a finer measure of complexity: the number of transmitted bits required to solve a task T, denoted BitC(T).

We prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC(Consensus) = 2 and BitC(Leader) = BitC(MaxF) = 2log₂ M ± O(1), where the gap between the lower and upper bounds is almost always 1. For a chain, BitC(Consensus) = Θ(n), BitC(Leader) = Θ(n + log M), and BitC(MaxF) = Θ(n log M). For the ring topology, we prove the lower bound of Ω(n log M) for Leader, and (hence) MaxF.

We consider also a chain where the intermediate processors have no identities. We prove that BitC(Leader) = Θ(n log M), which is equal to n times the bit complexity of the problem for two processors. For the specific case when the chain length is even, we prove that BitC(Leader) = Θ(n), for both above settings. In addition, we show that for any algorithm solving MaxF, there exists an input, for which every execution has the bit complexity Ω(n log M) (this is not the case for Leader).

In our proofs, we use both methods of distributed computing and of communication complexity theory, establishing new links between the two areas.

References

[1]

Attiya, H., and Welch, J. 1998. Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw--Hill, New York.

Digital Library

[2]

Bodlaender, H. L. 1991. New lower bound techniques for distributed leader finding and other problems on rings of processors. Theoret. Comput. Sci. 81, 237--256.

Digital Library

[3]

Bodlaender, H. L., Moran, S., and Warmuth, M. K. 1994. The distributed bit complexity of the ring: From the anonymous to the non-anonymous case. Inf. Comput. 114, 2, 34--50.

Digital Library

[4]

Burns, J. E. 1980. A formal model for message passing systems. Tech. Rep. TR-91. Computer Science Dept., Indiana Uni., Bloomington, IN.

[5]

Dietzfelbinger, M. 1997. The linear-array problem in communication complexity resolved. In Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, New York, pp. 373-- 382.

Digital Library

[6]

Dinitz, Y., Moran, S., and Rajsbaum, S. 1999. Bit complexity of breaking and achieving symmetry in paths and rings. In Proceedings of the 31th Symposium on Theory of Computing (STOC'99). ACM, New York, pp. 265--274.

Digital Library

[7]

Dinitz, Y., Moran, S., and Rajsbaum, S. 2003. Exact communication costs for consensus and leader in a tree. J. Disc. Algorithms 1, 167--183.

Digital Library

[8]

Dinitz, Y., and Solomon, N. 2007. Two absolute bounds for distributed bit complexity. Theoret. Comput. Sci. 384, 168--183.

Digital Library

[9]

Duris, P., and Galil, Z. 1991. Two lower bounds in asynchronous distributed computation. J. Comput. Syst. Sci. 42, 3, 254--266.

Digital Library

[10]

Fitzi, M., and Garay, J. 2003. Efficient player-optimal protocols for strong and differential consensus. In Proceedings of the 22nd ACM Symposium on the Principles of Distributed Computing (PODC'03) (Boston, MA, July), ACM, New York, pp. 211--220.

Digital Library

[11]

Gallager, R. G., Humblet, P. A., and Spira, P. M. 1983. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Prog. Lang. Syst. 5, 1 (Jan.), 66--77.

Digital Library

[12]

Hirschberg, D. S. and Sinclair, J. B. 1980. Decentralized extrema-finding in circular configurations of processes. Commun. ACM 23 (11), 627--628.

Digital Library

[13]

Korach, E., Moran, S., and Zaks, S. 1984. Tight upper and lower bounds for some distributed algorithms for a complete network of processors. In Proceedings of the 3th Annual ACM Symposium on Principles of Distributed Computing. ACM, New York, pp. 199--207.

Digital Library

[14]

Kushilevitz, E., and Nisan, N. 1997. Communication Complexity. Cambridge University Press, Cambridge, UK.

Digital Library

[15]

Kushilevitz, E., Lineal, N., and Ostrovsky, R. 1999. The linear-array conjecture in communication complexity is false. Combinatorica, 19, 2, 241--254.

[16]

Lynch, N. A. 1996. Distributed Algorithms. Morgan-Kaufmann. San Francisco, CA.

Digital Library

[17]

Moran, S., and Warmuth, M. K. 1993. Gap theorem in distributed computing. SIAM J. Comput. 22, 2, 379--394.

Digital Library

[18]

Moran, S., and Wolfsthal, Y. 1987. An extended impossibility result for asynchronous complete networks. Inf. Proc. Lett. 26, 141--151.

Digital Library

[19]

Tel, G. 1994. Introduction to Distributed Algorithms, Cambridge University Press, Cambridge, UK.

Digital Library

[20]

Tiwari, P. 1987. Lower bounds on communication complexity in distributed computer networks. J. ACM 34, 921--938.

Digital Library

[21]

Yao, A. C. 1979. Some complexity questions related to distributed computing. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing, ACM, New York, pp. 209--213.

Digital Library

Cited By

Rincon Galeana HSchmid U(2024)Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed SystemsStructural Information and Communication Complexity10.1007/978-3-031-60603-8_29(501-506)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_29
Fraigniaud PGelles RLotker Z(2023)The topology of randomized symmetry-breaking distributed computingJournal of Applied and Computational Topology10.1007/s41468-023-00150-98:4(909-940)Online publication date: 13-Nov-2023
https://doi.org/10.1007/s41468-023-00150-9
Delporte-Gallet CFauconnier HRajsbaum S(2020)Communication Complexity of Wait-Free Computability in Dynamic NetworksStructural Information and Communication Complexity10.1007/978-3-030-54921-3_17(291-309)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-54921-3_17
Show More Cited By

Index Terms

Bit complexity of breaking and achieving symmetry in chains and rings

Recommendations

The Complexity of Leader Election: A Chasm at Diameter Two
ICDCN '18: Proceedings of the 19th International Conference on Distributed Computing and Networking

Leader election is one of the fundamental problems in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message complexity of leader election in synchronous ...
Exact communication costs for consensus and leader in a tree

We continue the study of communication costs of Consensus and Leader initiated in a previous paper. We deal with all scenarios with linear complexity in a tree topology, and prove exact (as opposed to asymptotic) tight bounds for the bit and message ...
Two absolute bounds for distributed bit complexity

The concept of distributed communication bit complexity was introduced by Dinitz, Rajsbaum, and Moran. They studied the bit complexity of Consensus and Leader Election, arriving at more or less exact bounds. This paper answers two questions on Leader ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 55, Issue 1

February 2008

158 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1326554

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 February 2008

Accepted: 01 October 2007

Revised: 01 October 2007

Received: 01 August 2004

Published in JACM Volume 55, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Pre-selected

Funding Sources

United States-Israel Binational Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rincon Galeana HSchmid U(2024)Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed SystemsStructural Information and Communication Complexity10.1007/978-3-031-60603-8_29(501-506)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_29
Fraigniaud PGelles RLotker Z(2023)The topology of randomized symmetry-breaking distributed computingJournal of Applied and Computational Topology10.1007/s41468-023-00150-98:4(909-940)Online publication date: 13-Nov-2023
https://doi.org/10.1007/s41468-023-00150-9
Delporte-Gallet CFauconnier HRajsbaum S(2020)Communication Complexity of Wait-Free Computability in Dynamic NetworksStructural Information and Communication Complexity10.1007/978-3-030-54921-3_17(291-309)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-54921-3_17
Casteigts AMétivier YRobson JZemmari A(2019)Deterministic Leader Election Takes $$\Theta (D + \log n)$$?(D+logn) Bit RoundsAlgorithmica10.1007/s00453-018-0517-381:5(1901-1920)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00453-018-0517-3
Pfleger DSchmid U(2018)On Knowledge and Communication Complexity in Distributed SystemsStructural Information and Communication Complexity10.1007/978-3-030-01325-7_27(312-330)Online publication date: 31-Oct-2018
https://doi.org/10.1007/978-3-030-01325-7_27
Vyalyi MKhuziev I(2017)Fast protocols for leader election and spanning tree construction in a distributed networkProblems of Information Transmission10.1134/S003294601702006553:2(183-201)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1134/S0032946017020065
Castan͂eda AImbs DRajsbaum SRaynal M(2016)Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent ObjectsSIAM Journal on Computing10.1137/13093682845:2(379-414)Online publication date: Jan-2016
https://doi.org/10.1137/130936828
Métivier YRobson JZemmari A(2016)A distributed enumeration algorithm and applications to all pairs shortest paths, diameter...Information and Computation10.1016/j.ic.2015.12.004247:C(141-151)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1016/j.ic.2015.12.004
Casteigts AMétivier YRobson JZemmari A(2016)Deterministic Leader Election in $$O(D+\log n)$$ Time with Messages of Size O(1)Distributed Computing10.1007/978-3-662-53426-7_2(16-28)Online publication date: 4-Sep-2016
https://doi.org/10.1007/978-3-662-53426-7_2
Vyalyi MKhuziev I(2015)Distributed communication complexity of spanning tree constructionProblems of Information Transmission10.1134/S003294601501006851:1(49-65)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1134/S0032946015010068
Show More Cited By

View Options

Get Access

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents