.png){kind=icon}
.png){kind=icon}
Return
Asynchronous agreement and its relation with error-correcting codes
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2007.1043.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The condition-based approach identifies sets of input vectors, called conditions, for which it is possible to design an asynchronous protocol solving a distributed problem despite process crashes. This paper establishes a direct correlation between distributed agreement problems and error-correcting codes. 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. This correlation is exemplified by concentrating on two well-known agreement problems, namely, consensus and interactive consistency, in the context of the condition-based approach. Specifically, the paper presents the following results: First, it shows that the conditions that allow interactive consistency to be solved despite f(c) crashes and f(e) value domain faults correspond exactly to the set of error- correcting codes capable of recovering from f(c) erasures and f(e) corruptions. Second, the paper proves that consensus can be solved despite f(c) crash failures iff the condition corresponds to a code whose Hamming distance is f(c) + 1 and Byzantine consensus can be solved despite f(b) Byzantine faults iff the Hamming distance of the code is 2f(b) + 1. Finally, the paper uses the above relations to establish several results in distributed agreement that are derived from known results in error-correcting codes and vice versa.
Keywords:
agreement problem
asynchronous distributed system
coding theory
condition
consensus
crash failure
distributed computing
erroneous value
error-correcting code
fault tolerance
Hamming distance
interactive consistency
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K
Organization
No organization information available