Reaching Agreement in the Presence of Faults：在故障的存在达成协议.ppt

Reaching Agreement in the Presence of Faults M. Pease, R. Shostak, and L. Lamport SRI International, Menlo Park, California Abstract The problem concerns a set of isolated processors, some unknown subset of which may be faulty. Each non-faulty processor has a private value that must be communicated to every other non-faulty processor. The Problem The value inferred for a non-faulty processor must be the processor’s private value and the value inferred for a faulty processor must be consistent with the corresponding value inferred by each other non-faulty processor. Claim The given problem is only solvable for n ≥ 3m +1, where m is the number of faulty processors and n is the total number of processors. Interactive Consistency Compute a vector of values for every processor, such that: The non-faulty processors compute the exact same vector The element of this vector corresponding to a given non-faulty processor is the private value of that processor. Interactive Consistency The algorithm guarantees Interactive Consistency since it allows the non-faulty processors to come to a consistent view of all processors. The computed vector is called the Interactive Consistency Vector. The Single-Fault Case m=1, n=4 The procedure consists of an exchange of messages, followed by the computation of the interactive consistency vector on the basis of the results of the exchange. Two Rounds of exchange are required. In the first round the processors exchange their private values and in the second round they exchange the results obtained in the first round. The Single-Fault Case The Single-Fault Case The Single-Fault Case The Single-Fault Case The Single-Fault Case The Single-Fault Case The Single-Fault Case The Single-Fault Case Procedure for n≥3m+1 For 1 faulty processor ? 2 rounds of communication For m faulty processors ? m+1 rounds of communication P: Set of processors V: Set of values k≥1: k-level scenario ? mapping from a set of non-empty strings {p1,p2,p3,…p