Communication Complexity of Consensus in Anonymous Message Passing Systems

• Autorzy: Fusco E. G. , Pelc A.

Identyfikatory

DOI

10.3233/FI-2015-1181

• Języki publikacji: EN

Abstrakty

EN

We consider the message complexity of achieving consensus in synchronous anonymous message passing systems. Unlabeled processors (nodes) communicate through links of a network. An adversary wakes up some subset of processors at possibly different times and assigns them arbitrary numerical input values. All other processors are dormant and do not have input values. Any message wakes up a dormant processor. The goal of consensus is to have all processors agree on one of the input values. We seek deterministic consensus algorithms using as few messages as possible. As opposed to most of the literature on consensus, the difficulty of our scenario are not faults (we assume that the network is fault-free) but the arbitrary network topology combined with the anonymity of nodes. For n-node networks of unknown topology we show a consensus algorithm using Ώ(n²) messages; this complexity is optimal for this class. We show that if the network topology is known, then the complexity of consensus decreases significantly. Our main contribution is an algorithm that uses Ώ(n^2/3 log² n) messages on any n-node network and we show that some networks require (n log n) messages to achieve consensus.

Słowa kluczowe

EN

algorithm; consensus; anonymous networks; message complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 3
• Strony: 305--322
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Fusco E. G.

• Department of Computer, Control, and Management Engineering “Antonio Ruberti”, Sapienza, University of Rome Via Ariosto 25, 00185 Rome, Italy

autor

Pelc A.

• Département d’informatique, Université du Québec en Outaouais, Gatineau Québec J8X 3X7, Canada

Bibliografia

• [1] N. A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.
• [2] L. Gasieniec, A. Pelc, D. Peleg, The wakeup problem in synchronous broadcast systems, SIAM J. Discrete Math. 14 (2) (2001) 207–222.
• [3] H. Attiya, J. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition), John Wiley Interscience, 2004.
• [4] M. C. Pease, R. E. Shostak, L. Lamport, Reaching agreement in the presence of faults, J. ACM 27 (2) (1980) 228–234.
• [5] M. Raynal, Fault-tolerant Agreement in Synchronous Message-passing Systems, Morgan & Claypool, 2010.
• [6] S. Gilbert, D. R. Kowalski, Distributed agreement with optimal communication complexity, in: M. Charikar (Ed.), SODA, SIAM, 2010, pp. 965–977.
• [7] V. Hadzilacos, J. Y. Halpern, Message-optimal protocols for byzantine agreement, Mathematical Systems Theory 26 (1) (1993) 41–102.
• [8] G. Chockler, M. Demirbas, S. Gilbert, N. A. Lynch, C. C. Newport, T. Nolte, Consensus and collision detectors in radio networks, Distributed Computing 21 (1) (2008) 55–84.
• [9] Y. Moses, M. Raynal, Revisiting simultaneous consensus with crash failures, Journal of Parallel and Distributed Computing 69 (4) (2009) 400 – 409. doi:http://dx.doi.org/10.1016/j.jpdc.2009.01.001.
• [10] J. Czyzowicz, L. Gasieniec, D. R. Kowalski, A. Pelc, Consensus and mutual exclusion in a multiple access channel, IEEE Trans. Parallel Distrib. Syst. 22 (7) (2011) 1092–1104.
• [11] J. E. Burns, A formal model for message passing systems, Tech. Rep. TR-91, Computer Science Department, Indiana University, Bloomington (September 1980).
• [12] B. S. Chlebus, D. R. Kowalski, M. Strojnowski, Scalable quantum consensus for crash failures, in: N. A. Lynch, A. A. Shvartsman (Eds.), DISC, Vol. 6343 of Lecture Notes in Computer Science, Springer, 2010, pp. 236–250.
• [13] B. S. Chlebus, L. Gasieniec, D. R. Kowalski, T. Radzik, On the wake-up problem in radio networks, in: L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, M. Yung (Eds.), ICALP, Vol. 3580 of Lecture Notes in Computer Science, Springer, 2005, pp. 347–359.
• [14] B. S. Chlebus, D. R. Kowalski, A better wake-up in radio networks, in: S. Chaudhuri, S. Kutten (Eds.), PODC, ACM, 2004, pp. 266–274.
• [15] A. Czumaj, W. Rytter, Broadcasting algorithms in radio networks with unknown topology, in: FOCS, IEEE Computer Society, 2003, pp. 492–501.
• [16] B. S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in ad hoc radio networks, Distributed Computing 15 (1) (2002) 27–38.
• [17] D. Angluin, Local and global properties in networks of processors (extended abstract), in: R. E. Miller, S. Ginsburg, W. A. Burkhard, R. J. Lipton (Eds.), STOC, ACM, 1980, pp. 82–93.
• [18] P. Boldi, S. Vigna, Computing anonymously with arbitrary knowledge, in: PODC, 1999, pp. 181–188.
• [19] P. Boldi, S. Shammah, S. Vigna, B. Codenotti, P. Gemmell, J. Simon, Symmetry breaking in anonymous networks: Characterizations, in: ISTCS, 1996, pp. 16–26.
• [20] E. Kranakis, Invited talk: Symmetry and computability in anonymous networks, in: N. Santoro, P. G. Spirakis (Eds.), SIROCCO, Carleton Scientific, 1996, pp. 1–16.
• [21] E. Kranakis, D. Krizanc, J. van den Berg, Computing boolean functions on anonymous networks, Inf. Comput. 114 (2) (1994) 214–236.
• [22] N. Sakamoto, Comparison of initial conditions for distributed algorithms on anonymous networks, in: PODC, 1999, pp. 173–179.
• [23] M. Yamashita, T. Kameda, Computing on an anonymous network, in: PODC, 1988, pp. 117–130.
• [24] M. Yamashita, T. Kameda, Computing on anonymous networks: Part I-characterizing the solvable cases, IEEE Trans. Parallel Distrib. Syst. 7 (1) (1996) 69–89.
• [25] H. Attiya, M. Snir, M. K. Warmuth, Computing on an anonymous ring, J. ACM 35 (4) (1988) 845–875.
• [26] H. Attiya, M. Snir, Better computing on the anonymous ring, J. Algorithms 12 (2) (1991) 204–238.
• [27] K. Diks, E. Kranakis, A. Malinowski, A. Pelc, Anonymous wireless rings, Theor. Comput. Sci. 145 (1&2) (1995) 95–109.