Distributed Agreement and Its Relation with Error-Correcting Codes
R. Friedman5
, A. Mostéfaoui6
, S. Rajsbaum7, 8
and M. Raynal6 
| (5) |
Department of Computer Science, The Technion, Haifa, Israel |
| (6) |
IRISA, Université de Rennes 1, Campus de Beaulieu, 35042 Rennes, France |
| (7) |
HP Research Lab, Cambridge, MA 02139, USA |
| (8) |
Inst. Matem. UNAM, Mexico |
Abstract
The condition based approach identifies sets of input vectors, called conditions, for which it is possible to design a protocol solving a distributed problem despite process crashes. This paper investigates
three related agreement problems, namely consensus, interactive consistency, and k-set agreement, in the context of the condition-based approach. In consensus, processes have to agree on one of the proposed
values; in interactive consistency, they have to agree on the vector of proposed values; in k-set agreement, each process decides on one of the proposed values, and at most k different values can be decided on. For both consensus and interactive consistency, a direct correlation between these problems
and error correcting codes is established. In particular, crash failures in distributed agreement problems correspond to erasure
failures in error correcting codes, and Byzantine and value domain faults correspond to corruption errors. It is also shown
that less restrictive codes can be used to solve k-set agreement, but without a necessity proof, which is still an open problem.
Keywords Asynchronous Distributed System - Code Theory - Condition - Consensus - Crash Failure - Distributed Computing - Erroneous Value - Error-Correcting Code - Fault-Tolerance - Hamming Distance - Interactive Consistency
As decided by the program committee, this paper results from the merging of [17] and [24], which were developed separately.
References secured to subscribers.