Synchronous Set Agreement: a Concise Guided Tour with open problemsReport as inadecuate

Synchronous Set Agreement: a Concise Guided Tour with open problems - Download this document for free, or read online. Document in PDF available to download.

1 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires

Abstract : The $k$-set agreement problem is a paradigm of coordination problems encountered in distributed computing. The parameter $k$ defines the coordination degree we are interested in. The case $k=1$ corresponds to the well-known uniform consensus problem. More precisely, the $k$-set agreement problem considers a system made up of $n$ processes where each process proposes a value. It requires that each non-faulty process decides a value such that a decided value is a proposed value, and no more than $k$ different values are decided. This paper visits the $k$-set agreement problem in synchronous systems where up to $t$ processes can experience failures. Three failure models are explored: the crash failure model, the send omission failure model, and the general omission failure model. Lower bounds and protocols are presented for each model. Open problems for the general omission failure model are stated. This paper can be seen as a short tutorial whose aim is to make the reader familiar with the $k$-set agreement problem in synchrony models with increasing fault severity. An important concern of the paper is simplicity. In addition to its survey flavor, several results and protocols that are presented are new. \\ Ce rapport constitue une visite guidé de l-accord ensembliste synchrone en présence de crashs, de fautes d-omission en émission, et de fautes d-omission en émission et réception.

Mots-clés : Agreement problem Consensus Crash failure Distributed algorithm Early decision Efficiency General omission failure k-set agreement Lower bound Message-passing system Receive omission failure Round-based computation Send omission failure Synchronous system \\ Systèmes répartis asynchrones Tolérance aux fautes Crash de processus Accord ensembliste Omission en émission Omission en réception

Author: Michel Raynal - Corentin Travers -



Related documents