半順序ドメインを用いた一般合意プロトコル

概要

論文の詳細を見る
In distributed applications like groupware, a group of multiple processes cooperate to realize some objective. The processes have to make consensus in order to do the cooperation. The processes achieve consensus if they take a value which satisfies a consensus condition by exchanging values with each other. Only two values, i.e. 1 (commit) and 0 (abort) can be taken in the in the two-phase commitment (2PC) protocol. In the 2PC protocol, the process taking 1 can take 1 or 0 although the process taking 0 can only take 0. Hence, we name it a binary commitment. After notifying other processes of 1, the process is uncertain where the processes have to wait for the decision of the coordinator process. Here, the process may block if the coordinator is faulty. In more general consensus protocols, the processes may take more kinds of values. After taking some value v, the process can take one value which depends on v. Takizawa el. al. discuss a dominant relation ⪯ in which the domain D is partially ordered. That is, a value v_1 in D dominates v_2 (v_1 ⪯ v_2) if the process can take v_2 after taking v_1. There are two kinds of groups, i.e. homogeneous and heterogeneous. In the homogeneous group, one dominant relation holds for all the processes. In the heterogeneous group, a dominant relation is defined for each process. That is, even if one process takes a value v' after taking v, another process right not take v' after v. Each process has to learn the dominant relations of other processes by obtaining the values taken by the processes. In this paper, we discuss a general consensus protocol with the ordered domain composed of multiple values v_1, ..., v_m. The protocol is obtained by extending the 2PC protocol.
一般社団法人情報処理学会の論文
1997-09-24

半順序ドメインを用いた一般合意プロトコル

スポンサーリンク

概要

著者

関連論文

スポンサーリンク