Fast Rounds in Spite of Collisions. Guaran- teeing that proposals do not conflict is exactly what the Collision-Fast Paxos protocol [37] does to ensure that, in the absence of failures and message loss, agents reach agreement and learn the decision in two communication steps. In Collision-Fast Paxos, CFPaxos for short, agents agree not on a single value but on a mapping from each proposer to its proposed value, allowing the protocol to void any conflicts since each proposal is mapped from a different proposer. If commands are not commutable, then once the mapping is learned, a deterministic func- tion may be applied to transform it into a sequence. An- other very interesting aspect of CFPaxos is that, in the absence of failures, the more parallel proposals there are, the smaller the relative cost for each one to be learned because all proposals are learned in parallel. By combining CFPaxos and the multicoordinated fast rounds presented in the previous section we get a round type that is perfectly suited for reaching agreement in networks of groups. In Section 5 we introduce two of such combined protocols, a basic and an optimized ver- sion. To simplify the presentation of our protocols, we first overview the CFPaxos protocol, in the following sec- tion.
