Narrowing Power vs. Efficiency in Synchronous Set Agreement
Autor: | Michel Raynal, Achour Mostefaoui, Corentin Travers |
---|---|
Přispěvatelé: | As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Shrisha Rao, Mainak Chatterjee and Prasad Jayanti and C. Siva Ram Murthy and Sanjoy Kumar Saha, SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique |
Jazyk: | angličtina |
Rok vydání: | 2008 |
Předmět: |
Consensus
Lower bound Generalization Computer science Value (computer science) 0102 computer and information sciences 02 engineering and technology Efficiency Set agreement 01 natural sciences Upper and lower bounds Uniform consensus Synchronous system ACM: C.: Computer Systems Organization/C.4: PERFORMANCE OF SYSTEMS 0202 electrical engineering electronic engineering information engineering ComputingMilieux_MISCELLANEOUS Discrete mathematics Asynchronous system Computability 020207 software engineering Base (topology) Round-based algorithm 010201 computation theory & mathematics ACM: D.: Software/D.4: OPERATING SYSTEMS [INFO.INFO-OS]Computer Science [cs]/Operating Systems [cs.OS] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Algorithm $t$-Resilience |
Zdroj: | 9th International Conference on Distributed Computing and Networking 9th International Conference on Distributed Computing and Networking, Jan 2008, Kolkata, India. pp.99-111 [Research Report] PI 1836, 2007, pp.13 Distributed Computing and Networking ISBN: 9783540774433 ICDCN |
Popis: | The k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most k different values are decided. It has been shown that any algorithm that solves the k-set agreement problem in synchronous systems that can suffer up to t crash failures requires ⌊t/k⌋ + 1 rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after min (⌊f/k⌋ + 2, ⌊t/k⌋ + 1) rounds, where f is the number of actual crashes in a run (0 ≤ f ≤ t). This paper explores a new direction to solve the k-set agreement problem in a synchronous system. It considers that the system is enriched with base objects (denoted [m, l]-SA objects) that allow solving the l-set agreement problem in a set of mprocesses (m < n). The paper has several contributions. It first proposes a synchronous k-set agreement algorithm that benefits from such underlying base objects. This algorithm requires O(tl/mk ) rounds, more precisely, Rt = ⌊t/Δ⌋ + 1 rounds, where Δ = m⌊k/l⌋ + (k mod l). The paper then shows that this bound, that involves all the parameters that characterize both the problem (k) and its environment (t, m and l), is a lower bound. The proof of this lower bound sheds additional light on the deep connection between synchronous efficiency and asynchronous computability. Finally, the paper extends its investigation to the early deciding case. It presents a k-set agreement algorithm that directs the processes to decide and stop by round Rf = min ⌊f/Δ⌋ + 2, ⌊t/Δ⌋ + 1). These bounds generalize the bounds previously established for solving the k-set problem in pure synchronous systems. |
Databáze: | OpenAIRE |
Externí odkaz: |