( PDF ) Adaptação de protocolos distribuídos simétricos pelo texto à dinamicidade e heterogeneidade da carga do ambiente de execução através de oráculos de latência



ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

76, 1% 45, 4%

76, 1%

45, 4%

♦S

0 32

32

p

2

p

1

p

2

p

1

♦S

local

i

global

i

estimativ a corrente

i

(n−f)

p

r

i

est1

i

♦S

•

P = {p

1

, p

2

, p

3

}

m

1

m

2

p

1

m

1

∀p

i

∈ P

p

1

m

2

∀p

i

∈ P

p

2

m

2

p

1

p

2

m

1

p

1

p

3

m

2

p

1

p

3

m

1

p

1

P p

1

p

2

p

3

p

3

p

1

m

1

∀p

i

∈ P p

2

m

1

∀p

i

∈ P p

3

m

1

∀p

i

∈ P

p

1

m

2

∀p

i

∈ P p

2

m

2

∀p

i

∈ P p

3

m

2

∀p

i

∈ P

p

2

m

2

p

1

p

1

m

2

p

2

p

2

m

2

p

3

p

2

m

1

p

1

p

1

m

1

p

2

p

2

m

1

p

3

p

3

m

2

p

1

p

3

m

2

p

2

p

1

m

2

p

3

p

3

m

1

p

1

p

3

m

1

p

2

p

1

m

1

p

3

ms s

ms

♦S

•

D D

′

D D

′

D

′

D D D

′

♦S ♦W Ω

Ω

• p t

p

ALG 1

CRA

ALGs

ALG 2

Mensagens / Requisições

Ativa / Desativa

k

Interface de rede

Aplicação

Consenso

DF

obtemSuspeitos()

envia(msg) recebe(msg)

propoe(v) decide(u)

lista de suspeitos

♦S

Π n Π = {p

1

, p

2

, ..., p

n

} n > 1

f f < n/2

p

i

p

j

c

ij

p

j

p

i

c

ji

p

i

p

j

c

ij

p

j

c

ji

♦S

Lat

p

i

p

j

t

p

i

p

j

t

Lat : Π × Π × R

+

→ R

+

(p

i

, p

j

, t) ∈ Π × Π × R

+

Lat(p

i

, p

j

, t) = L L ∈ R

+

∀(p

i

, p

j

, t) ∈ Π × Π × R

+

, ∃L ∈ R

+

: Lat(p

i

, p

j

, t) = L.

•

• v

•

♦S

n ≥ 2f + 1

r c = (r mod n) + 1 c

•

ts

p

c p

c

p

v

p

estimate

p

= v

p

state

p

=

r

p

= ts

p

= 0

state

p

=

r

p

= r

p

+ 1

c

p

= (r

p

mod n) + 1

p, r

p

, estimate

p

, ts

p

c

p

p == c

p

⌈(n + 1)/2⌉ q, r

p

, estimate

q

, ts

q

msgs

p

[r

p

] q, r

p

, estimate

q

, ts

q

p q, r

p

, estimate

q

, ts

q

t ts

p

q, r

p

, estimate

q

, ts

q

∈ msgs

p

[r

p

]

estimate

p

estimate

q

q, r

p

, estimate

q

, t ∈ msgs

p

[r

p

]

p, r

p

, estimate

p

c

p

, r

p

, estimate

c

p

c

p

c

p

∈ D

p

c

p

, r

p

, estimate

c

p

c

p

estimate

p

= estimate

c

p

ts

p

= r

p

p, r

p

, c

p

p, r

p

, c

p

p == c

p

⌈(n + 1)/2⌉ q q, r

p

, q, r

p

,

⌈(n + 1)/2⌉ q q, r

p

,

p, r

p

, estimate

p

,



q, r

q

, estimate

q

,

state

p

estimate

q

state

p

c

• p

c

⌈(n + 1)/2⌉

•

p

c

• p

c

⌈(n+ 1)/2⌉

f(r, n) = (r mod n) + 1

r

n r

Π

e1

=

{p

1

, p

2

, p

3

}

p

i

l = {p

2

, p

3

, p

1

, p

2

, p

3

, p

1

, ...}

r = 1 f(1, 3) = 2

p

2

r

f(r, n) l

l

{p

2

, p

3

, p

1

}

l

c

t

p

i

,l

c

e(r)

e(r) p

i

r

l

c

T

p

i

,l

c

e

1

(r),e

2

[t

p

i

,l

c

e

1

(r)

, t

p

i

,l

c

e

2

]

T

Π,l

c

e

1

(r),e

2

e

1

(r) e

2

∀p ∈ Π

[t

p

i

,l

c

e

1

(r)

, t

p

j

,l

c

e

2

]

p

i

, p

j

∈ Π

p

i

Π

p

i

Π

p

i

p

i

Π

p

i

t

p

i

,l

c

inicialC(1)

t

p

i

,l

c

finalC

p

i

l

c

T

p

i

,l

c

inicialC(1),finalC

p

i

T

p

i

,l

c

inicialC(1),finalC

= t

p

i

,l

c

finalC

− t

p

i

,l

c

inicialC(1)

.

p

i

p

i

r

p

i

r

′

r = r

′

p

i

t

p

i

,l

c

finalC

t

p

i

,l

c

inicialC(1)

p

i

EXEC LOCAL

p

i

,l

c

F INALC

p

i

,l

c

t

p

i

,l

c

finalC

EXEC LOCAL

p

i

,l

c

= {T

p

i

,l

c

inicialC(1),finalC

| T

p

i

,l

c

inicialC(1),finalC

∈ R

+

,

T

p

i

,l

c

inicialC(1),finalC

= t

p

i

,l

c

finalC

− t

p

i

,l

c

inicialC(1)

,

∀(t

p

i

,l

c

finalC

, r

finalC

) ∈ F INALC

p

i

,l

c

}.

l

c

k 1 ≤ k ≤ |Π|

EXEC GLO BAL

Π,l

c

p

i

∈ Π l

c

T

Π,l

c

inicialC(1),finalC

= P egaItemPosId(EXEC

GLOBAL

Π,l

c

, k) onde,

EXEC

GLOBAL

Π,l

c

= {(T

p

i

,l

c

inicialC(1),finalC

, p

i

) | (T

p

i

,l

c

inicialC(1),finalC

, p

i

) ∈ R

+

× N,

T

p

i

,l

c

inicialC(1),finalC

= P egaItemP os(EXEC

LOCAL

p

i

,l

c

, 1),

∀p

i

∈ Π}.

P egaItemPos i

P egaItemPos : P (R

+

) × N → R

+

P (R

+

) = {A|A ⊆

R

+

}

R

+

R

+

P egaItemPos (A, i) ∈ P (R

+

) × N a a ∈ R

+

∧ a ∈ A

P egaItemPos(A, i) = a : a ∈ A, i = |Min a| onde,

Min

a = {x | x ∈ A, x ≤ a}.

P egaItemPosId P egaItemPos

A B = {(y, id) | y ∈

R

+

, id ∈ N}

B y

id P egaItemPosId

b

′

∈ R

+

i B (y, id) b

′

= y (y, id) ∈ B

P egaItemPosId(B, i) = b

′

: b

′

= y, (y, id) ∈ B, i = |Min (y, id)| onde,

Min

(y, id) = {(y

i

, id

i

) | (y

i

, id

i

) ∈ B, y

i

≤ y, id

i

≤ id}.

P E(n)

Π n = |Π| |P E(n)| = n!

EXEC GLOBAL

Π,P E(n)

EXEC GLOBAL

Π,P E(n)

= {(T

Π,l

c

inicialC(1),finalC

, l

c

) | (T

Π,l

c

inicialC(1),finalC

, l

c

) ∈ R

+

× P (N),

T

Π,l

c

inicialC(1),finalC

= P egaItemP osLista(EXEC

GLOBAL

Π,l

c

, k),

∀l

c

∈ P E(n), 1 ≤ k ≤ |Π|}.

P egaItemPosLista P egaItemPosId

B

C = {(y, lista) | y ∈ R

+

, lista ∈ P (N)} C

y lista

R

+

P (N)

P egaItemPosLista c

′

∈ R

+

i

C (y, lista) c

′

= y (y, lista) ∈ C

≤ lista

i

lista

P egaItemPosLista(C, i) = c

′

: c

′

= y, (y, lista) ∈ C, i = |Min (y, lista)| onde,

Min

(y, lista) = {(y

i

, lista

i

) | (y

i

, lista

i

) ∈ C, y

i

≤ y, lista

i

≤ lista}.

p

i

t

p

i

,l

c

finalC

F INALC

p

i

,l

c

t

p

i

,l

c

finalC

t

p

i

,l

c

finalC

p

c

(r)

r p

c

(r) ∈ Π

p

c

(r)

t

p

c

(r),l

c

e1

= t

p

c

(r),l

c

propostaC(r)

p

c

(r)

t

p

c

(r),l

c

e2

= t

p

c

(r),l

c

val orC(r)

p

c

(r) DC

t

p

c

(r),l

c

e3

= t

p

c

(r),l

c

inicialDC(r)

p

c

(r)

p

i

p

i

∈ Π t

p

i

,l

c

e4

= t

p

i

,l

c

finalDC(r)

p

i

p

c

(r) t

p

c

(r),l

c

inicialDC(r)

t

p

i

,l

c

finalDC(r)

[t

p

c

(r),l

c

inicialDC(r)

, t

p

i

,l

c

finalDC(r)

]

T

p

i

,l

c

inicialDC(r),finalDC(r)

t

p

c

(r),l

c

inicialDC(r)

= t

p

c

(r),l

c

val orC(r)

t

p

c

(r),l

c

propostaC(r)

t

p

c

(r),l

c

val orC(r)

p

c

(r) r

r

⌈(N + 1)/2⌉ N = |Π|

r

p

i

r

′

1 ≤ r

′

≤ r r

p

i

r ≤ N r = 1 N r = 2

N − 1 r = N

r = ⌊(N + 1 )/2⌋

⌈(N +1)/2⌉

r r ⌈(N + 1)/2⌉ 1 ≤ r ≤ ⌊(N + 1)/2⌋

p q

t

p

c

(r),l

c

propostaC(r)

→ t

p

c

(r),l

c

val orC(r)

→ t

p

c

(r),l

c

inicialDC(r)

→ t

p

i

,l

c

finalDC(r)

t

p

c

(r),l

c

val orC(r)

= t

p

c

(r),l

c

inicialDC(r)

p

i

∈ Π

t

p

i

,l

c

finalC

= t

p

i

,l

c

finalDC(r)

DC

p

i

,r

p

i

r 1 ≤ r ≤ ⌊(N + 1)/2⌋

F INALC

p

i

,l

c

p

i

q

p (coordenador)

estimativa

confirmação

proposta

difusão

e1 = propostaC(1)

e2 = valorC(1)

e3 = inicialDC(1)

e4 = finalDC

e1 e2 = e3 e4

e4

F INALC

p

i

,l

c

= {(t

p

i

,l

c

finalC

, r

finalC

) | (t

p

i

,l

c

finalC

, r

finalC

) ∈ R

+

× N,

t

p

i

,l

c

finalC

= P egaItemPos(DC

p

i

,r

, 1), r

finalC

= r,

∀r, 1 ≤ r ≤ ⌊(N + 1 )/2⌋}.

Π

e2

= {p

1

, p

2

, p

3

, p

4

, p

5

}

m

1

p

1

m

1

m

1

N N = |Π

e2

|

N − 1 p

i

p

i

nl 1 ≤ nl ≤ N − 1

pn

1

pn

2

pn

1

pn

N−1

pn

N−2

p

1

p

2

p

2

pn

nl

p2 = pn1 p2 = pn2 p2 = pn3

p1 p1 p1 p1pn1 pn1 pn2 pn1 pn2 pn3 pn1 pn2 pn3 pn4

nível 1 nível 2 nível 3

p2 = pn4

nível 4

p

2

p

1

p1 p2

nível 1

p1 p3 p2

p1 p4 p2

p1 p5 p2

nível 2

p1 p4 p5 p2

p1 p5 p3 p2

p1 p5 p4 p2

p1 p3 p4 p2

p1 p3 p5 p2

p1 p4 p3 p2

nível 3

p1 p3 p4 p5 p2

p1 p3 p5 p4 p2

p1 p4 p3 p5 p2

p1 p4 p5 p3 p2

p1 p5 p3 p4 p2

p1 p5 p4 p3 p2

nível 4

p

2

p

1

r p

i

t

p

i

,l

c

finalDC(r)

DC

p

i

,r

nl

t

p

i

,l

c

finalDC(r)

= P egaItemP os(DC

p

i

,r

, 1) onde,

DC

p

i

,r

=



DC

p

i

,r,nl

, ∀nl, 1 ≤ nl ≤ N − 1.

DC

p

i

,r,nl

nl p

i

t

p

i

,l

c

finalDC(r,nl)

nl = 1

t

p

i

,l

c

finalDC(r,nl)

finalDC(r, x) p

i

finalDC(r, x − 1)

x − 1

p

i

p

i

p

i

= pn

1

p

i

p

i

= pn

nl

1 ≤ nl ≤ N − 1 Π

nl

nl DC

p

i

,r,nl

p

i

nl 1 ≤ nl ≤ N − 1

nl = 1, DC

p

i

,r,1

= {t

p

i

,l

c

finalDC(r,1)

| t

p

i

,l

c

finalDC(r,1)

∈ R

+

,

t

p

i

,l

c

finalDC(r,1)

= t

p

c

(r),l

c

val orC(r)

+ Lat(p

c

(r), p

i

, t

p

c

(r),l

c

val orC

)}

nl > 1, DC

p

i

,r,nl

= {t

p

i

,l

c

finalDC(r,nl)

| t

p

i

,l

c

finalDC(r,nl)

∈ R

+

,

t

p

i

,l

c

finalDC(r,nl)

= t

pn

nl−1

,l

c

finalDC(r,nl−1)

+ Lat(pn

nl−1

, p

i

, t

pn

nl−1

,l

c

finalDC(r,nl−1)

),

∀pn

z

∈ Π

z

∧ ∀t

pn

z

,l

c

finalDC(r,z)

∈ DC

pn

z

,r,z

, z = nl − 1}.

finalDC(r)

propostaC(r) valorC(r)

p

i

p

i

r 1 ≤ r ≤ ⌊(N + 1)/2⌋

P ROP OST AC

p

c

(r)

V ALORC

p

c

(r)

P ROP OST AC

p

c

(r)

V ALORC

p

c

(r)

r > ⌊(N + 1)/2⌋

V ALORC

p

c

(r)

P ROP OST AC

p

c

(r)

V ALORC

p

c

(r)

pid

p

c

(r)

P egaItemPosId

t

p

c

(r),l

c

propostaC(r)

= max(t

p

c

(r),l

c

inicialR(r)

, P egaItemP osId(P ROP OST AC

p

c

(r)

, ⌈(N + 1)/2⌉)), onde,

|P ROP OST AC

p

c

(r)

| ≥ ⌈(N + 1)/2⌉;

P ROP OST AC

p

c

(r)

= {(t

p

c

(r),l

c

est(r)

, pid) | (t

p

c

(r),l

c

est(r)

, pid) ∈ R

+

× N,

t

p

c

(r),l

c

est(r)

= t

p

i

,l

c

inicialR(r)

+ Lat(p

i

, p

c

(r), t

p

i

,l

c

inicialR(r)

),

∀p

i

∈ Π}.

t

p

c

(r),l

c

val orC(r)

= P egaItemPosId(V ALORC

p

c

(r)

, ⌈(N + 1)/2⌉), onde,

|V ALORC

p

c

(r)

| ≥ ⌈(N + 1)/2⌉;

V ALORC

p

c

(r)

= {(t

p

c

(r),l

c

conf irma(r)

, pid) | (t

p

c

(r),l

c

conf irma(r)

, pid) ∈ R

+

× N,

t

p

c

(r),l

c

conf irma(r)

= t

p

c

(r),l

c

propostaC(r)

+ Lat(p

c

(r), p

i

, t

p

c

(r),l

c

propostaC(r)

)+

Lat(p

i

, p

c

(r), t

p

c

(r),l

c

propostaC(r)

+ Lat(p

c

(r), p

i

, t

p

c

(r),l

c

propostaC(r)

))}.

r inicialR(r)

valorC(r) propostaC(r)

t

p

c

(r),l

c

val orC(r)

> t

p

c

(r)

proposta

≥ t

p

c

(r)

inicialR(r)

t

p

c

(r),l

c

propostaC(r)

t

p

i

,l

c

inicialR(1)

= t

p

i

,l

c

inicialC(1)

∀p

i

∈ Π p

i

r p

i

1 ≤ r ≤ N − 1 p

i

= p

c

(r) p

i

r + 1

p

c

(r) t

p

i

,l

c

inicialR(r)

r = 1

t

p

i

,l

c

inicialR(r)

= t

p

c

(r−1),l

c

proposalC(r−1)

+ Lat(p

c

(r − 1), p

i

, t

p

c

(r−1),l

c

proposalC(r−1)

).

Π

P E(n) Π

l

c

∈ P E(n)

p

i

∈ Π

l

c

F INALC

p

i

,l

c

p

i

l

c

EXEC LOCAL

p

i

,l

c

p

i

l

c

EXEC GLOBAL

Π,l

c

k l

c

T

Π,l

c

inicialC(1),finalC

∀l

c

∈ P E(n)

k

EXEC GLOBAL

Π,P E(n)

P egaItemPosLista(EXEC GLOBAL

Π,P E(n)

Π

e3

= {p

1

, p

2

, p

3

}, N = |Π

e3

| = 3 Lat(p

i

, p

i

, t) = 0 ∀t ∈ R

+

∀p

i

∈ Π

e3

P E(3)

P E(3) = {[p

1

, p

2

, p

3

], [p

1

, p

3

, p

2

], [p

2

, p

1

, p

3

], [p

2

, p

3

, p

1

], [p

3

, p

1

, p

2

], [p

3

, p

2

, p

1

]}

P E(3)

l

c

= [p

1

, p

2

, p

3

]

t

p

i

,[p

1

,p

2

,p

3

]

inicialC(1)

= 0

∀p

i

∈ Π

e3

F INALC

p

i

,[p

1

,p

2

,p

3

]

propostaC(r)

P ROP OST AC

p

c

(r)

valorC(r)

V ALORC

p

c

(r)

p

i

∈ Π

e3

r 1 ≤ r ≤ 3

r = 1 r = 1 p

1

Π

e3

p

1

p

2

p

3

t

p

1

(1),[p

1

,p

2

,p

3

]

inicialR(1)

= t

p

1

(1),[p

1

,p

2

,p

3

]

inicialC(1)

= 0

t

p

2

,[p

1

,p

2

,p

3

]

inicialR(1)

= t

p

2

,[p

1

,p

2

,p

3

]

inicialC(1)

= 0

t

p

3

,[p

1

,p

2

,p

3

]

inicialR(1)

= t

p

3

,[p

1

,p

2

,p

3

]

inicialC(1)

= 0

propostaC(1) p

1

P ROP OST AC

p

1

(1)

P ROP OST AC

p

1

(1)

= {(t

p

1

(1),[p

1

,p

2

,p

3

]

inicialR(1)

+ Lat(p

1

(1), p

1

(1), t

p

1

(1),[p

1

,p

2

,p

3

]

inicialR(1)

), p

1

),

(t

p

2

,[p

1

,p

2

,p

3

]

inicialR(1)

+ Lat(p

2

, p

1

(1), t

p

2

,[p

1

,p

2

,p

3

]

inicialR(1)

), p

2

),

(t

p

3

,[p

1

,p

2

,p

3

]

inicialR(1)

+ Lat(p

3

, p

1

(1), t

p

3

,[p

1

,p

2

,p

3

]

inicialR(1)

), p

3

)}

t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(1)

= max(t

p

1

(1),[p

1

,p

2

,p

3

]

inicialR(1)

, P egaItemP osId(P ROP OST AC

p

1

(1)

, 2))

valorC p

1

(1)

V ALORC

p

1

(1)

V ALORC

p

1

(1)

= {(t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

+ Lat(p

1

(1), p

1

(1), t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

)+

Lat(p

1

(1), p

1

(1), t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

+ Lat(p

1

(1), p

1

(1), t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

)), p

1

),

(t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

+ Lat(p

1

(1), p

2

, t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

)+

Lat(p

2

, p

1

(1), t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

+ Lat(p

1

(1), p

2

, t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

)), p

2

),

(t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

+ Lat(p

1

(1), p

3

, t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

)+

Lat(p

3

, p

1

(1), t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

+ Lat(p

1

(1), p

3

, t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(r)

)), p

3

)}

t

p

1

(1),[p

1

,p

2

,p

3

]

val orC(1)

= P egaItemP osId (V ALORC

p

1

(1)

, 2)

P ROP OSALC

p

1

(1)

V ALORC

p

1

(1)

propostaC(1) valorC( 1)

r = 1

finalDC(1, nl) 1 ≤ nl ≤ 2

r = 1

p

1

nl = 1

p

2

p

3

nl = 1 nl = 2

DC

p

i

,1,1

finalDC(1, 1) p

i

∈ Π

e3

DC

p

1

(1),1,1

= {t

p

1

(1),[p

1

,p

2

,p

3

]

val orC(1)

+ Lat(p

1

(1), p

1

(1), t

p

1

(1),[p

1

,p

2

,p

3

]

val orC(1)

)}

DC

p

2

,1,1

= {t

p

1

(1),[p

1

,p

2

,p

3

]

val orC(1)

+ Lat(p

1

(1), p

2

, t

p

1

(1),[p

1

,p

2

,p

3

]

val orC(1)

)}

DC

p

3

,1,1

= {t

p

1

(1),[p

1

,p

2

,p

3

]

val orC(1)

+ Lat(p

1

(1), p

3

, t

p

1

(1),[p

1

,p

2

,p

3

]

val orC(1)

)}

DC

p

i

,1,2

finalDC(1, 2) p

2

p

3

DC

p

2

,1,2

= {t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(1,1)

+ Lat(pn

1

, p

2

, t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(1,1)

)}

= {t

p

3

,[p

1

,p

2

,p

3

]

finalDC(1,1)

+ Lat(p

3

, p

2

, t

p

3

,[p

1

,p

2

,p

3

]

finalDC(1,1)

)}

DC

p

3

,1,2

= {t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(1,1)

+ Lat(pn

1

, p

3

, t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(1,1)

)}

= {t

p

2

,[p

1

,p

2

,p

3

]

finalDC(1,1)

+ Lat(p

2

, p

3

, t

p

2

,[p

1

,p

2

,p

3

]

finalDC(1,1)

)}

DC

p

i

,1

finalDC(1, nl) [1, 2] DC

p

i

,1

=



DC

p

i

,1,nl

1 ≤ nl ≤ 2 p

i

∈ Π

e3

DC

p

1

(1),1

= DC

p

1

(1),1,1

DC

p

2

,1

= DC

p

2

,1,1

∪ DC

p

1

(1),1,2

DC

p

3

,1

= DC

p

3

,1,1

∪ DC

p

3

,1,2

p

i

p

i

t

p

i

,l

c

finalC

r = 1 p

1

(1) t

p

i

,l

c

finalC

t

p

1

(1),[p

1

,p

2

,p

3

]

finalC

= P egaItemPos(DC

p

1

(1),1

, 1)

t

p

2

,[p

1

,p

2

,p

3

]

finalC

= P egaItemPos(DC

p

2

,1

, 1)

t

p

3

,[p

1

,p

2

,p

3

]

finalC

= P egaItemPos(DC

p

3

,1

, 1)

r = 2 r = 2 p

2

p

2

p

3

r = 1 p

1

r = 2 r = 2 p

2

p

3

t

p

2

(2),[p

1

,p

2

,p

3

]

inicialR(2)

= t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(1)

+ Lat(p

1

(1), p

2

(2), t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(1)

)

t

p

3

,[p

1

,p

2

,p

3

]

inicialR(2)

= t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(1)

+ Lat(p

1

(1), p

3

, t

p

1

(1),[p

1

,p

2

,p

3

]

propostaC(1)

)

propostaC p

2

(2)

P ROP OST AC

p

2

(2)

P ROP OST AC

p

2

(2)

= {(t

p

2

(2),[p

1

,p

2

,p

3

]

inicialR(2)

+ Lat(p

2

(2), p

2

(2), t

p

2

(2),[p

1

,p

2

,p

3

]

inicialR(2)

), p

2

),

(t

p

3

,[p

1

,p

2

,p

3

]

inicialR(2)

+ Lat(p

3

, p

2

(2), t

p

3

,[p

1

,p

2

,p

3

]

inicialR(2)

), p

3

)}

t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

= max(t

p

2

(2),[p

1

,p

2

,p

3

]

inicialR(2)

, P egaItemP osId(P ROP OST AC

p

2

(2)

, 2))

valorC p

2

(2)

V ALORC

p

2

(2)

V ALORC

p

2

(2)

= {(t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

+ Lat(p

2

(2), p

2

(2), t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

)+

Lat(p

2

(2), p

2

(2), t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

+ Lat(p

2

(2), p

2

(2), t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

)), p

2

),

(t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

+ Lat(p

2

(2), p

3

, t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

)+

Lat(p

3

, p

2

(2), t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

+ Lat(p

2

(2), p

3

, t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

)), p

3

)}

t

p

2

(2),[p

1

,p

2

,p

3

]

val orC(2)

= P egaItemP osId (V ALORC

p

2

(2)

, 2)

r = 2 p

2

(2)

nl = 1 p

1

p

3

nl = 1

nl = 2 DC

p

i

,2,1

finalDC(2, 1)

p

i

∈ Π

e3

DC

p

1

,2,1

= {t

p

2

(2),[p

1

,p

2

,p

3

]

val orC(2)

+ Lat(p

2

(2), p

1

, t

p

2

(2),[p

1

,p

2

,p

3

]

val orC(2)

)}

DC

p

2

(2),2,1

= {t

p

2

(2),[p

1

,p

2

,p

3

]

val orC(2)

+ Lat(p

2

(2), p

2

(2), t

p

2

(2),[p

1

,p

2

,p

3

]

val orC(2)

)}

DC

p

3

,2,1

= {t

p

2

(2),[p

1

,p

2

,p

3

]

val orC(2)

+ Lat(p

2

(2), p

3

, t

p

2

(2),[p

1

,p

2

,p

3

]

val orC(2)

)}

DC

p

i

,2,2

finalDC(2, 2) p

1

p

3

DC

p

1

,2,2

= {t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(2,1)

+ Lat(pn

1

, p

1

, t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(2,1)

)}

= {t

p

3

,[p

1

,p

2

,p

3

]

finalDC(2,1)

+ Lat(p

3

, p

1

, t

p

3

,[p

1

,p

2

,p

3

]

finalDC(2,1)

)}

DC

p

3

,2,2

= {t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(2,1)

+ Lat(pn

1

, p

3

, t

pn

1

,[p

1

,p

2

,p

3

]

finalDC(2,1)

)}

= {t

p

1

,[p

1

,p

2

,p

3

]

finalDC(2,1)

+ Lat(p

1

, p

3

, t

p

1

,[p

1

,p

2

,p

3

]

finalDC(2,1)

)}

DC

p

i

,2

p

i

∈ Π

e3

DC

p

1

,2

= DC

p

1

,2,1

∪ DC

p

1

,2,2

DC

p

2

(2),2

= DC

p

2

(2),2,1

DC

p

3

,2

= DC

p

3

,2,1

∪ DC

p

3

,2,2

r = 2 p

2

t

p

1

,[p

1

,p

2

,p

3

]

finalC

= P egaItemPos(DC

p

1

,2

, 1)

t

p

2

(2),[p

1

,p

2

,p

3

]

finalC

= P egaItemPos(DC

p

3

,2

, 1)

t

p

3

,[p

1

,p

2

,p

3

]

finalC

= P egaItemPos(DC

p

3

,2

, 1)

r = 3 r = 3 p

3

p

1

p

2

r = 1 r = 2

r = 3 p

3

t

p

3

(3),[p

1

,p

2

,p

3

]

inicialR(3)

= t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

+ Lat(p

2

(2), p

3

(3), t

p

2

(2),[p

1

,p

2

,p

3

]

propostaC(2)

)

⌈N + 1/2⌉ = 2

propostaC(3) valorC(3)

P ROP OST AC

p

3

(3)

V ALORC

p

3

(3)

t

p

3

(3),[p

1

,p

2

,p

3

]

propostaC(3)

t

p

3

(3),[p

1

,p

2

,p

3

]

val orC(3)

P ROP OST AC

p

3

(3)

= {(t

p

3

(3),[p

1

,p

2

,p

3

]

inicialR(3)

+ Lat(p

3

(3), p

3

(3), t

p

3

(3),[p

1

,p

2

,p

3

]

inicialR(3)

), p

3

)}

∄t

p

3

(3),[p

1

,p

2

,p

3

]

propostaC(3)

pois |P ROP OST AC

p

3

(3)

| < 2

V ALORC

p

3

(3)

= ∅

∄t

p

3

(3),[p

1

,p

2

,p

3

]

val orC(3)

pois |V ALORC

p

3

(3)

| < 2

r = 3 2

∄t

p

i

,[p

1

,p

2

,p

3

]

finalC

∀p

i

∈ Π

e3

F INALC

p

i

,[p

1

,p

2

,p

3

]

F INALC

p

i

,[p

1

,p

2

,p

3

]

finalC

p

i

r = 1 r = 2

F INALC

p

i

,[p

1

,p

2

,p

3

]

p

i

∈ Π

e3

F INALC

p

1

,[p

1

,p

2

,p

3

]

= {(P egaItemPos(DC

p

1

(1),1

, 1), 1), (P egaItemP os(DC

p

1

,2

, 1), 2)}

F INALC

p

2

,[p

1

,p

2

,p

3

]

= {(P egaItemPos(DC

p

2

,1

, 1), 1), (P egaItemP os(DC

p

2

(2),2

, 1), 2)}

F INALC

p

3

,[p

1

,p

2

,p

3

]

= {(P egaItemPos(DC

p

3

,1

, 1), 1), (P egaItemP os(DC

p

3

,2

, 1), 2)}

[p

1

, p

2

, p

3

] p

i

∈ Π

e3

EXEC LOCAL

p

i

,[p

1

,p

2

,p

3

]

[t

p

i

,[p

1

,p

2

,p

3

]

inicialC(1)

, t

p

i

,[p

1

,p

2

,p

3

]

finalC

]

∀t

p

i

,[p

1

,p

2

,p

3

]

finalC

∈ F INALC

p

i

,[p

1

,p

2

,p

3

]

EXEC LOCAL

p

i

,[p

1

,p

2

,p

3

]

EXEC LOCAL

p

1

,[p

1

,p

2

,p

3

]

= {P egaItemP os(DC

p

1

(1),1

, 1) − 0, P egaItemP os(DC

p

1

,2

, 1) − 0}

= {P egaItemP os(DC

p

1

(1),1

, 1), P egaItemP os(DC

p

1

,2

, 1)}

EXEC LOCAL

p

2

,[p

1

,p

2

,p

3

]

= {P egaItemP os(DC

p

2

,1

, 1) − 0, P egaItemP os(DC

p

2

(2),2

, 1) − 0}

= {P egaItemP os(DC

p

2

,1

, 1), P egaItemP os(DC

p

2

(2),2

, 1)}

EXEC LOCAL

p

3

,[p

1

,p

2

,p

3

]

= {P egaItemP os(DC

p

3

,1

, 1) − 0, P egaItemP os(DC

p

3

,2

, 1) − 0}

= {P egaItemP os(DC

p

3

,1

, 1), P egaItemP os(DC

p

3

,2

, 1)}

EXEC GLOBAL

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

p

i

EXEC LOCAL

p

i

,[p

1

,p

2

,p

3

]

EXEC GLOBAL

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

= {(P egaItemP os(EXEC LOCAL

p

1

,[p

1

,p

2

,p

3

]

, 1), p

1

),

(P egaItemPos(EXEC

LOCAL

p

2

,[p

1

,p

2

,p

3

]

, 1), p

2

),

(P egaItemPos(EXEC

LOCAL

p

3

,[p

1

,p

2

,p

3

]

, 1), p

3

)}

EXEC GLOBAL

Π

e3

,[p

1

,p

2

,p

3

]

k

1 ≤ k ≤ 3 [p

1

, p

2

, p

3

]

k = 1 T

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

inicialC(1),finalC

= P egaItemP osId (EXEC GLOBAL

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

, 1)

k = 2 T

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

inicialC(1),finalC

= P egaItemP osId (EXEC

GLOBAL

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

, 2)

k = 3 T

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

inicialC(1),finalC

= P egaItemP osId (EXEC

GLOBAL

{p

1

,p

2

,p

3

},[p

1

,p

2

,p

3

]

, 3)

l

c

= [p

1

, p

2

, p

3

]

P E(3)

R

E

D

E

CLT1

CLT2

(ok)1. checar permissão do arquivo [A1A2A3]

(ok)2. modificar cópia local do arquivo [A1A4A5]

(ok)3. fragmentar arquivo − F1(A1)F2(A4)F3(A5)

4. disseminar arquivo...

R2 − executando...

5. apagar cópia local do arquivo

(ok)1. checar permissão do arquivo [A1A2A3]

(ok)2. obter nomes dos fragmentos F1F2F3

3. recuperar fragmentos...

R1 − executando...

4. recompor o arquivo

SVR1

SVR2

SVR3

F1(cópia2)

F2(cópia1)

F1(cópia1)

F3(cópia1)

R1(READ, F1, F2, F3)

R1, R2

R2, R1

R1, R2

R2(WRITE, F1(A1), F2(A4), F3(A5))

F3(A3)

F2(A2)

F1(A1)

R

E

D

E

CLT1

CLT2

(ok)1. checar permissão do arquivo [A1A2A3]

(ok)2. modificar cópia local do arquivo [A1A4A5]

(ok)3. fragmentar arquivo − F1(A1)F2(A4)F3(A5)

4. disseminar arquivo...

R2 − executando...

5. apagar copia local do arquivo

(ok)1. checar permissão do arquivo [A1A2A3]

(ok)2. obter nomes dos fragmentos F1F2F3

(ok)3. recuperar fragmentos

R1 − finalizada!

(ok)4. recompor o arquivo [A1A4A3]????

SVR1

SVR2

SVR3

F1(cópia2)

F2(cópia1)

F1(cópia1)

F3(cópia1)

R1(READ, F1, F2, F3)

[A1A4A3]

R2, R1

R1, R2

R2(WRITE, F1(A1), F2(A4), F3(A5))

F1(A1)

F2(A4)

F3(A3)

[F

1

(A

1

), F

2

(A

2

), F

3

(A

3

)] F

i

A

i

SV R1 SV R2 SV R 3 CLT 1

CLT 2

F 2 F 3

[F

1

(A

1

), F

2

(A

4

), F

3

(A

5

)]

CLT 1

[F

1

(A

1

), F

2

(A

4

), F

3

(A

3

)]

R

E

D

E

CLT1

R1(READ, F1, F2, F3)

A

T

Ô

M

I

C

A

D

I

F

U

S

Ã

O

1. checar permissão do arquivo [A1A2A3]

2. modificar cópia local do arquivo [A1A4A5]

3. fragmentar arquivo − F1(A1)F2(A4)F3(A5)

4. disseminar arquivo

R2 − esperando...

5. apagar cópia local do arquivo

(ok)1. checar permissão do arquivo [A1A2A3]

(ok)2. obter nomes dos fragmentos F1F2F3

(ok)3. recuperar fragmentos

R1 − finalizada!

(ok)4. recompor arquivo [A1A2A3]

CLT2

R1, R2

R2(WRITE, F1(A1), F2(A4), F3(A5))

SVR1

F3(cópia1)

SVR2

F1(cópia1)

SVR3

F1(cópia2)

F2(cópia1)

F3(A3)

F2(A2)

F1(A1)

CLT1

R1(READ, F1, F2, F3)

CLT2

1. checar permissão do arquivo [A1A2A3]

2. modificar cópia local do arquivo [A1A4A5]

3. fragmentar arquivo − F1(A1)F2(A4)F3(A5)

4. disseminar arquivo

R2 − esperando...

5. apagar cópia local do arquivo

(ok)1. checar permissão do arquivo [A1A2A3]

(ok)2. obter nomes dos fragmentos F1F2F3

(ok)3. recuperar fragmentos

R1 − finalizada!

(ok)4. recompor arquivo [A1A2A3]

R

E

D

E

Exclusão

mútua

requisita lock recebe lock

aguarde...requisita lock

R1

SVR1

F3(cópia1)

SVR2

F1(cópia1)

SVR3

F1(cópia2)

F2(cópia1)

F3(A3)

F2(A2)

F1(A1)

v v =⊥

p

i

r est

⊥

v

i

est1

i

= v

i

; r

i

= 0

r

i

= r

i

+ 1

est2

i

= (r

i

, est1

i

)

r

i

, est2

i

n − f r

i

v v

⊥ est1

i

=⊥

v ⊥ est1

i

= v



• 1 ⊥ p

i

v =⊥ r p

j

p

i

r

′

v r

′

≤ r

• p

i

p

j

r

v v

′

(v =⊥) (v

′

=⊥)

v = v

′

• r r est1

est1 = v v ⊥

r

′

r

′

≥ r

• r

r

•

r r v v =⊥

r v p

j

r

v est1

j

= v

v l l > r

v

♦S

r

r ⊥

⊥

⊥ v

r v v

r ⊥

r

i

est1

i

♦S

est1

i

=⊥

est1

i

= prev est1

i

prev est1

i

= est1

i

c = (r

i

n) + 1

(i = c)

r

i

est1

i

r

i

v p

c

p

c

∈ Suspected

i

r

i

v p

c

v

⊥

♦S

r r

♦S

OL OL

i

Lat

p

i

p

j

t

∀(p

i

, p

j

, t) ∈ Π × Π × R

+

, ∃L ∈ R

+

: Lat(p

i

, p

j

, t) = L

Π

Lat(p

i

, p

j

, t

1

) = L

1

Lat(p

k

, p

m

, t

2

) = L

2

(p

i

, p

j

, t

1

) = (p

k

, p

m

, t

2

) L

1

= L

2

t

∀(p

i

, p

j

, t) ∈ Π × Π × N

∗

, ∃L ∈ R

+

: Lat(p

i

, p

j

, t) = L onde,

L

t .

n! n

Aplicação

Oráculo de

Latência

Detector de

Falhas

informação

de latência

lista ordenada de

processos

envia(msg) recebe(msg)

Rede

lista de suspeitos

decide(u)

Protocolo de Consenso

Ordenação de Processos

obtemSuspeitos()

propoe(v)

obtemRTT(pi,pj,t)

obtemOrdemProcessos(idConsenso)

♦S

p

i

p

j

t

p

i

p

j

t =

⊥

inicia

execução K

finaliza

execução K

Seleção

Confirmação

lista ordenada de

processos

Ordenação de

Processos

Detector de

Falhas

propoe(v)

Aplicação

decide(u)

informa

estimativa

de consenso

pergunta

estimativa

de consenso

Execução K

obtemOrdemProcessos(idConsenso)

lista de suspeitos

obtemSuspeitos()

Sequenciador

♦S

•

Emissor

Temporizador

Rede

Falhas

Detector de

suspeita

obtemSuspeitos()

lista de suspeitos

envia(msgDF)

recebe(msgDF)

envia(msgDF)

removeTemporizador()

defineTemporizador()

♦S

Gerenciador de

rtts

Acordo

Oráculo de

Latência

informação de

latência

Rede

recebeDifusao(rtt_j)

recebe(pong)

envia(ping)

enviaDifusao(rtt_i)

propoe(visaoInconsistenteRTT) decide(visaoConsistenteRTT)

obtemRTT(pi,pj,t)

p

i

p

j

t

Oráculo de

Latência

de latência

informação

Ordenação de

Processos

obtemOrdemProcessos(idConsenso)

lista ordenada de processos

obtemRTT(pi,pj,t)

♦S

p

j

p

j

p

j

k

(k +1)

k = 1

p

i

n × n

[i, j]

p

i

p

j

local

i i

global

i

global

i i

estimativ a corrente

i

estimativ a corrente

i

local

i

p

i

Π

i

[i, j]

local

i

Π

i i,j

Π

OL

k

[i, j]

local

k i

global

i

p

i

estimativ a corrente

i

global

i

estimativ a corrente

i

local

i

local

i

global

i

estimativ a corrente

i

k = 1, 2

0 X

i

p

i

k

i

p

i i

k k > 1

propoe(v), onde

v = valor_apl + valor_ol

inicia consenso

atualiza local_i

decide(u), onde

u = decisao_apl + decisao_ol

finaliza consenso

decide(u), onde

u = decisao_apl + decisao_ol

finaliza consenso

0 0 0

propoe(v), onde

v = valor_apl + valor_ol

valor_ol = estimativa_corrente_i

inicia consenso

decide(u), onde

u = decisao_apl + decisao_ol

finaliza consenso

copia

estimativa_corrente_i

para global_i

copia

estimativa_corrente_i

para global_i

atualiza

local_i

estimativa_corrente_i

copia global_i para

estimativa_corrente_i

copia global_i para

0 X1 0

X1 X2 X1

0 X2 X1

0 X1 X1

0 X1 0

CONSENSO k=1

estimativa_corrente_i

CONSENSO k=2

local_iglobal_i

global_i local_i

estimativa_corrente_iglobal_i local_i

estimativa_corrente_i =

decisao_ol

global_i local_i

estimativa_corrente_iglobal_i local_i

estimativa_corrente_iglobal_i

local_i

estimativa_corrente_i =

decisao_ol

global_i

local_i

estimativa_corrente_i

local_i

global_i

estimativa_corrente_iglobal_i local_i

estimativa_corrente_ilocal_iglobal_i

estimativa_corrente_i

global_i local_i

local

i

global

i

estimativ a corrente

i

OL

i

k

global

i

global

i

k = 1

global

i

n − f f n ≥ 2f + 1

i

(n − f) p

i

p

i

i k

p

k

∈ Π 1 ≤ k ≤ n n = |Π|

global

i

5 × 5 Π

e1

= {p

1

, p

2

, p

3

, p

4

, p

5

}

p1 p2 p3 p4 p5

p2

p5

p3

p1

p4

(n−f)−ésimo menor

rtts p5

rtts p4

rtts p2

rtts p3

rtts p1

rtts para pi

{0, 5, 10, 10, 30}

{0, 12, 15, 20, 50}

{0, 5, 10, 50, 70}

{0, 10, 20, 20, 55}

{0, 2, 10, 11, 15}

lista ordenada

de processos

global_i

0 210 15

53010 0 10

5015 20 0 12

70 0 505 10

55 020 10 20

11

{p1, p2, p4, p3, p5}

maioria_rtt1 = 10

maioria_rtt2 = 10

maioria_rtt3 = 15

maioria_rtt4 = 10

maioria_rtt5 = 20

maioria_rtt_i

(n − f)

p

i

p

j

t

Gerenciador de

rtts

informação de

latência

Acordo

Preditor

Rede

enviaDifusao(rtt_i)

envia(ping)

recebeDifusao(rtt_j)

recebe(pong)

latência

Oráculo de

obtemRTT(pi,pj,t)

rtt_i

decide(visaoConsistenteRTT) propoe(visaoInconsistenteRTT)



rtt

t+1

= 2.rtt

st

t

− rtt

nd

t

+

α

1−α

.(rtt

st

t

− rtt

nd

t

)

α = 0.125 rtt

st

t

rtt

st

t

= α.rtt

t

+ (1 − α).rtt

st

t−1

rtt

nd

t

rtt

nd

t

= α.rtt

st

t

+ (1 − α).rtt

nd

t−1

N

Camada n

NekoProcess

send deliver

Camada n

Camada 2

Camada 1

. . .

NekoProcess

Camada 1

Camada 2

Camada n

NekoProcess

. . .

send deliver

processo 0 processo n−1

. . .

APLICAÇÃO

Rede (real ou simulada)

REDES

cria NekoSystem

para mediçãopara simulação

cria NekoSystem

Main

neko.comm.Masterneko.sim.Simulation

cria simulaçao cria mediçao

neko.sim.nekosim.NekoSimSystem

(extends lse.neko.NekoSystem)

neko.comm.NekoCommSystem

(extends lse.neko.NekoSystem)

♦S

t

adj

p

j

p

k

[t

i

, t

f

k

] t

i

t

f

k

p

k

t

i

ms

n = 5

Π

e1

= {p

1

, p

2

, p

3

, p

4

, p

5

} n = |Π

e1

| p

1

100

NekoProcessNekoProcess

consenso−GR ou

consenso−GRA

NekoProcess

send deliver

consenso−GR ou

consenso−GRA

send deliver

processo 0 processo n−1

. . .

APLICAÇÃO

Rede (real ou simulada)

REDES

teste_latencia

apl_frd

teste_latencia

apl_frd

η

δ η = 1000ms δ = 10

12

ms

800ms 80 ms 6000ms 2, 98%

T

λ

T f(t) = λe

−λt

T F(t) = 1 − e

−λt

λ

T E(T ) = 1/λ V (T ) = 1/λ

2

λ = 0, 0 1 9 0 ms

λ = 0, 0 0004 24.700ms

λ = 0, 0013 λ

800ms λ = 1/800

100 100

N

λ

1 ≤ i ≤ 100

c

i,j

p

i

m p

j

m

c

i,j

CPU 1 CPU 2

canal1,2

canal1,3

m2

m3m1

Processo 1

(P1)

Processo 2

(P2)

send(m2,P1,P3)

send(m1,P1,P2)

send(m3,P1,P2)

CPU 3

Processo 3

(P3)

m3m2m1

transmit(m1,P1,P2)

transmit(m3,P1,P2)

REDE

receive(−)

Contenção de cpu

transmit(m2,P1,P3)

100

clt

i

svr

i

clt

i

svr

i

clt

i

svr

i

{A, B, C, D, E}

GRUPO DE

5 MÁQUINAS

máquina−1 máquina−4

máquina−1 máquina−3

máquina−1 máquina−2

máquina−1 máquina−5

máquina−2 máquina−3

máquina−2 máquina−4

máquina−2 máquina−5

máquina−3 máquina−4

máquina−3 máquina−5

máquina−4 máquina−5

máquina−2

máquina−1

máquina−3

máquina−4

máquina−5

CLIENTE SERVIDOR

1 ≤ i ≤ quantidade grupos

1 ≤ j ≤ 5

→

↓

•

→

↓

•

14.400

= lower forth − (f orth spread ∗ 3)

= upper forth + (forth spread ∗ 3)

lower forth =







upper forth =







forth spread = upper forth − lower forth

lower forth = 52, 1

upper

forth = 150

forth

spread = 97, 9

= −241, 6

= 443, 7

[−241, 6; 443, 7] 470

1.000

10.800

14.400

ind = 0 ind = 1

ind = ⌈ /1000⌉ + ind inicial%

ind inicial

ms

0ms ind inicial = 0 = 14.400

= 2ms, 1.400ms, 10.000ms

ind = 0, 2, 10 ind = k

(k + 1) ind = 0

1

o

3 ∗ 120 ∗ 81 ∗ 100 = 2.916.000

subsistema de consenso

carga com picos

carga sem picos

carga de previsao

lista de processos 120

lista de processos 1

trace de rede 1

trace de rede 81

trace da aplicação 100

. . .

trace da aplicação 1

(81) (100)(120)(3)

n amostra

n = t

2

y

S

2

E

2

o

,

S

2

=

1

n amostra − 1

n

amostra



i=1

(x

i

− ¯x)

2

t

y

= ;

.

E

o

=

.

n

amostra = .

S

2

=

.

n amostra = 20

t

y

= 2.093

8.507 ≈ 8.600

n amostra > 30 T

Z

ms

86

8.600

64.714

1 ≤ exp ≤ quantidade experimentos

t ∈

t

64.714 750

95% 5%

ms ± ± ±

9%

16, 4%

max min

76, 1%

200

300

400

500

600

700

800

900

1000

1100

carga_previsãocarga_picoscarga_sem_picos

Média da menor latência de decisão do consenso [ms]

Tipo de carga de rede

consenso−GR

consenso−AGR

p

0

NekoProcessNekoProcess NekoProcess

send deliver

teste_latencia

consenso−GR ou

consenso−GRA

apl_frd

teste_latencia

consenso−GR ou

consenso−GRA

apl_frd

ClockSynchronizerSlave

send deliver

. . .

Rede (real ou simulada)

REDES

ClockSynchronizer

processo 0 processo n−1

APLICAÇÃO

total rodadas

prec

p

i

min rodadas p

i

p

0

total rodadas

30ms

min rodadas = 3 total rodadas = 30

Π

e1

= {p

1

, p

2

, p

3

, p

4

, p

5

}

p

1

p

2

total rodadas

≤ prec min rodadas

[p

4

, p

3

, p

1

, p

2

, p

5

]

p4 p3 p1 p2 p5 p2 p3 p1 p4 p5

p4 p3 p1 p2 p5 p5 p3 p1 p2 p4

p1 p3 p4 p2 p5p4 p3 p1 p2 p5

p3 p4 p1 p2 p5p4 p3 p1 p2 p5

lista de processos

original

p4 p3 p1 p2 p5

95%

5%

[p

1

, p

3

, p

4

, p

2

, p

5

]

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

]

[p

2

, p

3

, p

1

, p

4

, p

5

]

[p

3

, p

4

, p

1

, p

2

, p

5

]

[p

4

, p

3

, p

1

, p

2

, p

5

]

[p

5

, p

3

, p

1

, p

2

, p

4

]

305, 3ms 367, 4ms 16, 9%

241, 6ms 463, 6ms 47, 9%

305, 3ms

367, 4ms 16, 9%

241, 6ms 463, 6ms 47, 9%

5%

v

1

± e

1

v

2

± e

2

(v

1

−e

1

) > (v

2

+ e

2

) v

1

> v

2

(v

1

+ e

1

) < (v

2

−e

2

) v

1

< v

2

[p

3

, p

4

, p

1

, p

2

, p

5

]

219, 0 ± 10, 45 v

1

197, 4 ± 9, 87 v

2

198, 55 < 207, 27 (v

1

− e

1

) < (v

2

+ e

2

)

100

∗

∗ ∗

−3% −21, 3%

7, 1%

∗

9, 8%

ms

∗

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

]

[p

2

, p

3

, p

1

, p

4

, p

5

]

[p

3

, p

4

, p

1

, p

2

, p

5

]

[p

4

, p

3

, p

1

, p

2

, p

5

]

[p

5

, p

3

, p

1

, p

2

, p

4

]

∗

149, 1ms 197, 4 ms

[p

1

, p

3

, p

4

, p

2

, p

5

]

∗

ind = 0 14.400

0 14.400

ind

95%

5%

[p

1

, p

3

, p

4

, p

2

, p

5

]

ind = 0

6, 7% 5%

52, 2% 74%

3, 6% 6, 7% 5%

4, 8% 6, 7% 0, 8% 5, 4%

4, 3% 9, 3% 0, 5%

16%

[p

1

, p

3

, p

4

, p

2

, p

5

]

[p

2

, p

3

, p

1

, p

4

, p

5

]

[p

3

, p

4

, p

1

, p

2

, p

5

]

[p

4

, p

3

, p

1

, p

2

, p

5

]

[p

5

, p

3

, p

1

, p

2

, p

4

]

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

]

[p

2

, p

3

, p

1

, p

4

, p

5

]

[p

3

, p

4

, p

1

, p

2

, p

5

]

[p

4

, p

3

, p

1

, p

2

, p

5

]

[p

5

, p

3

, p

1

, p

2

, p

4

]

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

]

[p

2

, p

3

, p

1

, p

4

, p

5

]

[p

3

, p

4

, p

1

, p

2

, p

5

]

[p

4

, p

3

, p

1

, p

2

, p

5

]

[p

5

, p

3

, p

1

, p

2

, p

4

]

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

]

[p

2

, p

3

, p

1

, p

4

, p

5

]

[p

3

, p

4

, p

1

, p

2

, p

5

]

[p

4

, p

3

, p

1

, p

2

, p

5

]

[p

5

, p

3

, p

1

, p

2

, p

4

]

t

t + t

′

t

0

32

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

]

[p

2

, p

3

, p

1

, p

4

, p

5

]

[p

3

, p

4

, p

1

, p

2

, p

5

]

[p

4

, p

3

, p

1

, p

2

, p

5

]

[p

5

, p

3

, p

1

, p

2

, p

4

]

0 32

0

[p

3

, p

4

, p

1

, p

2

, p

5

]

23, 3%

87, 7%

ms

32

98% →

0% 6%

1

0 32

32

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

] ± ±

[p

2

, p

3

, p

1

, p

4

, p

5

] ± ±

[p

3

, p

4

, p

1

, p

2

, p

5

] ± ±

[p

4

, p

3

, p

1

, p

2

, p

5

] ± ±

[p

5

, p

3

, p

1

, p

2

, p

4

] ± ±

ms ms

[p

1

, p

3

, p

4

, p

2

, p

5

] ± ±

[p

2

, p

3

, p

1

, p

4

, p

5

] ± ±

[p

3

, p

4

, p

1

, p

2

, p

5

] ± ±

[p

4

, p

3

, p

1

, p

2

, p

5

] ± ±

[p

5

, p

3

, p

1

, p

2

, p

4

] ± ±

v

2

±e

2

v

3

±e

3

med med = (v

2

+v

3

)/2±e

med

e

med

= ⌈|med−[(v

2

+e

2

)+(v

3

+e

3

)/2]|⌉

e

med

= ⌈|med − [(v

2

− e

2

) + (v

3

− e

3

)/2]|⌉

40, 3%

45, 4%

1.028, 5ms 11.136, 0ms

130, 3ms 378, 9ms

90, 8% 65, 6%

29, 5%

76, 1%

100

150

200

250

300

350

400

[p5,...,p4][p4,...,p5][p3,...,p5][p2,...,p5][p1,...,p5]

Média da menor latência de decisão do consenso [ms]

Cenários variando a lista ordenada de processos

consenso−GR

consenso−AGR

2000

4000

6000

8000

10000

[p5,...,p4][p4,...,p5][p3,...,p5][p2,...,p5][p1,...,p5]

Média da menor latência de decisão do consenso [ms]

Cenários variando a lista ordenada de processos

consenso−GR

consenso−AGR

95%

5%

76, 1%

32

76, 1%

64.714

5

40, 3% 4 5 , 4%

−23, 3% 87, 7%

•

14

th

4th

13

th

Ω

k

8th

4

th

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 