1. Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks
- Author
-
Pierre Sens, Thibault Rieutord, Luciana Arantes, Denis Jeanneau, Sens, Pierre, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Département Informatique et Réseaux (INFRES), Télécom ParisTech, Labex SMART, supported by French state funds managed by the ANR within the Investissements d’Avenir programmeunder reference ANR-11-LABX-65., and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Discrete mathematics ,020203 distributed computing ,K-set ,Dynamic networks ,Computer science ,Detector ,Failure detectors ,k-Set agreement ,0102 computer and information sciences ,02 engineering and technology ,Distributed systems ,01 natural sciences ,Formalism (philosophy of mathematics) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Hardware and Architecture ,Asynchronous communication ,Signal Processing ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,0202 electrical engineering, electronic engineering, information engineering ,Failure detector ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Algorithm - Abstract
The failure detector abstraction has been used to solve agreement problems in asynchronous systems prone to crash failures, but so far it has mostly been used in static and complete networks. This paper aims to adapt existing failure detectors in order to solve agreement problems in unknown, dynamic systems. We are specifically interested in the k-set agreement problem. The problem of k-set agreement is a generalization of consensus where processes can decide up to k different values. Although some solutions to this problem have been proposed in dynamic networks, they rely on communication synchrony or make strong assumptions on the number of process failures. In this paper we consider unknown dynamic systems modeled using the formalism of Time-Varying Graphs, and extend the definition of the existing $\Pi \Sigma _{x,y}$ failure detector to obtain the $\Pi \Sigma _{\bot, x,y}$ failure detector, which is sufficient to solve k-set agreement in our model. We then provide an implementation of this new failure detector using connectivity and message pattern assumptions. Finally, we present an algorithm using $\Pi \Sigma _{\bot, x,y}$ to solve k-set agreement.
- Published
- 2017
- Full Text
- View/download PDF