Cuts

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.

[Definition] A cut of a historyH_i^δi is a tuple of valuesv^t₁¹, . . . , v^t_nⁿwheret_j <

δ_j for eachj =1, . . . , n.

A cutv₁^t1, . . . , v^t_nⁿis referred to as current ifftj =δj for every peerpj. A cut v₁^t1, . . . , v^t_nⁿ is referred to as concurrent iff each valuev_i^ti is taken at the same round. A current cut is concurrent.

[Definition] A cutv₁^t1, . . . , v_n^tnof a historyH_i^δi is satisfiable in a peerpi iff the cutv₁^t1, . . . , v_n^tnsatisfies the agreement conditionAC_i.

Since every peerp_i is assumed to have the same agreement conditionAC_i = AC in this paper, a satisfiable cut in some peer is also satisfiable in every peer.

In the coordination protocol presented in the preceding section, a peerp_itakes a forward function, i.e. takes a new value. However, even if the current cut is not satisfiable, there might be a satisfiable cut in a historyH_i^δi. Suppose the current cutv₁^δ1, . . . , v_n^δnis not satisfiable but another cutv₁^t1, . . . , v_n^tnis satisfiable in a historyH_i^δi. Here, if every peerp_i backs to the previous roundt_i+ 1 by compen-sating the local history H_ii^δi (i = 1, . . ., n), all the peers p₁, . . . , p_n can make an agreement on a valuev =GD_i(v₁^t1, . . . , v_n^tn) for the cutv₁^t1, . . . , v_n^tn.

[Definition] Let H_ii^δi be a local history v_i⁰, v¹_i, . . . , v_i^δi−1 of each peer p_i (i = 1, . . . , n). A cutct=v^t₁¹, . . . , v^t_nⁿis obtainable in a peerp_iiff a postfixv_i^ti+1, . . . , v_i^δi−1 of the local historyH_ii^δi is compensatable in the peerp_i.

A peer p_i can back to the previous value v_i^ti if there is an obtainable cut v₁^t1, . . . , v^t_i¹, . . . , v_n^t1. A cutct= v₁^t1, . . . , v_n^tnis obtainable iff the cut ctis ob-tainable in every peer. A cutct=v₁^t1, . . . , v_n^tnis maximally obtainable in a peer p_i iff the cut ctis obtainable in the peer p^t_i, i.e. a postfix v_i^ti+1, . . . , v_i^δi−1 is compensatable, but a postfixv_i^ti, v_i^ti+1, . . . , v_i^δi−1of the local historyH_ii^δi is not compensatable. A cutct=v₁^t1, . . . , v_n^tnis maximally obtainable iff the cut ctis maximally obtainable in every peerp_i.

Letctbe a cutv^t₁¹, . . . , v_n^tn in a historyH_i^δi. The cutctis obtainable if the following conditions hold:

[Obtainability conditions]

1. Letmrujbe the most recently uncompensatable value in a local historyH_ij^δj. A valuev_j^tj in the cutctprecedes the valuemru_j inH_ij^δj (mru_j ⇒v_j^tj).

2. Letv_k mean a value from a peerp_k in the minimal domainM D_j(v_j^tj), i.e.

v^t_j^j depends onv_k(v_k j v^t_j^j). From each valuev_j^tj in the cutct, every value v_kinM D_j(v^t_j^j) precedes a value v_k^tk in the local historyH_ij^δj (v_k ⇒ v_j^tj) as shown in Figure 3.10.

H

_i1

H

_i3

H

_i2

: most recently uncompensatable value.

mru

mru

mru 1

2

3

v₁

v₂

v₃

t₁

t₂

t3

: value in a cut .ct

i

v

v v₁

2

3

ct

1

ct

2

Figure 3.10: Obtainable cut.

Even if a cut ct = v^t₁¹, . . . , v^t_nⁿ satisfies the agreement condition AC_i, the previous value v_i^ti may not be obtainable in some peer pi. We have to find a cut which is not only satisfiable but also obtainable in each peerp_i.

[Definition] Act=v₁^t1, . . . , v_n^tnis referred to as recoverable in a historyH_i^δi iff the cutctis satisfiable and obtainable in a peerpi. A cutctis recoverable iff the cutctis recoverable in every peerp_i.

[Theorem] If there is a recoverable cutct=v₁^t1, . . . , v_n^tnin a historyH_i^δi, every peerpican make an agreement on the cutctby backing to the previous roundti+ 1.

[Proof] The cutct=v₁^t1, . . . , v_n^tnsatisfies the agreement condition from the as-sumption. Each peer pi can back to the previous roundti + 1 since the cutctis obtainable in the peerp_i.

In a historyH_i^δi, there might be multiple recoverable cutsct₁, . . . , ct_m (m >

1). Every peerpi has to take the same cutctl out of the possible cutsct₁, . . . , ctn. Letct₁andct₂be a pair of recoverable cutsv₁₁^t11, . . . , v^t₁¹ⁿ_nandc^t₂₁²¹, . . . , c^t₂²ⁿ_nof a history H_i^δi, respectively. First, the cut ct₁ is referred to as precede the other cutct₂ in the historyH_i^δi (ct₁ → ct₂) ift_1j ≤t_2j for every peer p_j (= 1, . . ., n).

Otherwise, a pair of the cutsct₁ andct₂ are referred to as intersect. Figure 3.11 shows a historyH_i^δi and three cutsct₁,ct₂ andct₃. Here, the cutct₁ precedes the

other cut ct₂ (ct₁ → ct₂). The cutsct₁ andct₂ intersect and the cutsct₂ andct₃ also intersect. Suppose there are a pair of recoverable cutsct₁ andct₂ in a history H_i^δi. Here, each peerpihas to make a decision on which cutct₁ orct₂to be taken.

In this paper, each peer p_i takes the cutct₁ if the cutct₂ precedes the cutct₁ in the historyH_i^δi (ct₂ → ct₁). Next, suppose a pair of the cutsct₁ andct₂ intersect in the historyH_i^δi. Here, we introduce the weight|ct|for a cutct=v^t₁¹, . . . , v_n^tn in a historyH_i^δ₁¹, . . . , H_in^δnas|ct|=

j=1,...,n (δ_j -t_j). A cutct₁ is referred to as smaller than another cutct₂ (ct₁ < ct₂) if|ct₁|<|ct₂|. The cutct₁ is taken if the cutsct₁andct₂ intersect and thect₁ is smaller than the cutct₂ (|ct₁|<|ct₂|). Let CT be a set of recoverable cuts in a historyH_i^δi. A cutctis referred to as maximal in the history H_i^δi iff there is no cutct in the historyH_i^δi where ctprecedes the cutct (ct→ct). Each peerp_iselects a cutctin the setCT as follows:

[Select (CT)]

1. LetM CT be a set of maximal cuts in the setCT with respect to the prece-dent relation→.

2. A smallest cutctis selected in the minimal cut setM CT.

H

₁₁

H

₁₃

H

₁₂

ct

₁

ct

₃

ct

₂

Figure 3.11: Cuts.

This selection rule means each peer takes a more recent cut to reduce the number of values which to be withdrawn.

The cuts can be also ordered in the preference of each peer. A cut ct₁ = v₁₁^t11, . . . , v₁^t1n_n is referred to as more preferable than another cutct₂=v^t₂₁²¹, . . . , v₂^t2n_n (ct₁ ct₂) iffv₂^t2j_j ^P_j v₁^t1j_j orv₂^t2j_j |^P_j v₁^t1j_j for every peer p_j (j = 1,. . . , n). The

cutsct₁ andct₂ are preferentially independent (ct₁ |ct₂) iff neitherct₁ ct₂ nor ct₁ ct₂. A cut ct₁ is referred to as preferentially superior to another cut ct₂ (ct₁ ⇒ ct₂) iff ct₁ | ct₂ and |{v₁j |v^t₂^2j_j ^Pj v₁^t1j_j }| ≥ |{v₂k | v₁^t2k_k ^Pk v^t₂^1k_k}|. The cutct₁ includes more preferable values than the other cutct₂. A cutctis taken by every peer in the selection rule Mselection(CT):

[Selection rules: Mselect(CT)]

1. Let M P C be a set of cuts which are maximally preferable in the cut set CT.

2. If M P C =φ, one cutct is selected in the setM P C, i.e. where ctis the smallest in the setM P C.

3. IfM P C =φ,ct= Select(CT).

A local historyH_j^tj of a peer p_j at roundt_j is a sequence v⁰_j, v_j¹, . . . , v_j^tj−1 of values which each peer p_j takes until roundt_j (j =1, . . . , n). v^s_j precedes v_j^u iff s < u. The value v_j^tj−1 is current and the other values are previous in H_j^tj. v_j⁰, . . . , v_j^u andv_j^u, . . . , v_j^tj−1 (0 ≤u ≤ t_j −1) are prefix and postfix of H_j^tj, respectively. Suppose a peerp_ireceives values a, b, c, d, and e from another peer p_j. Here,H_j⁵ =a, b, c, a, d, e. a, b, cis a prefix andd, eis a postfix ofH_j⁵.

For each valuev_j^u in the historyH_j^tj, letV_j^u(v_j^u) show a package ofv_j^u. That means, a peerp_jsends the packageV_j^u(v^u_j) and takes the primary valuev_j^uat round u.

A global history G is a collection of local histories H₁^t1, . . ., H_n^tn. In a global history G = H₁^t1, . . . , H_n^tn where H_i^ti = v⁰_i, . . . , v_i^ti−1 (i = 1, . . . , n), a tuple[x^u₁¹, . . . , x^u_nⁿ]of values is referred to as cut, whereu_k ≤t_k and each value x^u_k^kis in a packageV_k^ukof a local historyH_k^tkfork= 1,. . .,n. A cut[x^u₁¹, . . . , x^u_nⁿ] is satisfiable if the valuesx^u₁¹, . . . , x^v_nⁿ satisfy the agreement conditionAC.

Letcu=[x^u₁¹, . . . , x^u_nⁿ]andcs=[y₁^s1, . . . , y_n^sn]be a pair of satisfiable cuts in a global historyG=H₁^t1, . . . , H_n^tnwherev_i ≤t_i ands_i ≤t_ifori=1, . . . , n. The size|cu|of the cutcuis given as_n

i=1(t_i -u_i). A cutcuis smaller than another cutcs(cu < cs) iff |cu|<|cs|. The cutcuprecedes another cutctiffu_i ≤s_i for i=1, . . . , n. A cutcu=[y₁^u1, . . . , y_n^un]is maximally satisfiable iffctis satisfiable and there is no satisfiable cut ct^, which precedesctin a global history G. A cut cu is maximally satisfiable iffcuis satisfiable and there is no satisfiable cutcu which is smaller thancu.

p

p p

a time

V

₃¹

1

2

3

V

₃²

round1 round 2 b

c d

e c

a b

e b

d c

V

₂²

V

₂¹

V

₁²

V

₁¹

p

p p

time

1 a

2

3

b c d

e

c b a

b e c d

round 1 round 2 round 3 round 4

(1)

(2)

Figure 3.12: Multiple cuts.

Figure 3.12 (1) shows the history of three peersp₁,p₂, andp₃after exchanging

packages with each other. At each roundk, each peerp_isends a packageV_i^kwhich including a pair of values. For example, the peer p₁ sends a packageV₁¹ = a, b where a value a is primary and b is secondary. In Figure 3.12 (2), each peer takes the single-value exchange scheme to send the same values as Figure 3.12 (1). In this example, each peer has five different values in the value domainD= a, b, c, d, e. The E-precedent relations between values in each peerpias follows:

p₁: a→b→c→d→e p₂: c→e→b →a→d p₃: b→e→c→d→a

In the multi-value exchange scheme, according to the precedent relation between values, the peers p₁, p₂ and p₃ send packagesV₁¹ =a, b, V₂¹ = c, e, andV₃¹ = b, eto the other peers at round 1, respectively. On the other hand, in the single-value exchange scheme, the peers p₁, p₂ and p₃ send values a, c, and b to each other at round 1, respectively. In the multi-value exchange scheme, as shown in the Figure 3.12 (1) after two rounds, the peers detect two satisfiable cuts ct₁ = [c, c, c,] andct₂ = [b, b, b] in the history, respectively. Therefore, the peers makes agreement on the cutct₂, becausect₂is the smallest cut among satisfiable cuts. In the single-value exchange scheme, as shown in the Figure 3.12 (2), it takes three rounds to detect the same satisfiable cuts. Following the example, it is obvious that, by using the multi-value exchange scheme, we can significantly reduce the overall time consumption.

In this paper, we consider the binary package V_iⁱ only contains two values.

After evaluating the scheme, we would like to extend it to a multi-ary package which can include more than two values.

[Definition] A cut

v₁^u1−1, . . . , v_n^un−1

is consistent in a global historyG=H₁^t1, . . .,H_n^tniff there is no valuev_j in a packageV_j^sj(v_j^sj) (s_j ≤u_j−1) such thatv_i^ri

→i v_j andu_i−1≤r_i.

ドキュメント内 Efficient and Flexible Agreement Protocols Based on Trustworthiness Relation of Peers in Unstructured Peer-to-Peer Overlay Networks (ページ 65-71)