Simple Fast Quorum Requirement Sample Clauses

Simple Fast Quorum Requirement. If Q, R, and S are quorums, then Q ∩ R ∩ S /= Ø. We will explain how Assumption 2 is used once we have presented the algorithm. In fact, a relaxed version of it would be enough, but that would unnecessarily com- plicate the algorithm. We relax the assumption later, when reviewing the Fast Paxos protocol in Section 2.3.2, from which point on all algorithms will assume the relaxed version. Before presenting B -Consensus and R -Consensus, respectively in Sections 2.2.2 and 2.2.3, we describe Weak Ordering Oracles and, more specifically, the WAB ab- straction used in both algorithms. 2.2.1 Weak Atomic Broadcast‌ ∈ Weak ordering oracles [Xxxxxx et al., 2002b] provide best-effort message ordering guarantees, that is, they try to deliver messages in some total order to all processes but cannot be trusted to always perform this task. A WAB, or Weak Atomic Broad- cast, is a weak ordering oracle defined by the primitives w-broadcast(k , m) and w-deliver(k , m), where k 4 defines a w-broadcast instance and m is a message. The invocation of “w-broadcast(k , m) to S ” broadcasts message m in instance k to the agents in S ; w-deliver(k , m) w-delivers a message m w-broadcast in instance k . WAB satisfies the following property: WAB If agents w-broadcast in an infinite number of instances to the agents in some set S , then for every instance k there is an instance k ’ ≥ k in which Fairness every nonfaulty agent in S w-delivers a message, and Spontaneous Order the first message w-delivered in instance k ’ is the same for every agent that w-delivers a message in k ’. Consider, for example, the use of WAB depicted in Figure 2.1, where w-broadcast and w-deliver are noted as wb and wd, respectively. The two agents depicted by dashed lines w-broadcast messages to the other processes. No agent crashes and no message is lost. In instance 1, message m1 is the first w-delivered by one of the three wd(1,m1) wd(1,m2) wd(2,m4) wd(2,m3) wd(3,m5) wd(3,m6) receivers; the spontaneous order property is clearly not satisfied in this instance. In instance 2, however, the first message w-delivered by all receivers is the same, m4, satisfying spontaneous ordering. Last, in instance 3, even though just one message is w-broadcast and spontaneous ordering is attained, not all nonfaulty processes deliver the message. As long as this bad scenario does not happen infinitely often in the subsequent instances, the WAB properties may still be satisfied. wb(1,m1) wb(2,m3) wb(3,m5) wb(1,m2) wb(2,m4) wb(...