Making an Agreement in an Order-Heterogeneous Group by using a Distributed Coordination Protocol

摘要

In peer-to-peer (P2P) applications, multiple peer processes are required to cooperate to make a global decision. In this paper, every process is assumed to be peer and autonomous, i.e. no centralized coordination. A domain of a process is a collection of possible values which the process can take. Each process first takes a value v in its domain and notifies the other processes of the value v. A process can take another value obtained from the values received from other processes. For example, a process may abort after notifying commit but cannot commit after notifying abort in the commitment control. An existentially (E)-precedent relation shows what values a process can take after taking a value. In addition, a process takes a more preferable value if the process can take one of multiple values. Thus, values are ordered in the preferentially (P)-precedent relation. Based on the precedent relations, each process takes the most preferable one in the values which can be changed from the current value v. In this paper, we discuss a coordination protocol in a type of heterogeneous system where every pair of processes have different precedent relations on the same domain. Each process learns a part of the precedent relation of another process through exchanging values.