Distributed Agreement and Its Relation with Error-Correcting Codes

摘要

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 κ-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 fc-set agreement, each process decides on one of the proposed values, and at most κ 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 fc-set agreement, but without a necessity proof, which is still an open problem.