Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Distributed Agreement and Its Relation with Error-Correcting Codes

R. FriedmanContact Information, A. MostéfaouiContact Information, S. Rajsbaum7, 8 Contact Information and M. RaynalContact Information

(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.

Contact Information R. Friedman
Email: roy@cs.technion.ac.il

Contact Information A. Mostéfaoui
Email: achour@irisa.fr

Contact Information S. Rajsbaum
Email: Sergio.Rajsbaum@hp.com

Contact Information M. Raynal
Email: raynal@irisa.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.108 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)