Multicoordinated Fast Rounds. Consider the price of solving standard consensus in a network of groups using a leader based protocol such as Paxos. Let Gl be the group to which the leader belongs. Because the protocol is so dependent on the leader, it has the follow- ing clear drawbacks: (i) agents in Gm , m = l , must mon- itor the leader through intergroup links; (ii) in the case of a leader failure, the reconfiguration takes two intergroup delays, plus the time to detect the failure; and, (iii) while for every agent in Gl the time between proposal and deci- sion is of two intergroup delays in good runs, for any other agent not in Gl the latency is of at least three intergroup delays. Using the multicoordinated approach that we have described in the previous sections with all coordinators within Gl will minimize the effects of the first two draw- backs. That is, failure detection may be less aggressive since rounds are more resilient and it is unlikely that rounds will need to be changed due to conflicts, since groups are probably within a single area network where messages tend to be ordered spontaneously and collisions are more unlikely. Multicoordination, however, does not help with the third drawback. To allow a two-step latency from any group of agents, fast rounds would be more appropriate, but they have their own drawbacks: collisions of proposals and, by conse- quence, larger acceptor quorums and, therefore, lesser re- siliency and more messages crossing the boundaries of groups. To minimize the number of messages exchanged, one agent may be selected from each group to aggregate the groups’ proposals and forward them to the acceptors instead of letting every agent propose in every fast round. Such a fast round with aggregation is, in fact, a multicoor- dinated round in which each agent aggregating proposals is a coordquorum. Observe however that this multicoor- dinated fast round does not satisfy the coordquorum re- quirement (Assumption 3). When comparing single-coordinated and fast rounds, we see that we either need to ensure that a single value is proposed or we allow conflicting values be proposed but require Assumption 4 be true and more acceptors be avail- able. The same holds true for multicoordinated classic and multicoordinated fast rounds, as the one described in the previous paragraphs of this section. That is, we either enforce that only a single proposal per round can possibly be accepted by satisfying the coordquorum requirement or we relax this requirement and s...
