A Backward Algorithm in a Distributed Agreement Computing
Ailixier Aikebaier, Tomoya Enokido, Makoto Takizawa · 2008
In traditional agreement protocols, multiple processes just aim at agreeing on one value out of values shown by the processes. In meetings of human societies, agreement procedures are often used and are so flexible that persons can change their opinions and can use various types of agreement conditions like majority-condition. We discuss a flexible agreement protocol of multiple peers by taking into account human behaviors in social agreement procedures in a fully unstructured peer-to-peer (P2P) model. We define a recoverable cut which is a satisfiable set of previous values which every peer can back. We discuss constraints on values which each peer can take at each round and a backward algorithm to find a satisfiable cut. If each peer takes a previous value in a recoverable cut, the peer can make an agreement. We discuss a protocol for multiple peers to find a recoverable cut.