ADDING INTRA-GROUP RECONFIGURATION. Although reconfiguration happens less often in Ba- sicMCF than in the original CFPaxos, it may still happen if coordinators inside groups are unreliable. We now dis- cuss how to extend BasicMCF in such a way that, in cer- tain situations, failures are handled inside groups without changing rounds. This extended algorithm, that we call ExtendedMCF, makes two extra assumptions. The first assumption is that messages may be ad- dressed to the coordinators inside a group obliviously to the group’s actual membership. In practice, this feature is available through multicast protocols such as IP multi- cast. In IP multicast, processes subscribe to a group by registering at the closest multicast router. The router then informs other routers that it has subscribers for the group, but does not have to inform which or how many. The sec- ond assumption is that the coordinators of a group have access to a consensus oracle running inside that group. In general lines, the idea in ExtendedMCF is that inter-group message exchange addresses all coordinators of a group instead of specific ones. Inside each group, agents agree on exactly which coordinators should actu- ally form coord-quorums for the group. As the proto- col proceeds, the selected coordinators may be replaced to cope with alleged failures, as long as care is taken to avoid inconsistent decisions. That is, if a mapping from the group to some value has been possibly learned, the group can only confirm the value; they cannot propose another. Acceptors and learners, which receive messages from the coordinators, can be informed on-the-fly about the composition of coord-quorums. To allow them to dis- tinct different coord-quorum versions for the same round, coordinators add a version number to their messages; ac- 2B Propose 1A 1B 2A 2S 2A 2A Learners G1 Acceptors G2 G3 Figure 3. A sample BasicMCF round; some messages have been omitted and acceptors are depicted outside their groups for clarity. After the round coordinator in G1 starts the round, two values from proposers in G1 and G2 are decided; the more proposals, the less the amortized the cost of each decision. ceptors and learners only consider the messages with the highest version numbers. The following paragraphs de- tails these procedures. When the leader starts the second phase of a round i, it multicasts the “2S” message to the coordinators of each group containing coordquorums. When the coordinators of some group G hear about round i, by receiving the res...
