A Topological Perspective on Distributed Network Algorithms

Autor: Ami Paz, Matthieu Roy, Sergio Rajsbaum, Pierre Fraigniaud, Armando Castañeda, Corentin Travers
Přispěvatelé: Technion - Israel Institute of Technology [Haifa], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Pierre Fraigniaud and Corentin Travers are supported by ANR projects DESCARTES and FREDA, Pierre Fraigniaud receives additional support from INRIA project GANG, Ami Paz is supported by the Fondation Sciences Mathématiques de Paris (FSMP), Sergio Rajsbaum is supported by project unam-papiit IN109917., Keren Censor-Hillel, Michele Flammini, ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2
Jazyk: angličtina
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
Network algorithms
General Computer Science
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Structure (category theory)
Combinatorial topology
0102 computer and information sciences
02 engineering and technology
Topology
01 natural sciences
Theoretical Computer Science
0202 electrical engineering
electronic engineering
information engineering
ComputingMilieux_MISCELLANEOUS
Message passing
Perspective (graphical)
020207 software engineering
16. Peace & justice
Distributed computing
Shared memory
Computer Science - Distributed
Parallel
and Cluster Computing
Distributed algorithm
010201 computation theory & mathematics
Distributed graph algorithms
020201 artificial intelligence & image processing
Distributed
Parallel
and Cluster Computing (cs.DC)
[INFO.INFO-DC]Computer Science [cs]/Distributed
Parallel
and Cluster Computing [cs.DC]
Zdroj: 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019)
26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), Jul 2019, L'Aquila, Italy. ⟨10.1007/978-3-030-24922-9_1⟩
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2021, 849, pp.121-137. ⟨10.1016/j.tcs.2020.10.012⟩
26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), Jul 2019, L'Aquila, Italy
Structural Information and Communication Complexity ISBN: 9783030249212
SIROCCO
ISSN: 1879-2294
0304-3975
Popis: International audience; 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 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.
Databáze: OpenAIRE
Externí odkaz: