Efficiently Making Agreement among Peer Processes by Using Recoverable Cuts

In peer-to-peer (P2P) applications, peers exchange their opinions with each other and make an agreement on one opinion. Agreement procedures have to be so flexible that persons can change their opinions, withdraw previous opinions under some constraints on the opinions, and use various types of agreement conditions like majority-condition in our society. We discuss a flexible agreement protocol of multiple peers by taking into account human behaviors in a fully unstructured peer-to-peer (P2P) system model. Each peer first notifies the other peers of its value. The peer in turn receives values from other peers. Unless the values satisfy the agreement condition, the peer can take another value. This is the forward strategy to make an agreement. In addition, we discuss other strategies, backward, mining, and observation ones in this paper. In the backward strategy, a peer backs to a previous round where the peer can take another value from previous values. In the mining one, a peer tries to find a tuple of previous values named a cut which satisfies the agreement condition. In the observation one, a peer does not take a new value and keeps the previous value. Each peer autonomously takes one of the strategies at each round. We discuss how peers cooperate to take one strategy at each round.