Fast Paxos. Fast Paxos [37] involves two types of execution modes: a classic and a fast mode, that cor- respond to classic and respectively fast rounds. The classic mode functions just the same as Classic Paxos. In [37], there exists a static a priori agreement between the participants, regard- ing the round numbers that will be executed in the fast mode. → → → This second strategy, presented by Xxxxxxx in a protocol called Fast Paxos (with a blank) [37], tries to take advantage from a low throughput of the flow of initial values pro- vided by the proposers. It aims at reducing the number of communication steps to three (proposer acceptors leader xxxxxxx), in favorable circumstances. If the most recent consensus instance has been completed for a long time, instead of being idle, the current leader can anticipate some part of the computation for the next consensus instance. The leader prepares the next consensus instance by sending a special value, called an Any value, to the acceptors. Once an acceptor receives it, it knows it is allowed to adopt a value directly provided by a proposer, which sends an initial value to both acceptors and coordinators. This is also called a fast round. In favorable circumstances, a gain can be obtained: if all pro- posers provide the same initial value, as such an initial value does not pass in transit through C1 A1 A2 C2 L the leader and therefore the decision latency is reduced. These communication steps are de- scribed in Figure 3.5. Decide v wait for a larger quorum Any v v v P1 Ak P2
Fast Paxos. Unlike Paxos, in Fast Paxos [37], the values adopted by the acceptors during a round r are not necessarily equal. Different proposers may provide different values. These proposal messages may be received in different orders by different acceptors. In such cases, a collision may occur. Consequently, a more restrictive definition of quorums has to be used to assess the successful termination of either a Read or a Write operation. As indicated by Xxxxxxx [9], majority quorums have to be replaced by larger quorums called herein Any quorums. As an Any quorum is larger, the maximal number of failures f that are tolerated has to be lower. Moreover, these larger quorums are more difficult to obtain as they require to collect more replies from the acceptors. In [37], Xxxxxxx defines quorums as sets of processes (acceptors). Each round has a set of quorums associated with it. Classic rounds use classic quorums while fast rounds rely on fast quorums. These sets of acceptors must satisfy some given properties called Quorum Requirements. These properties state that (1) any two quorums must have a nonempty in- tersection and (2) any quorum and any two fast quorums from the same round must also have a nonempty intersection. More formally, the Fast Quorum Requirement states that for any rounds i and j: Let an i-quorum denote the quorum of acceptors used during round i. - if Q is an i-quorum and R is a j-quorum, then Q ∩ R ̸= ∅. - if Q is an i-quorum, R and S are j-quorums and j is a fast round, then Q ∩ R ∩ S ̸= ∅. Based on these requirements, Xxxxxxx has defined in [37], the minimum number of acceptors that can constitute a quorum. Let us assume that N is the total number of acceptors that are in the system. The cardinality of any classic quorum, Qc, and of any fast quorum, Qa, can be computed as follows: | | ≥ ⌊ ⌋ ≥ ⌈ ⌉| | Qc N/2 + 1, Qa 3N/4 . The same requirements for quorums cardinalities are also obtained in [55]. C2 C1 wait for a larger quorum Conflicting Proposals No value to decide A1 Any v A2 v1 v2 Ak P1 P2
