TRABAJO

04 - Algoritmos Distribuidos
IIC2523 - Sistemas Distribuidos
Cristian Ruz – cruz@ing.puc.cl
Departamento de Ciencia de la Computaci´
on
Pontificia Universidad Cat´
olica de Chile

Semestre 1-2013

C.Ruz (PUC)

IIC2523

1/2013

1 / 115

Contenidos
1

Estados Globales y Tiempo
Relojes, eventos y estados
Sincronizaci´on de Relojes
Relojes y Vectores L´
ogicos
EstadosGlobales

2

Exclusi´on Mutua y Consenso
Exclusi´on Mutua Distribuida
Elecci´on y Consenso

3

Transacciones

4

Tolerancia a Fallas y Replicaci´
on

C.Ruz (PUC)

IIC2523

1/2013

2 / 115

Algoritmos Distribuidos

Conceptos fundamentales algor´ıtmicos
Independiente de tecnolog´ıas particulares
Modelo de ejecuci´on particular:
Se ejecutan en procesadores independientesToman decisiones basados en informaci´
on local
No poseen toda la informaci´
on del sistema
No hay una fuente precisa de tiempo global

C.Ruz (PUC)

IIC2523

1/2013

3 / 115

Estados Globales y Tiempo

Contenidos
1

Estados Globales y Tiempo
Relojes, eventos y estados
Sincronizaci´on de Relojes
Relojes y Vectores L´
ogicos
Estados Globales

2

Exclusi´on Mutua y ConsensoExclusi´on Mutua Distribuida
Elecci´on y Consenso

3

Transacciones

4

Tolerancia a Fallas y Replicaci´
on

C.Ruz (PUC)

IIC2523

1/2013

4 / 115

Estados Globales y Tiempo

La importancia del tiempo

Para muchas aplicaciones es importante conocer el tiempo en que se
ejecut´o alguna instrucci´on (o evento).
Timestamps para:
Consistencia
Sincronizaci´
on
Prevenci´on de duplicados
Compilaci´
on autom´atica (make)
...

C.Ruz (PUC)

IIC2523

1/2013

5 / 115

Estados Globales y Tiempo

Necesitamos medir el tiempo

Pero no es tan f´acil medir el tiempo, ¿por qu´e?
Teor´ıa Especial de la Relatividad
Observaciones de eventos son relativas
Dos eventos simult´aneos en un marco de referencia no lo son
necesariamenete para observadores en otromarco de referencia.

Entonces, ¿nada que hacer?
Dos eventos pueden ser vistos en distintos orden por distintos
observadores.
Al menos para eventos independientes
¿Y si uno provoca el otro?
El tiempo entre causa y efecto puede variar, pero no el orden.

C.Ruz (PUC)

IIC2523

1/2013

6 / 115

Estados Globales y Tiempo

Pero estamos hablando de computadores . . .
. . . que noviajan a la velocidad de la luz

¿C´
omo generar timestamps precisos en nodos distintos?
Para dos eventos e1 , e2 ,
¿cu´al ocurri´o primero?
¿ocurrieron “simult´aneamente”?
¡No hay un reloj global!
Sin embargo,. . . los algoritmos funcionan . . .
Dos problemas
Sincronizar relojes usando paso de mensajes
Observaci´
on del estado global de un sistema distribuido

C.Ruz (PUC)

IIC25231/2013

7 / 115

Estados Globales y Tiempo

Relojes, eventos y estados

Modelo

Consideramos un sistema distribuido como una colecci´on P de N procesos
pi , con i = 1, 2, . . . , N.
Cada proceso pi ejecuta en un procesador independiente
Suponemos que no hay memoria compartida
S´
olo se comunican por paso de mensajes: send y recv

Cada proceso pi tiene un estado si que cambiadurante la ejecuci´on.
Evento
Ocurrencia de una acci´on individual
send, recv u otra acci´on que cambie el estado del pi

C.Ruz (PUC)

IIC2523

1/2013

8 / 115

Estados Globales y Tiempo

Relojes, eventos y estados

Historia

Los eventos dentro de pi poseen un orden total, definido por la relaci´on →i
Relaci´on ocurre antes
e1 →i e2 ⇔ e1 ocurre antes que e2 en pi .
Ahora esposible definir la historia del proceso pi
Historia de pi
Serie de eventos que ocurren en pi definidos por la relaci´on →i
history (pi ) = hi = ei0 , ei1 , ei2 , . . .

C.Ruz (PUC)

IIC2523

1/2013

9 / 115

Estados Globales y Tiempo

Relojes, eventos y estados

Relojes
¿Y c´
omo se asignan esos timestamps?

CPUs poseen relojes f´ısicos
Objetivo: medir el tiempo real t...