II Escuela de Verano en Matemáticas Discretas ISCV

ELECCIÓN FUTURA DE LÍDER EN SISTEMASDISTRIBUIDOS NO FIABLES

II Escuela de Verano en MatemáticasDiscretas

ISCV-Universidad de ChileAntonio Fernandez

[email protected]

Universidad Rey Juan Carlos

– p.1/52

Sistema distribuido

Un sistema distribuido es una colección dedispositivos de computación que pueden comunicarseentre sí.

• Definición muy general. Incluye desde chips hastala Internet, pasando por los multiprocesadores.

• Nos centraremos en sistemas distribuidosdébilmente acoplados: ordenadores que secomunican a través de una red.

– p.2/52

Modelo de sistema distribuido

En esta presentación vamos a suponer que tenemosun sistema distribuido con paso de mensajes, formadopor:• Un conjunto de n procesos/procesadores,

Π = p0, ..., pn−1. Pueden fallar.• Canales de comunicación bidireccionales que

unen cada par de procesos. Pueden no ser fiableso ser lentos.

• Programas ejecutados por los procesos.Dichos programas envian y reciben mensajesusando los canales.

– p.3/52

Niveles de sincronía

A efectos de diseño de algoritmos, se pueden suponervarios niveles de sincronía en el sistema distribuido:• Sistema asíncrono: Los procesos del sistema

avanzan a cualquier velocidad (> 0) y losmensajes que intercambian pueden sufrir retardosarbitarios ( 6=∞).

Muy general: modela muy bien Internet.Veremos que hay problemas que no se puedenresolver en este modelo.

– p.4/52

Niveles de sincronía

• Sistema síncrono: La mínima velocidad de avancede los procesos y el máximo retardo de losmensajes están acotados y las cotas sonconocidas.

Evolución del sistema como rondas síncronas: (envíode mensajes, recepción de mensajes, cómputo local).

– p.5/52

Fall@s

Vamos a suponer que los procesos pueden fallar:• Fallos de parada: Un proceso que falla

simplemente deja de avanzar. Si estaba enviandomensajes a otros procesos, puede que algunos sehayan enviado y otros no.Aquí suponemos este tipo de fallo.

• Fallos de parada/recuperación: Un proceso que separa se recupera más adelante. Puede conservaro no (parte de) su estado.

• Fallos bizantinos: El comportamiento de unproceso fallido no está limitado. Sucomportamiento puede ser malicioso.

– p.6/52

Elección de líder

Problema a resolver: elección de líder:• Todos los procesos se ponen de acuerdo en un

mismo proceso líder.• El líder es un proceso correcto.

Dos versiones (al menos) del problema:• Elección de líder, versión “clásica".• Elección futura de líder (eventual leader election).

Aquí estudiaremos principalmente esta versión.

– p.7/52

Elección de líder: definición

Elección de líder [García-Molina 1982] [Sabel,Marzullo 1995]:• Cada proceso pi tiene una variable

leader i ∈ true, false.• Acuerdo: Nunca hay dos líderes (procesos pi y pj

con leader i = leader j = true).

• Terminación: Para todo instante t sin líder, tarde otemprano (∃t′ > t) algún proceso pℓ acaba porestablecer leader ℓ = true.

– p.8/52

Elección de líder: aplicaciones

Observaciones:• No puede haber nunca más de un líder.• El líder pℓ es elegido en el momento en que se

pone leader ℓ = true.

Aplicaciones:• Elección de un primario en sistemas

primario/secundarios.• Secuenciador para obtener order total.• Coordinador para exclusión mutua.

– p.9/52

Elección de líder: algoritmo

Se apoya en un servicio de difusión (bcast) quegarantiza:• Integridad: Un mensaje entregado fue enviado por

algún proceso.• No duplicados: No se entrega el mismo mensaje

más de una vez.• Viveza sin fallos: Un mensaje enviado por un

proceso correcto es recibido por todos losprocesos correctos.

– p.10/52

Elección de líder: algoritmo

Sistema asíncrono sin fallos y con canales fiables.Cada proceso sabe inicialmente su identificador y eltamaño n.

Algoritmo elección de líder: (código para proceso pi)leader i ← falsebcast(i)receive n messagesif (i is the smallest ID in the n messages) then

leader i ← true

¿Qué ocurre si hay fallos?

– p.11/52

Elección futura de líder: aplicaciones

Hay aplicaciones en las que no son necesarias lasrestricciones anteriores:• Es admisible tener varios líderes a la vez.• No es necesario saber cuándo el líder ha sido

elegido.

Ejemplos:• Red de sensores transmitiendo a una estación

externa.• Detector de fallos para resolver el problema del

consenso.• Algoritmos indulgentes.

– p.12/52

Elección futura de líder: definición

Elección futura de líder [Chandra, Hadzilacos,Toueg1996]:• Cada proceso pi tiene una variable leader i ∈ Π.• Terminación: Tarde o temprano todo procesos

correcto pi tiene leader i = pℓ permanentemente,donde pℓ es un proceso correcto.

Esta es la definición de la clase de electores futuros de

líder, que se suele denotar por Ω.

– p.13/52

Interés de Ω

Historia:• Fischer, Lynch y Paterson (1985) demuestran que

no es posible resolver consenso en un sistemaasíncrono con fallos.

• Chandra y Toueg (1991, 1996) introducen losdetectores de fallos como oráculos que permitenresolver consenso en sistemas asíncronos.

• Chandra, Hadzilacos y Toueg (1992, 1996)demuestran que Ω es la clase de detectores de“fallos"más débil que permite resolver consensoen sistemas asíncronos.

– p.14/52

Problemas de acuerdo: Consenso

Es muy común en aplicaciones distribuidas que variosprocesos se tengan que poner de acuerdo.Ejemplos:• Bases de datos replicadas que deben acordar el

orden en que realizan los cambios para mantenerla coherencia.

• Sistemas transaccionales que deben decidir sicomprometer o abortar una transacción.

Estos problemas no son sencillos si hay fallos.El problema de acuerdo más popular es el problemade consenso (consensus).

– p.15/52

Problema de consenso: definición

En una instancia del problema de consenso cadaproceso pi propone un valor vi (con una llamadapropose(vi)) y tarde o temprano cada proceso correctodecide el mismo valor v (con decide(v)).Formalizando:• Terminación: Todo proceso correcto decide en

algún momento.• Acuerdo: Dos procesos correctos no deciden

valores diferentes.• Validez: El valor decidido debe ser uno de los

propuestos.

– p.16/52

Consenso en sistemas asíncronos

Teorema 1 ([FLP 1985]). No hay ningun algoritmo que resuelvaconsenso en un sistema asıncrono con f ≥ 1 fallos de parada.

• Intuición: No es posible distinguir un proceso lentode uno fallido.

• Se empieza demostrando el resultado para 2procesos p0 y p1.

• Generalizamos por simulación para n procesos.

– p.17/52

Cómo vencer el resultado FLP

Varias opciones hasta el momento:• Sincronía parcial: El sistema no es completamente

asíncrono.• Aleatorización: No se alcanza consenso con

probabilidad 1.• Detectores de fallos: Oráculos que dan

información acerca de los procesos que hanfallado. Ocultan la sincronía.

– p.18/52

Consenso vs elección de líder

Sistema asíncrono con fallos y canales fiables.• Elección de líder no se puede resolver en un

sistema asíncrono con fallos.• Teniendo un “módulo"de consenso no obtenemos

elección de líder.• Teniendo un elector de tipo Ω y una mayoría de

procesos correctos podemos resolver consenso.• Elección de líder requiere un detector de fallos

más fuerte que Ω: Elección de líder es más“duro"que consenso.

– p.19/52

Servicio de difusión fiable

Problema en un sistemas asíncrono con fallos deparada, la difusión fiable (reliable broadcast):• Un proceso pi puede invocar el servicio como

Rbcast(i,m), donde m es un mensaje.• El servicio entrega el mensaje m con una

operación Rdeliver(m).

– p.20/52

Definición de difusión fiable

Propiedades que debe cumplir el servicio (algoritmo):• Integridad: Un mensaje entregado fue enviado por

algún proceso.• No duplicados: No se entrega el mismo mensaje

más de una vez.• Viveza sin fallos: Un mensaje enviado por un

proceso correcto es recibido por todos loscorrectos.

• Viveza con fallos: Un mensaje enviado por unproceso que falla es recibido por todos loscorrectos o por ninguno.

– p.21/52

Algoritmo para difusión fiable

Observa que no basta con que pi envíe m a todos yluego lo entregue él:• Si falla puede que algunos procesos correctos lo

reciban y entreguen y otros no.

Es necesario que un proceso que reciba m porprimera vez lo redistribuya antes de entregarlo.

– p.22/52

Algoritmo para difusión fiable

Algoritmo difusión fiable: (código para proceso pi)

when function Rbcast(m) is invoked:

bcast(i,m)

Rdeliver(m)

when message (j,m) is received:

if (i 6= j and message m was not already received) then

bcast(j,m)

Rdeliver(m)

– p.23/52

Corrección

Teorema 2. El algoritmo implementa difusion fiable.

• Integridad y viveza sin fallos: Garantizados por lasemántica de bcast si el emisor es correcto.

• No duplicados: Un proceso sólo entrega elmensaje m la primera vez que lo manipula.

• Viveza con fallos: Si un proceso correcto entrega,difunde con bcast . Entonces por la semántica debcast todos los correctos entregan.

– p.24/52

Consenso con Ω

Presentamos un algoritmo que resuelve consenso enun sistema asíncrono:• El algoritmo usa un elector de tipo Ω con interfaz

leader().• Los canales son fiables.• Hay una mayoría de procesos correctos: f < n/2.

Tomado de [Mostefaoui, Raynal 2001].

– p.25/52

Algoritmo consenso: fase 1

Algoritmo consenso con Ω: (código para proceso pi)

when function propose(vi) is invoked:

start T1 and T2;

Task T1:

est i ← vi

ri ← 0

loop forever

bcast(P1, ri, est i)

wait until (leader() = pℓ ∧ (P1, ri, v) received from pℓ)

est i ← v

– p.26/52


bcast(P2, ri, est i)

wait until ((P2, ri, v) received from n− f processes)

if (the same value v received from a majority) then

aux i ← v

else

aux i ← NIL

end if

bcast(P3, ri, aux i)

wait until ((P3, ri, aux ) received from n− f processes)

– p.27/52


if ((P3, ri, aux ) received with aux = v 6= NIL) then

est i ← v

end if

if ((f + 1) messages (P3, ri, aux ) with aux 6= NIL) then

Rbcast(DECIDE, est i) ; stop T1

end if

end loop

Task T2: when Rdeliver(DECIDE, v):

decide(v) ; stop T2

– p.28/52

Corrección

Teorema 3. El algoritmo resuelve consenso.

• Validez: est i sólo toma valores propuestos.• Terminación: Ningún proceso correcto se bloquea.

Cuando el elector se estabiliza se decide (si noantes).

• Acuerdo: Si se decide v en una ronda r:• Todos los que deciden en esa ronda deciden v.• Todas las variables est i = v al final de la ronda.

– p.29/52

Implementación de Ω

No se puede implementar un elector final de líder enun sistema asíncrono (ni con canales fiables).• El caso para f < n/2 es consecuencia directa de

FLP y el algoritmo anterior.• Se puede demostrar la imposibilidad para

cualquier f > 0.

Hay que imponer alguna restricción adicional al siste-

ma.

– p.30/52

Canales parcialmente síncronos

Un canal es síncrono futuro si existen dos parámetrosT y ∆ desconocidos tal que:• Hasta el instante T el canal no da garantías. Por

ejemplo, todos los mensajes se pueden perder ollegar tarde.

• A partir de T , un mensaje enviado en un instante tse entrega como tarde en instante ∆.

– p.31/52

Implementando Ω sobre canalessíncronos futuros

Suponemos procesos síncronos y canales síncronosfuturos. [Chandra, Toueg 1996].

Algoritmo elector 1: (código para proceso pi)

leader i ← i

tout i ← η

set timer to tout i

start T1 and T2;

Task T1:

repeat every η time

bcast(HBEAT)

end repeat

– p.32/52

Implementando Ω sobre canalessíncronos futuros

Task T2:

when received HBEAT from pj and j < leader i:

leader i ← j

tout i ← tout i + 1

reset timer to tout i

when timer expires:

leader i ← i

set timer to tout i

– p.33/52

Corrección del algoritmo

Consideremos instante t > T en que todos losprocesos que van a fallar lo han hecho:• Los latidos del proceso correcto con identificador

más pequeño, pℓ, llegan como mucho cada η + 2∆.• Si la variable tout i no alcanza ese valor es que

deja de incrementarse. Entonces, tras recibir unHBEAT de pℓ, leader i = ℓ.

• Si la variable alcanza ese valor, no se incrementamás, y tras recibir un HBEAT de pℓ, leader i = ℓ.

– p.34/52

Análisis del algoritmo

• Todos los procesos envían mensajepermanentemente.

• En un sistema sin fallos se usan n2 canalespermanentemente.

• En realidad basta con que sea pℓ quien mandemensajes y sus canales de salida sean síncronosfinales.

– p.35/52

Implementación más eficiente de Ω

Canales de salida de pℓ son síncronos futuros. [Larreaet al. 2000].


leader i ← 0

. . .

Task T1:


if (leader i = i) then

send HBEAT to processes pi+1, ..., pn−1

end if

end repeat

– p.36/52

Implementación más eficiente de Ω

• Demostración de corrección es similar a laanterior, notando que llega un momento en queleader ℓ = ℓ permanentemente.

• Como mucho n− 1 canales tienen que sersíncronos futuros y son usados permanentemente.

• Si f = n− 1, esta cota es óptima.• Si f < n− 1 es conocido, se puede reducir, ya que

hay al menos un proceso correcto entre los f + 1primeros procesos.

– p.37/52

Mínima sincronía para implementar Ω

Sistema con procesos síncronos, y canales síncronosfuturos y asíncronos con pérdidas (sin garantías).Propiedad 1. Al menos un proceso correcto puede alcanzar losdemas procesos correctos a traves de caminos de canalessıncronos futuros y procesos correctos.

Teorema 4 ([Fernandez et al 2006]). Para poder implementar unelector de tipo Ω, un sistema con canales sıncronos futuros yasıncronos con perdidas debe satisfacer la Propiedad 1.

– p.38/52


• Supongamos que hay un algoritmo A queimplementa el elector en un sistema más débil.

• Considera una ejecución R sin fallos en que todoslos mensajes en canales con pérdidas se pierden:• Se elige a pℓ como líder.• Algún proceso pi no recibe nada de información

de pℓ.• Considera una ejecución R′ en que pℓ falla pero

que desde el punto de pi es igual que R. pi elige apℓ permanentemente como líder.

– p.39/52


Algoritmo que implementan un elector de tipo Ω bajoestas condiciones mínimas de sincronía.


leader i ← i

∀j ∈ Π:

suspect i[j]← η

set timer i[j] to suspect i[j]

start T1 and T2 ;

Task T1:


Rbcast(suspect i)

end repeat– p.40/52

Algoritmo de sincronía mínima

Task T2:

when Rdeliver(suspect j) from pj :

suspect i[k]← max(suspect i[k], suspect j [k]),∀k ∈ Π

leader i ← argmink(suspect i[k], k)

reset timer i[j] to suspect i[j]

when timer i[j] expires:

suspect i[j]← suspect i[j] + 1



– p.41/52


Teorema 5. El algoritmo implementa un elector de tipo Ω en unsistema con canales sıncronos futuros y asıncronos con perdidasque satisface la Propiedad 1.

Lema 1. Dado un proceso correcto pi y un proceso pj que falla,suspect i[j] crece sin cesar.

Para cada proceso correcto pi, definimos

Vi = suptsuspect i[i](t).

Lema 2. Dado un proceso correcto pi que satisface la Propiedad1, Vi <∞.

– p.42/52


Sea B = pi : Vi <∞.Lema 3. Hay un tiempo tras el cual, para todo proceso pj ∈ B ytodo proceso pi que satisface Propiedad 1, se tienesuspect i[j] = Vj .

• A partir de un instante, pi debe recibir Rdeliver depj periódicamente, ya que timer i[j] expira unnúmero acotado de veces.

• El primero que reciba con suspectj [j] = Vj

establecerá el valor.• Tras ese momento el valor no se modifica.

– p.43/52


Sea ℓ = argmini(Vi, i).Lema 4. Hay un tiempo tras el cual, para todo proceso correcto pj

tal que j /∈ B, y todo proceso pi que satisface Propiedad 1 setiene suspect i[j] > Vℓ.

• Una vez suspect j [j] > Vℓ hay dos casos:• pi recibe algún Rdeliver de pj. Entonces

actualiza suspect i[j] > Vℓ.• Si no, expirará timer i[j] hasta que

suspect i[j] > Vℓ.

– p.44/52


Lema 5. Dado un proceso pi que satisface Propiedad 1, el valorde suspect i[j],∀j es continuamente propagado a todos losprocesos correctos.

Como consecuencia, pℓ es elegido líder por todos los

procesos correctos tarde o temprano.

– p.45/52

Variables acotadas

¿Qué ocurre si?Task T2:

when Rdeliver(suspect j) from pj :

...

when timer i[j] expires:

if (j = leader i) then

suspect i[j]← suspect i[j] + 1


end if


– p.46/52

Líneas activas de investigación

• Conocimiento de f .• Condiciones no basadas en temporizadores

(orden de los mensajes).• Comportamiento de los canales variable con el

tiempo.• Desconocimiento de la composición del sistema.• Sistemas con memoria compartida.• Fallos de parada y recuperación.

– p.47/52

Problemas abiertos

• ¿Se puede obtener consenso sobre elección delíder?

• Otros modelos de fallos. Ej: Sistemas con fallos yrecuperaciones.

• Sistemas con composición variable y/odesconocida.

• Implementación eficiente de detectores de fallosen todos los modelos.

• Sistemas reales: MANET, P2P, Internet.• Ver actas de PODC y DISC.

– p.48/52

Consenso en sistemas asíncronos

Teorema 6 ([FLP 1985]). No hay ningun algoritmo que resuelvaconsenso en un sistema asıncrono con f ≥ 1 fallos de parada.

• Intuición: No es posible distinguir un proceso lentode uno fallido.

• Se empieza demostrando el resultado para 2procesos p0 y p1.

• Generalizamos por simulación para n procesos.

– p.49/52

Imposibilidad para 2 procesos

Para 2 procesos p0 y p1:• Ejecución R0 en que p1 falla al inicio y p0 propone

0.• p0 decide 0 tras un tiempo t0.• Ejecución R1 en que p0 falla al inicio y p1 propone

1.• p1 decide 1 tras un tiempo t1.• En una ejecución R2 en que ningún mensaje llega

antes de max(t0, t1), ambos deciden diferente y seviola acuerdo.

– p.50/52

Imposibilidad para n procesos

Panorámica de la demostración para n procesos:• Algoritmo A que resuelve consenso para n > 2

procesos.• Simulamos con p0 y p1 el comportamiento de los n

procesos (virtuales) ejecutando A con laspropuestas de p0 y p1.

• Si un proceso real falla sólo bloquea la ejecuciónde uno virtual.

• Los procesos reales deciden lo mismo que losvirtuales: Simulación resuelve consenso para 2procesos.

– p.51/52

Imposibilidad para n procesos

Detalles de la simulación:• Ambos p0 y p1 simulan los n virtuales.• pi simula un “paso” de uno virtual, difunde el

nuevo estado y pasa al siguiente proceso virtual.• Si p1−i ya ejecutó un paso, pi no lo re-ejecuta:

obtiene el estado.• Un mismo paso lo pueden ejecutar p0 y p1:

prevalece el nuevo estado calculado por p0.• En cuanto un proceso virtual decide, pi lo hace.

– p.52/52

Documents

II Escuela de Verano en Matemáticas Discretas ISCV