×

A topological perspective on distributed network algorithms. (English) Zbl 1464.68438

Summary: More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in failure-free networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the local model and dynamic networks.

MSC:

68W15 Distributed algorithms
68M10 Network design and communication in computer systems
68M14 Distributed systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alcantara, Manuel; Castañeda, Armando; Flores-Peñaloza, David; Rajsbaum, Sergio, The topology of look-compute-move robot wait-free algorithms with hard termination, Distrib. Comput., 32, 3, 235-255 (2019) · Zbl 1451.68033
[2] Alistarh, Dan; Aspnes, James; Ellen, Faith; Gelashvili, Rati; Zhu, Leqi, Why extension-based proofs fail, (Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC (2019)), 986-996 · Zbl 1433.68052
[3] Alpern, Bowen; Schneider, Fred B., Defining liveness, Inf. Process. Lett., 21, 4, 181-185 (1985) · Zbl 0575.68030
[4] Attiya, Hagit; Castañeda, Armando; Herlihy, Maurice; Paz, Ami, Bounds on the step and namespace complexity of renaming, SIAM J. Comput., 48, 1, 1-32 (2019) · Zbl 1410.68054
[5] Balliu, Alkida; Brandt, Sebastian; Hirvonen, Juho; Olivetti, Dennis; Rabie, Mikaël; Suomela, Jukka, Lower bounds for maximal matchings and maximal independent sets, (60th IEEE Symposium on Foundations of Computer Science. 60th IEEE Symposium on Foundations of Computer Science, FOCS (2019))
[6] Barenboim, Leonid; Elkin, Michael; Goldenberg, Uri, Locally-iterative distributed \(( \delta + 1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models, (Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC (2018)), 437-446 · Zbl 1428.68365
[7] Barenboim, Leonid; Elkin, Michael; Pettie, Seth; Schneider, Johannes, The locality of distributed symmetry breaking, (53rd IEEE Symposium on Foundations of Computer Science. 53rd IEEE Symposium on Foundations of Computer Science, FOCS (2012)), 321-330
[8] Bhadra, Sandeep; Ferreira, Afonso, Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs, J. Internet Serv. Appl., 3, 3, 269-275 (2012)
[9] Biely, Martin; Robinson, Peter; Schmid, Ulrich; Schwarz, Manfred; Winkler, Kyrill, Gracefully degrading consensus and k-set agreement in directed dynamic networks, Theor. Comput. Sci., 726, 41-77 (2018) · Zbl 1390.68086
[10] Borowsky, Elizabeth; Gafni, Eli, Generalized FLP impossibility result for t-resilient asynchronous computations, (Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC (1993)), 91-100 · Zbl 1310.68078
[11] Brandt, Sebastian; Fischer, Orr; Hirvonen, Juho; Keller, Barbara; Lempiäinen, Tuomo; Rybicki, Joel; Suomela, Jukka; Uitto, Jara, A lower bound for the distributed Lovász local lemma, (48th ACM Symposium on Theory of Computing. 48th ACM Symposium on Theory of Computing, STOC (2016)), 479-488 · Zbl 1375.68191
[12] Castañeda, Armando; Fraigniaud, Pierre; Paz, Ami; Rajsbaum, Sergio; Roy, Matthieu; Travers, Corentin, A topological perspective on distributed network algorithms, (Structural Information and Communication Complexity - 26th International Colloquium. Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO (2019)), 3-18 · Zbl 07176645
[13] Castañeda, Armando; Rajsbaum, Sergio, New combinatorial topology bounds for renaming: the lower bound, Distrib. Comput., 22, 5-6, 287-301 (2010) · Zbl 1231.68068
[14] Castañeda, Armando; Rajsbaum, Sergio, New combinatorial topology bounds for renaming: the upper bound, J. ACM, 59, 1, Article 3 pp. (2012) · Zbl 1281.68159
[15] Casteigts, Arnaud; Flocchini, Paola; Godard, Emmanuel; Santoro, Nicola; Yamashita, Masafumi, On the expressivity of time-varying graphs, Theor. Comput. Sci., 590, 27-37 (2015) · Zbl 1327.68174
[16] Casteigts, Arnaud; Flocchini, Paola; Quattrociocchi, Walter; Santoro, Nicola, Time-varying graphs and dynamic networks, Int. J. Parallel Emerg. Distrib. Syst., 27, 5, 387-408 (2012)
[17] Chang, Yi-Jun; Li, Wenzheng; Pettie, Seth, An optimal distributed \((\operatorname{\Delta} + 1)\)-coloring algorithm?, (50th ACM Symposium on Theory of Computing. 50th ACM Symposium on Theory of Computing, STOC (2018)), 445-456 · Zbl 1427.68355
[18] Charron-Bost, Bernadette; Függer, Matthias; Nowak, Thomas, Approximate consensus in highly dynamic networks: the role of averaging algorithms, (Automata, Languages, and Programming - 42nd International Colloquium. Automata, Languages, and Programming - 42nd International Colloquium, ICALP (2015)), 528-539 · Zbl 1417.68012
[19] Charron-Bost, Bernadette; Függer, Matthias; Nowak, Thomas, Fast, robust, quantizable approximate consensus, (43rd International Colloquium on Automata, Languages, and Programming. 43rd International Colloquium on Automata, Languages, and Programming, ICALP (2016)), 137:1-137:14 · Zbl 1388.68293
[20] Charron-Bost, Bernadette; Schiper, André, The heard-of model: computing in distributed systems with benign faults, Distrib. Comput., 22, 1, 49-71 (2009) · Zbl 1267.68151
[21] Chaudhuri, Soma; Herlihy, Maurice; Lynch, Nancy A.; Tuttle, Mark R., Tight bounds for k-set agreement, J. ACM, 47, 5, 912-943 (2000) · Zbl 1320.68034
[22] Coulouma, Etienne; Godard, Emmanuel; Peters, Joseph G., A characterization of oblivious message adversaries for which consensus is solvable, Theor. Comput. Sci., 584, 80-90 (2015) · Zbl 1315.68008
[23] Fischer, Manuela; Ghaffari, Mohsen; Kuhn, Fabian, Deterministic distributed edge-coloring via hypergraph maximal matching, (58th IEEE Annual Symposium on Foundations of Computer Science. 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2017)), 180-191
[24] Fischer, Michael J.; Lynch, Nancy A.; Paterson, Mike, Impossibility of distributed consensus with one faulty process, J. ACM, 32, 2, 374-382 (1985) · Zbl 0629.68027
[25] Függer, Matthias; Nowak, Thomas; Schwarz, Manfred, Tight bounds for asymptotic and approximate consensus, (Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC (2018)), 325-334 · Zbl 1428.68067
[26] Ghaffari, Mohsen, An improved distributed algorithm for maximal independent set, (27th ACM-SIAM Symposium on Discrete Algorithms. 27th ACM-SIAM Symposium on Discrete Algorithms, SODA (2016)), 270-277 · Zbl 1411.68175
[27] Ghaffari, Mohsen; Kuhn, Fabian; Maus, Yannic, On the complexity of local distributed graph problems, (49th ACM Symposium on Theory of Computing. 49th ACM Symposium on Theory of Computing, STOC (2017)), 784-797 · Zbl 1370.68127
[28] Godard, Emmanuel; Perdereau, Eloi, k-Set agreement in communication networks with omission faults, (20th International Conference on Principles of Distributed Systems. 20th International Conference on Principles of Distributed Systems, OPODIS (2016)), 8:1-8:17 · Zbl 1432.68030
[29] Göös, Mika; Hirvonen, Juho; Suomela, Jukka, Linear-in-Δ lower bounds in the LOCAL model, Distrib. Comput., 30, 5, 325-338 (2017) · Zbl 1423.68192
[30] Harris, David G.; Schneider, Johannes; Su, Hsin-Hao, Distributed \((\operatorname{\Delta} + 1)\)-coloring in sublogarithmic rounds, (48th ACM Symposium on Theory of Computing. 48th ACM Symposium on Theory of Computing, STOC (2016)), 465-478 · Zbl 1376.68160
[31] Herlihy, Maurice; Kozlov, Dmitry; Rajsbaum, Sergio, Distributed Computing Through Combinatorial Topology (2013), Morgan Kaufmann · Zbl 1341.68004
[32] Herlihy, Maurice; Rajsbaum, Sergio, Set consensus using arbitrary objects, (Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing. Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC (1994)), 324-333 · Zbl 1373.68101
[33] Herlihy, Maurice; Rajsbaum, Sergio, Algebraic spans, Math. Struct. Comput. Sci., 10, 4, 549-573 (2000) · Zbl 0956.68098
[34] Herlihy, Maurice; Rajsbaum, Sergio; Tuttle, Mark R., An axiomatic approach to computing the connectivity of synchronous and asynchronous systems, Electron. Notes Theor. Comput. Sci., 230, 79-102 (2009) · Zbl 1339.68307
[35] Herlihy, Maurice; Shavit, Nir, The asynchronous computability theorem for t-resilient tasks, (25th ACM Symposium on Theory of Computing. 25th ACM Symposium on Theory of Computing, STOC (1993)), 111-120 · Zbl 1310.68079
[36] Herlihy, Maurice; Shavit, Nir, The topological structure of asynchronous computability, J. ACM, 46, 6, 858-923 (1999) · Zbl 1161.68469
[37] Kuhn, Fabian; Lynch, Nancy A.; Oshman, Rotem, Distributed computation in dynamic networks, (42nd ACM Symposium on Theory of Computing. 42nd ACM Symposium on Theory of Computing, STOC (2010)), 513-522 · Zbl 1293.68305
[38] Kuhn, Fabian; Moscibroda, Thomas; Wattenhofer, Roger, Local computation: lower and upper bounds, J. ACM, 63, 2, Article 17 pp. (2016) · Zbl 1426.68092
[39] Kuhn, Fabian; Moses, Yoram; Oshman, Rotem, Coordinated consensus in dynamic networks, (30th ACM Symposium on Principles of Distributed Computing. 30th ACM Symposium on Principles of Distributed Computing, PODC (2011)), 1-10 · Zbl 1321.68028
[40] Kuhn, Fabian; Oshman, Rotem, Dynamic networks: models and algorithms, SIGACT News, 42, 1, 82-96 (2011) · Zbl 1350.68047
[41] Linial, Nathan, Locality in distributed graph algorithms, SIAM J. Comput., 21, 1, 193-201 (1992) · Zbl 0787.05058
[42] Mendes, Hammurabi; Tasson, Christine; Herlihy, Maurice, Distributed computability in Byzantine asynchronous systems, (46th Symposium on Theory of Computing. 46th Symposium on Theory of Computing, STOC (2014)), 704-713 · Zbl 1315.68020
[43] Nowak, Thomas; Schmid, Ulrich; Winkler, Kyrill, Topological characterization of consensus under general message adversaries, (Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC (2019)), 218-227 · Zbl 07298679
[44] Peleg, David, Distributed Computing: A Locality-Sensitive Approach (2000), SIAM: SIAM Philadelphia, PA · Zbl 0959.68042
[45] Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin, The iterated restricted immediate snapshot model, (14th Int. Conference on Computing and Combinatorics. 14th Int. Conference on Computing and Combinatorics, COCOON (2008)), 487-497 · Zbl 1148.68330
[46] Sakavalas, Dimitris; Tseng, Lewis, Network topology and fault-tolerant consensus, (Synthesis Lectures on Distributed Computing Theory (2019)) · Zbl 1415.68008
[47] Saks, Michael E.; Zaharoglou, Fotios, Wait-free k-set agreement is impossible: the topology of public knowledge, (25th ACM Symposium on Theory of Computing. 25th ACM Symposium on Theory of Computing, STOC (1993)), 101-110 · Zbl 1310.68041
[48] Suomela, Jukka, Survey of local algorithms, ACM Comput. Surv., 45, 2, Article 24 pp. (2013) · Zbl 1293.68306
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.