Reliable and Efficient Agreement Protocol in Fully Distributed Systems

In various types of peer-to-peer (P2P) applications, peers have to efficiently and flexibly make an agreement on one value which satisfies an agreement condition. In traditional agreement protocols, each peer sends one value to the other peers at each round. If each peer could not make an agreement on the values, the peer sends another value to the other peers at next round. Depending on the order of values shown by each peer, the peers might not make an agreement even if there are values on which every peer can make an agreement but which are shown at different rounds. In order to efficiently make an agreement, we discuss a novel approach that each peer sends a package of multiple possible values to the other peers at each round. Then, each peer tries to find agreement values in the packages. Each peer can deliver values to the other peers at one round. Furthermore, each peer can find an agreement values with higher possibility. By taking into account the multi-value exchange scheme, we can reduce the overhead of the agreement protocol, therefore increase the efficiency of the protocol.