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: |