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: