Algoritmos Distribuídos
3.1 Relógios Físicos
• Porque sincronizar relógios?
Algoritmo de Cristian
Algoritmo de Berkeley
NTP
Atividade
3.2 Relógios Lógicos
Relógios Lógicos
p1
a
b
m1
Physic al
ti me
p2
c
d
m2
p3
e
f
Relógios Lógicos
Relógios Lógicos
Relógios Lógicos
0
1
0
2
0
0
8
10
12
16
20
18
24
24
32
40
30
40
50
36
48
42
56
70
64
80
54
72
90
60
80
100
t = 6
t = 8
6
48
A
D
30
B
60
C
t = 10
Relógios Lógicos
0
1
0
2
0
0
8
10
12
16
20
18
24
24
32
40
30
40
50
36
48
42
61
70
69
80
54
77
90
60
85
100
6
48
t = 6
A
D
t = 8
30
B
60
C
t = 10
Relógios Lógicos
0
1
0
2
0
0
8
10
12
16
20
18
24
24
32
40
30
40
50
36
48
42
61
70
69
80
70
77
90
76
85
100
6
48
t = 6
A
D
t = 8
30
B
60
C
t = 10
Atividade
3.3 Exclusão Mútua Centralizada
Exclusão Mútua - Anel
p
1
p
2
p
n
p
3
p
4
T oken
Exclusão Mútua - Distribuída
Atividade
3.4 Eleição –
Bully
Eleição - Bully
Eleição - Ring
Eleição - Ring
Atividade
3.5 Commit Atômico
• Commit em 1 fase
• Commit em 2 fases
3.5 Commit Atômico
Coordinator
Participant
step
status
step
status
1
prepared to commit
2
prepared to commit
(waiting for votes)
3
committed
canCommit?
Yes
haveCommitted
done
(uncertain)
doCommit
4
committed
Atividade
3.6 Deadlock Distribuído
• Prevenir
• Request ordenado
• Request coletivo
Detecção Centralizada
• Todos informam o serviços sobre suas
esperas
• Quando o servidor detecta ciclo, tem
deadlock
Detecção Distribuída
• Todos informam o próximo sobre suas
esperas
Atividade