A history of a peer

3.3.1 History

Each peer pi takes a value while exchanging values with the other peers at each round as discussed in the basic coordination protocol. A historyH_i^tof a peerp_iis a collection of local historiesH_i^t₁, . . ., H_in^t at roundt. A local historyH_ii^t is a sequencev_i⁰, v_i¹, . . . , v^t_i⁻¹of values which a peerpihas taken until roundtfrom the initial round 0. A local historyH_ij^t is a sequence of valuesv_j⁰, v_j¹, . . . , v_j^t−1 which a peer p_i has received from another peer p_j until round t (j = 1, . . . n, i=j). Here,H_ij^t =H_jj^t since we assume the network and every peer to be reliable and every peer surely receives every value sent in the sending order by another peer. Initially,H_ij⁰ = φ (j = 1, . . . n). A notationH_ij^t|u shows a valuev_j^u which a peer p_i receives from a peer p_j at round u (u ≤ t). H_ii^t|u shows a value v_i^u which the peerp_i takes at the roundu. Suppose a peer p_i receives values a, b, c, d, and e at rounds 0, 1, 2, 3, and 4, respectively from another peerp_j. Here,H_ij⁵ = a, b, c, d, e. H_ij⁵|2=c.

LetH be a sequencex₁, . . . , x_m(m≥ 1) of values. Here, a valuex_l is re-ferred to as precede another value x_h (x_l ⇒ x_h) ifl < hin the sequence H. A notation “H +x” shows a sequencex₁, . . . , xm, xof values obtained by adding a value x to the sequence H. A subsequence x₁, . . . , x_l (l ≤ m) is a prefix of the sequence H. A subsequence x_k, . . . , x_m (1 < k) is a postfix of the se-quence H. For example, let H be a sequence a, b, c, d, e of values. A pair of subsequences a, b, c, d and c, d, e are a prefix and postfix of the sequence H, respectively. H + y₁, . . . , y_l = ((. . . ((H + y₁) + y₂) . . . ) + y_l−1) + y_l = x₁, . . . , xm, y₁, . . . , yl. “H -xl” gives a prefixx₁, . . . , xl−1of a sequenceH = x₁, . . . , x_l. H -x_l, . . . , x_m= (. . . ((H -x_m) -x_m−1) . . .) - x_l for a sequence H = x₁, . . . , x_mandl ≤ m. For example, H +f, a=a, b, c, d, e, f, αand H -d, e=a, b, c

A value x may occur multiple times in a sequence H of values. Let H_ij^t[x] show a subsequence x, . . . , x of instances of a value x in a local historyH_ij^t.

|H_ij^t[x]|is the number of instances of a valuexin a local historyH_ij^t. For example,

letH_ij⁷ be a sequencea, b, x, c, d, x, e, fof values.H_ij⁷[x]=x, x,H_ij⁷[c]=c,

|H_ij⁷[x]|= 2, and|H_ij⁷[c]|= 1.

A peerp_i takes a current valuev_i^t after obtaining a tuplev₁^t−1, . . . , v_n^t−1 of values from the other peersp₁, ...,p_n, respectively, at roundt. Letc^t_iiindicate the current valuev^t_i. Then, the peerpi sends the valuev_i^tand receives a valuev_j^tfrom another peerp_j. Letc^t_ij be a valuev_j^t which the peerp_i receives from the peer p_j at roundt. At roundt+ 1, the local historyH_ij^t+1 of a peerpi is obtained asH_ij^t + c^t_ij (=v_j^t) =v_j⁰, v_j¹, . . . , v_j^t−1, v^t_j(j=1, . . . , n).

For a pair of valuesv₁ and v₂ in a local history H_ij^t, v₁ precedes v₂ (v₁ ⇒j

v₂) if a peerp_i receives the value v₂ after the value v₁ from a peerp_j (j = 1, . . ., n). Suppose there are a pair of valuesv₁ andv₂ in a local historyH_ij^t. If a pair of valuesv₁ andv₂are in the local historyH_ij^t and the valuev₁E-precedes the value v₂ in a peer p_j (v₁ →^Ej v₂), the valuev₁ precedes the valuev₂ (v₁ ⇒j v₂) in the local historyH_ij^t. However, even ifv₁ →^Pj v₂, v₂ ⇒j v₁ might hold in the local historyH_ij^t. A peerp_j may take a less preferable value at some round.

3.3.2 Methods on a history

A peerpi takes a value and receives values based on the historyH_i^tat each round t. LetD_i^∗ show a set of possible sequences of values obtained from the domain D_i. Here,H_ii^t ∈D_i^∗for every local historyH_ii^t.

We introduce the following coordination methods on the historyH_i^t [Figure 3.7]:

1. forward:D_i^∗→D_i^∗. For a sequenceH₁inD_i^∗,H₁is a prefix of forward(H₁).

2. compensate: D^∗_i → D_i^∗. For a sequence H₁ in D_i^∗, compensate(H₁) is a prefix ofH₁.

3. null:D_i^∗→D_i^∗. For a sequenceH₁ inD^∗_i, null(H₁) =H₁.

LetH₁ be a sequence v₁, . . . , v_m of values. forward(H₁) = v₁, . . . , v_m, v_m+1, . . . , v_l. In the forward method, a sequencev_m+1, . . . , v_lis added to the sequenceH₁, i.e. H₁+v_m+1, . . . , v_l. compensate(H₁) gives a prefixv₁, . . . , v_k (k ≤ m) of the sequenceH₁. This means, a peerp_i backs to the previous state

null: compensate^:

forward: 1 m 1

1

m+1 l

k

m

k 1

m

1

1 m

Figure 3.7: History methods.

with a historyH₂by withdrawing the valuesv_k+1, . . . , v_m. In the null method, no new value is taken at roundt, null (H₁) =H₁.

Each peerp_i takes one of the coordination methods at each round as shown in Figure 3.8. If a peerp_i takes the forward method, the peerp_i selects a new value v_i^t at round t as presented in the basic coordination procedure. In the forward method, a value v is taken and added to the history H₁, i.e. v₁, . . . , v_m, v. If a peerp_itakes the null method, the peerp_idoes not select a new value at roundt. If a peerp_itakes the compensate method, the peerp_ibacks to a previous roundk+1 where values taken from the roundk+ 1to the present round are withdrawn.

: agreement condition.

forward null compensate

true

history methods

agreement

Figure 3.8: Coordination procedure of a peer.

3.3.3 Compensation

A peerp_ican back to the previous rounduby compensating a historyH_i^tat current round t (u < t). In some meeting of multiple persons, there may be some rule that each person can withdraw his remark but cannot withdraw a special remark

“no”. Thus, there is some valuevwhich a person cannot withdraw after the person shows the valuevto others. A valuexis referred to as primarily uncompensatable in a peer p_i iff the peerp_i cannot withdraw the valuexafter showing the valuex to the other peers, i.e. the valuexcannot be withdrawn in the history. Otherwise, a value is primarily compensatable in a peer pi. Let us consider a local history H_ii⁴ = a, b, c, d, eof a peerp_i. Suppose a valuecis primarily uncompensatable and the other values are primarily compensatable in the peer p_i. Here, the values dandecan be compensated but the valueccannot be compensated. Although the values a and b are primarily compensatable, neither the value a nor the value b can be withdrawn because the valuecpreceded by the values aandbin the local historyH_ii⁴ is primarily uncompensatable.

[Definition] In a local historyH_ii^t =v_i⁰,. . .,v_i^u−1,. . .,v^t_i⁻¹of a peerp_i, a value v_i^u−1is referred to as uncompensatable iff the valuev^u_i⁻¹is primarily uncompen-satable or some valuev_i(v_i^u−1 ⇒v_i) preceded by the valuev^u_i⁻¹is uncompensat-able. A valueu^u_i⁻¹ is compensatable iffv_i^u−1 is not uncompensatable in the local historyH_ii^t.

A sequencev⁰_i, v¹_i, . . . , v_i^t−1 is referred to as uncompensatable iff the value v_i^t−1 is primarily uncompensatable or the subsequence v⁰_i, . . . , v_i^t−2 is uncom-pensatable. A peerp_i cannot back to the previous round uat roundt (u < t) if a valuev^s_i (u < s < t) is uncompensatable in the local historyH_ii^t.

In the example, the local historyH_ii⁴ = a, b, c, d, e is uncompensatable, be-cause the valuecis primarily uncompensatable. The subsequenced, eis com-pensatable. In a local historyH_ii^t =v_i⁰, v_i¹, . . . , v_i^t−1, an uncompensatable value v_i^uis a most recently uncompensatable value iff a subsequencev_i^u+1, . . . , v_i^t−1is compensatable as shown in Figure 3.9. A compensatable postfixv_i^u+1, . . . , v_i^t−1 is referred to as maximally compensatable subsequence of a local history H_ii^t = v_i⁰, v_i¹, . . . , v_i^t−1iff a prefixv_i⁰, v¹_i, . . . , v_i^uis uncompensatable. In the local his-toryH_ii⁴ =a, b, c, d, e, the valuecis the most recently uncompensatable value. A postfixd, eis the maximally compensatable subsequence of H_ii⁴. A postfixe is compensatable but not maximally compensatable.

At roundt, a peer p_i takes a valuev^t_i from the tuple v^t₁⁻¹, . . . , v^t_n⁻¹. Here,

compensatable uncompensatable

: most recently uncompensatable value

ii

t

i

1

i u+1

i

t-1

H

Figure 3.9: Most recently uncompensatable sequence.

v_i^t−1 →^Ei v^t_i. Supposev_j^t−1 →^Ei v_i^t, i.e. v_i^t= v^t_i^{−1 E}i v^t_j⁻¹. Suppose the peer p_j withdraws the valuev_j^t−1. If a peerp_j takes another valuev (=v_j^t−1), the peerp_i may take a different value from the valuev_i^tdepending on the valuev. Hence, if the peer p_j compensates the value v_j^t−1, the peer p_i has to compensate the value v_i^t since the peer p_i takes the value v_i^t which is obtained by applying the local decision functionLD_i to the valuev_j^t−1.

[Definition] For each valuev_i^tat roundt, a minimal domainM D(v_i^t) is defined to be a subset of values in the tuplev₁^t−1, . . . , v^t_n⁻¹such thatv_i^t=^E_{i x∈MD(v}t

i)xand v_i^t=^E_{i x∈}MD(v^t_i)−yxfor every valueyinM D(v_i^t).

If any value in M D(v_i^t) is omitted, a least upper bound (lub) of values in M D_i(v_i^t) is not the valuev^t_i. A valuev_i^tis referred to as depend on a valuev_j^t−1in a peerp_i(v_j^t−1 v^t_i) iffv_j^t−1∈M D(v^t_i).

It is straightforward for the following theorem to hold from the definitions.

[Theorem 1] A valuev^t_i is required to be compensated in a peerp_i if at least one value in the minimal domainM D(v_i^t) is compensated.

[Theorem 2] If a value v_i^t is uncompensatable in a peer p_i, every value in the minimal domainM D(v_i^t) is uncompensated.

[Proof] Let v be a value in the minimal domain M D(v^t_i), v i v^t_i. Suppose the valuev is compensated in some peerp_j. The peerp_j might take another valuev (=v) after compensating the valuev. The valuev^t_i might not be the least upper bound ofM D(v_i^t) since the valuevis not inM D(v^t_i).

3.3.4 Constraints on values

In some meeting, there is a rule on how many times each person can say a remark.

For example, each person can say “no” at most once in some meeting. Thus, each valuevin a domainD_iis characterized in terms of the maximum occurrence

M O_i(v). The maximum occurrenceM O_i(v) shows how many times a peerp_ican take in an agreement procedure. If M O_i(v) = 1, a peer p_i can take a value v at most once. If a peerpi had so far taken a valuev or fever times thanM Oi(v), i.e.

|H_ii^t[v]|< M O_i(v), the peerp_i can take a valuev again at roundt. IfM O_i(v) =

∞, a peerp_ican take a valuev as many times as the peerp_iwould like to take.

At roundt, a peerpi takes a valuev_i^tin the forward method on a historyH_i^t. Here, the valuev_i^thas to satisfy the following conditions:

[Conditions of possible values]

1. For every valuexin the local historyH_ii^t,x→^Ei v^t_i. 2. |H_ii^t[v_i^t]|< M O_i(v^t_i).

LetP_i^t(v_i^t−1) show a set of possible values which a peerp_ican take at roundt.

The setP_i^t(v_i^t−1) is defined from the conditions as follows:

P_i^t(v^t_i⁻¹) ={v| |H_ii^t[v]|< M Oi(v) and for every valuexinH_ii^t,v_i^t−1 →^Ei v }.

A value v is not included in the possible value set P_i^t(v_i^t−1) if |H_ii^t [v]| = M O_i(v). Then, the peer p_i takes a value v^t_i in the set P_i^t(v_i^t−1) if P_i^t(v_i^t−1) = φ. Then, the peerp_i sends the valuev_i^tto the other peers. IfP_i^t(v_i^t−1) =φ, there is no value which the peerp_ican take at roundtin the forward method after taking a valuev_i^t−1at roundt- 1. Here the peerp_ihas to take another coordination method, null or compensate. If|P_i^t(v_i^t−1)| ≥2, the valuev_i^t−1 is referred to as branchable at roundt. Even if a valuev^t_i⁻¹is branchable in the domainD_i, i.e.|Corn_i(v_i^t−1)|

≥2, the valuev_i^t−1may be taken in previous rounds of the local historyH_ii^t.