Precedent relations

Chapter 3

v₁ →^Ei v₂ norv₂ →^Ei v₁, i.e. the peer p_i is allowed to take any value ofv₁ and v₂ after taking the valuev. Here, the peerp_i has to take one of the valuesv₁ and v₃. For example, if a peerpi prefers a valuev₁ to another valuev₂(v₂→^Pi v₁), the peer p_i would like to take the value v₁. It is noted that the peer p_i may take the valuev₂even if the valuev₁ is more preferable than the valuev₂.

The precedent relations→^Ei and→^Pi with the domainDi are assumed to be a priori specified when each peer p_i is initiated. In a homogeneous system, every peerp_i has the same relations→^Ei and→^Pi on the same domainD_i. In a hetero-geneous system, some pair of peersp_i andp_j have different relations→^Ei =→^Ej

or→^Pi =→^Pj on different domains,D_i =D_j.

There are the following relations between a pair of values v₁ and v₂ in the domainD_i of a peerp_i:

1. v₁is E-equivalent withv₂ inpi(v₁ ≡^Ei v₂)iffv₁ →^Ei v₂ andv₂ →^Ei v₁. 2. v₂is more E-significant thanv₁inp_i(v₁ ≺^Ei v₂)iffv₁ →^Ei v₂butv₂ →^Ei v₁. 3. v₁E-dominatesv₂inp_i(v₁ ^Ei v₂)iffv₁ ≺^Ei v₂orv₁ ≡^Ei v₂.

4. v₁ is E-incomparable with v₂ in p_i (v₁ |^Ei v₂) iff neither v₁ →^Ei v₂ nor v₂ →^Ei v₁.

5. v₁is P-equivalent withv₂ inpi(v₁ ≡^Pi v₂) iffv₁ →^Pi v₂ andv₂ →^Pi v₁. 6. v₁is more P-significant thanv₂inp_i(v₂ ≺^Pi v₁) iffv₁ →^Pi v₂butv₂ →^Pi v₁. 7. v₁P-dominatesv₂inp_i(v₂ ^P_i v₁) iffv₂ ≺^P_i v₁andv₂ ≡^P_i v₁.

8. v₁ and v₂ are P-incomparable in pi (v₁ |^Pi v₂) iff neither v₁ →^Pi v₂ nor v₂ →^Pi v₁.

A valuev₁ is referred to as maximal and minimal iff there is no valuev₂ such thatv₁ →^Ei v₂andv₂ →^Ei v₁in the domainD_i, respectively. For example, abort is maximal and commit is minimal in the commitment protocol. If a peer pi takes a maximal valuev in the domainD_i, the peerp_i cannot take any new value. On the other hand, a peerp_i can take a value after taking a minimal value in the domain Di. A valuev₁is referred to as top iffv₂ →^Ei v₁ for every valuev₂inDi. A value v₁ is referred to as bottom iff v₁ →^Ei v₂ for every valuev₂ in D_i. Let Corn_i(x) be a set of values which a peerp_i can take after taking a valuexin a domainD_i, Corni(x) ={y|x→^Ei y} ⊆Di. If a valuexis maximal,Corni(x) =φ. If there

are multiple values which a peerp_i can take after a value x, i.e. |Corn_i(x)| ≥2, the valuexis referred to as branchable in the domainD_i.

A least upper bound (lub) of valuesv₁ andv₂ (v₁ ^Ei v₂) is a valuev₃ in the domain D_i such that v₁ →^Ei v₃, v₂ →^Ei v₃, and there is no value v₄ such that v₁ →^Ei v₄ →^Ei v₃ and v₂ →^Ei v₄ →^Ei v₃ in a peer p_i. For example a peer p_i takes a value vi and another peer pj takes a value vj at round t. If →^Ei = →^Ej , the peer p_i and p_j can take v_i ^Ei v_j to make an agreement. A greatest lower bound (glb) of valuesv₁ and v₂ (v₁ ^Ei v₂) is a value v₃ in the domain D_i such thatv₃ →^Ei v₁,v₃ →^Ei v₂, and there is no valuev₄ such thatv₃ →^Ei v₄ →^Ei v₁and v₃ →^Ei v₄ →^Ei v₂. A least upper bound (lub)^Pi and greatest lower bound (glb) ^Pi are defined for the P-dominant relation→^Pi in the same way as^Ei and^Ei .

3.1.1 E-precedent relation

A system S is composed of n (≥ 1) peer processes p₁, . . . , p_n. A domain D_i of a process p_i is a set of possible values which the process p_i can take. Each processp_i initially takes a value v⁰_i in the domainD_i and notifies the other pro-cesses of the value v_i⁰. A process p_i receives a value v_j⁰ from every other pro-cess p_j (j = 1, . . . , n). The process p_i takes another value v¹_i from a tuple v₁⁰, . . . , v_n⁰. This is the first round. Then, the processp_i notifies the other pro-cesses of the valuev_i¹. Thus, at thet^th round, the processpi collects a tuplev^t−1

=v^t₁⁻¹, . . . , v^t_i⁻¹, . . . , v^t_n⁻¹wherep_itakes a valuev^t_i⁻¹ and receives a valuev_j^t−1 from each other processp_j (j=i). Ifv^t−1 satisfies the agreement conditionAC_i, the processpiobtains one valuevfromv^t−1as an agreement value and terminates.

Otherwise,p_itakes a valuev_i^tin the domainD_iand notifies the other processes of v_i^t. Here,p_ichanges the opinion from the valuev_i^t−1 tov_i^t. Here,v⁰_i, . . . , v_i^t−1 are referred to as previous values andv_i^tis a current value.

In the commitment protocols [47, 54], a process which notifies commit may abort if the coordinator process indicates abort to the process after receiving the values from the processes. Here, a process which notifies abort cannot take com-mit. Each processp_ican take a valuev_i^tafter taking a valuev_i^t−1in the domainD_i at round t ifp_i can changev_i^t−1 tov_i^t. Here,p_i changes the opinion fromv^t_i⁻¹ to v_i^t. Ifpi cannot take any value fromv^t_i⁻¹,pistill takes the valuev_i^t−1as the current value v^t_i or backs to the previous valuev_i^t−2 and tries to take another value from v_i^t−2.

[Definition] A valuev₁ is referred to as existentially (E) precede a valuev₂ with respect to a process p_i (v₁ →^Ei v₂) if and only if (iff ) the processp_i can take v₁ after takingv₂ in the domainD_i(→^E_i ⊆D_i²).

We assume the relation→^Ei to be transitive. A valuev₁ is E-equivalent with a valuev₂ in a processp_i (v₁ ≡^Ei v₂)iffv₁ →^Ei v₂ andv₂ →^Ei v₁. A valuev₁ is E-uncomparable with a value v₂ in a processpi (v₁ |^Ei v₂) iff neitherv₁ →^Ei v₂ norv₂ →^Ei v₁. A valuev₁ E-dominates a valuev₂ inp_i (v₁ ≺^Ei v₂)iffv₁ →^Ei v₂ butv₂ →^Ei v₁. v₁ ^Ei v₂ iffv₁ ≺^Ei v₂ orv₁ ≡^Ei v₂. In the commitment protocol, commit →^Ei abort but abort →^Ei commit for every process pi as presented here.

Hence, commit≺^Ei abort.

For every pair of valuesv₁ and v₂, v₁ E-precedes v₂ (v₁ →^E v₂), v₁ is E-equivalent with v₂ (v₁ ≡^E v₂), v₂ is more E-significant than v₁ (v₁ ≺^E v₂), v₂ E-dominates v₁ (v₁ ^E v₂), and v₁ is E-uncomparable with v₂ (v₁ |^E v₂) iff v₁ →^Ei v₂, v₁ ≡^Ei v₂, v₁ ≺^Ei v₂, v₁ ^Ei v₂, and v₁ |^Ei v₂ for every process p_i, respectively.

A processp_i can take a value v₂ after taking another value v₁ ifv₁ →^Ei v₂. Here, suppose that the processp_i had takenv₂ beforev₁. Question is whether or notp_ican take again a value whichp_i has previously taken.

[Definition] A valuev₁ acyclically E-precedes (AE-precedes) a valuev₂in a pro-cessp_i(v₁ ⇒^Ei v₂) iffp_ican takev₂after takingv₁andp_ihad previously not taken v₂.

A least upper bound (lub) of valuesv₁ andv₂ (v₁ ^Ei v₂) is a valuev₃ in the domain D_i such that v₁ →^Ei v₃, v₂ →^Ei v₃, and there is no value v₄ such that v₁ →^Ei v₄ →^Ei v₃ andv₂ →^Ei v₄ →^Ei v₃. Suppose there are a pair of processes p₁ and p₂ notifying one another of values v₁ and v₂, respectively. Suppose the processesp₁ andp₂ have the same E-precedent relation,→^E₁ =→^E₂ =→^E on the same domain D, D₁ = D₂ = D. Here, ^E₁ = ^E₂ = ^E and ^E₁ = ^E₂ = ^E. If there exists an lubv₃ =v₁ ^E v₂, bothp₁ andp₂ can takev₃ after taking v₁ and v₂, respectively. A greatest lower bound (glb) of valuesv₁ andv₂ (v₁ ^Ei v₂)is a value v₃ in Di such that v₃ →^Ei v₁, v₃ →^Ei v₂, and there is no value v₄ such thatv₃ →^Ei v₄ →^Ei v₁ and v₃ →^Ei v₄ →^Ei v₂. The processesp₁ and p₂ can also take the glbv₄=v₁^Ev₂as an agreement value if the processes can take previous values again. In this paper, there exist a pair of special values, bottom value ⊥^Ei

and top value ^Ei where⊥^Ei →^Ei v andv →^Ei ^Ei for every valuev inD_i. This means that a processp_i can take any value inD_i after taking the bottom⊥^Ei . On the other hand,pi taking the top^Ei cannot change the value. In the commitment protocol [42, 43, 44], each processp_i has a binary domainD_i ={abort,commit} where commit →^E_i abort. Here, abort is the top ^E_i and commit is the bottom

⊥^Ei . The value abort E-dominates commit (commit≺^Ei abort).

[Definition] Let →^Ei and →^Ej be E-precedent relations of processes p_i and p_j, respectively. A pair of precedent relations→^E_i and→^E_j are existentially (E)

con-sistent (→^Ei ∼=^E →^Ej) iff for every pair of valuesv₁ andv₂ inD_i ∩D_j, v₁ →^Ei v₂ iffv₁ →^Ej v₂.

A pair of E-precedent relations→^E_i and→^E_j are E-inconsistent (→i ∼=^E →j) iff→^Ei and→^Ej are not consistent. Let us consider a pair of processes p₁ andp₂. Here,D₁ ={a, b, c}andD₂={a, b, d, e}. In the processp₁, a→^E₁ b and a→^E₁ c. In the process p₂, a→^E₂ b→^E₂ d and b→^E₂ e. Here, →^E₁ =→^E₂ but→^E₁ and

→^E₂ are E-consistent (→^E₁ ∼= →^E₂) since D₁ ∩ D₂ = {a, b }and a →^E₁ b and a

→^E₂ b. Another processp₃has a domainD₃={a, b, e}where b→^E₃ a. Here, the E-precedent relation→^E₃ is not E-consistent with→^E₁ (→^E₃ ∼=→^E₁) since a→^E₁ b but b→^E₃ a forD₁ ∩D₃ ={a, b}.

In the E-precedent relation→^Ei (⊆ D²_i), a processp_i makes a decision on a value v₂ which p_i notifies to the other processes depending on a value v₁ most recently taken. That is, p_i takes a valuev₂ where v₁ →^Ei v₂. LetN ext^E_i (v₁)be {v₂ | v₁ →^Ei v₂}of values whichp_i can take next from a valuev₁. For example, N ext^E_i (commit) ={commit, abort}andN ext^E_i (abort) ={abort}.

3.1.2 P-precedent relation

Suppose a processp_i can take a pair of valuesv₁ andv₂ after taking a valuev₃ in the E-dominant relation →^Ei , i.e. v₃ →^Ei v₁ andv₃ →^Ei v₂. Here, the processpi

has to take one of the valuesv₁andv₃. Ifp_iprefersv₁tov₂(v₂→^Pi v₁),p_ican first take v₁. A partially ordered relation →^P_i ⊆D_i² is a preferentially (P) precedent relation on the domainDi.

[Definition] A value v₁ P-precedes a valuev₂ in a processp_i (v₁ →^Pi v₂) iff p_i prefersv₁ tov₂.

A value v₁ is P-equivalent with a value v₂ in a process p_i (v₁ ≡^Pi v₂) iff v₁ →^Pi v₂ andv₂ →^Pi v₁. v₁ is more P-significant than v₂ in p_i (v₂ ≺^Pi v₁) iff v₁ →^P_i v₂ butv₂ →^P_i v₁. v₁ P-dominatesv₂ inp_i (v₂ ^P_i v₁) iff v₂ ≺^P_i v₁ and v₂ ≡^Pi v₁. A pair of values v₁ and v₂ are P-uncomparable in p_i (v₁ |^Pi v₂) iff neither v₁ →^Pi v₂ norv₂ →^Pi v₁. In addition, v₁ →^P v₂, v₁ ≡^P v₂, v₁ ≺^P v₂, v₁ ^P v₂, andv₁ |^E v₂iffv₁ →^P_i v₂,v₁ ≡^P_i v₂,v₁ ≺^P_i v₂,v₁ ^P_i v₂, andv₁ |^E_i v₂ for every processp_i, respectively.

The least upper bound^Pi and greatest lower bound ^Pi are defined for the P-dominant relation→^Pi in the same way as^Ei and^Ei . There are special values, top^Pi and bottom ⊥^Pi with respect to the P-precedent relation→^Pi in the same way as the E-precedent relation→^Ei . We assume the P-precedent relation→^Pi is transitive.