A Distributed Coordination Protocol for Multiple Peer Processes

In this paper, we discuss a fully distributed unstructured P2P system where there is no centralized coordinator. Each process makes by itself a decision on an agreement value to realize some objectives by communicating with other processes in a group. Each process first takes a value v in a domain Di which is a collection of possible values and notifies the other processes of the value v. A process in turn receives values from other processes. Unless a set of the values satisfy an agreement condition, a process can take an other value v¹, differently from the traditional consensus protocols. In human societies, people change their opinions in an agreement procedure. Types of precedent relations on values are discussed to show which value to be taken after a value v₁ is taken. An existentially precedent relation (v₁ rarr V₂) shows a process pi can take a value v₂ after taking v₁. In addition, values are ordered in the preferentially precedent relation (rarr^P). A history of a process pi is a sequence of values which pi has taken. Some value may not be taken multiple times. Each value is characterized in terms of the maximum number of occurrences in a history. If a process pi finds some mistake on selecting a value at a previous round, the process would like to roll back to the previous round. A process takes a checkpoint at a round. The process pi can roll back to the checkpoint most recently taken. In this paper, we discuss the checkpoint mechanism in the coordination protocol. Based on the precedent relations and checkpoints, each process takes the most preferable value v¹ in the values which are changeable from current value v.