Sistemas
Distribuidos
Algoritmos de Coordinación
Florentino Salazar García
Cinvestav, Tamaulipas
Instituto Politécnico Nacional
Cd. Victoria, Tamaulipas
Introducción
O Para alcanzar sus objetivos, los Sistemas
Distribuidos
O cuentan con formas especificas de
coordinación entre procesos.
(Preprocesamiento)
O Sincronización de reloj (clock synchronization)
O Construcción de un árbol de expansión
No son inherentes a los objetivos del
negocio.
Introducción
¿Qué?
P1
P5
P2
¿Cómo?
P3
P4
Contenido
O Se abordarán dos técnicas (tipos de
algoritmos) de coordinación.
O Elección de líder (lider election)
O Sincronizadores (synchronizers)
Elección de líder
(Algoritmos de Elección)
O «De un conjunto determinado de procesos, uno
es elegido como líder, y le son asignadas
responsabilidades especiales necesarias para
los demás procesos del sistema.»
O Cada proceso activo, P, tiene un identificador, i
(prioridad), en el Sistema Distribuido.
O El líder será el proceso con la mayor prioridad.
O El líder es siempre el centro de control.
P1
P2
Elección
Pi
P4
P3
O El objetivo del algoritmo de elección:
O asegurar que cuando se comience una
elección, se concluya con que todos los
procesos están de acuerdo en cuál es el
nuevo líder.
Ejemplo: DBMS centralizado.
Elección de un nuevo líder
P1
P2
Elección
P3
Pi
Pj
Elección de líder != Exclusión mutua
O Similitud
O Interés: Elegir a uno de los procesos como
privilegiado (cualquier proceso que entre a la
sección crítica).
O Diferencias
O EM; Los algoritmos trabajan en ausencia de fallos.
EL: Es lo que inicia una nueva elección.
O El problema de «Starvation» es irrelevante en EL.
O EL; no requiere que el proceso líder salga de la
sección crítica. Contrario a EM.
O EL; el líder debe informar a cada proceso activo
sobre su identidad, lo cual no es un problema en
EM.
Algoritmo Bully (matón)
(García-Molina)
O Trabaja en una red completamente
conectada.
O Los enlaces de comunicación están libres
de fallos.
O Los procesos pueden fallar solamente si se
detienen (o se caen) (only by stopping).
O Las fallas pueden ser detectadas mediante
el uso de timeout.
Algoritmo Bully (matón)
(García-Molina)
O El algoritmo usa 3 diferentes tipos de
mensaje:
O «election»: Un proceso inicia una elección con
este mensaje. («¿Puedo ser el líder?»).
O «reply»: Es una respuesta al mensaje de
elección. («No, no puedes ser el líder»).
O «leader»: Un proceso envía este mensaje
cuando cree ser el nuevo líder.
Algoritmo Bully (matón)
(García-Molina)
1.
2.
3.
4.
Cualquier proceso, después de detectar una falla del líder,
solicita ser el nuevo líder enviando un mensaje «election» a
cada proceso con un identificador mayor.
Si cualquier proceso con identificador mayor responde un
«reply», entonces el proceso solicitante desiste. Espera un
«leader» («Soy el lider») por parte de un proceso con un
identificador mayor.
Si ningún proceso con identificador mayor responde con un
«reply» al mensaje «election» enviado por el proceso i,
entonces el proceso i se elije líder y envía un mensaje
«leader» a cada proceso en el sistema.
Si el proceso i recibió un «reply» a su mensaje «election» y no
recibe un «leader» en un periodo predeterminado (timeout),
entonces el proceso i deduce que el proceso ganador falló y
reinicia la elección.
Complejidad del algoritmo Bully
 3
Topología de anillo
(Maxima Finding on a Ring)
O El problema ahora se reduce a eficientar la
búsqueda del proceso con el identificador
(único) mínimo o máximo, según convenga.
O A diferencia del algoritmo Bully, los
siguientes algoritmos no requieren de un
grafo completamente conectado.
Algoritmo Chang-Roberts
(Fase 1)
1.
2.
3.
4.
5.
Se asume una topología de anillo unidireccional (izquierda).
Inicialmente, todos los procesos son «no participante».
Si un proceso detecta una falla del líder actual, inicia una elección.
Envía un mensaje de elección con su ID a su vecino izquierdo.
Cada vez que un proceso envía o pasa un mensaje de elección, éste
se marca como «participante».
Cuando un proceso recibe un mensaje de elección, compara el ID en
el mensaje con el suyo:
1.
2.
3.
4.
Si el identificador en el mensaje es mayor, el proceso sólo lo pasa a
su vecino izquierdo.
Si el identificador en el mensaje es menor, y el proceso aún no es
«participante», éste reemplaza el ID del mensaje por el suyo y lo
envía a su vecino izquierdo.
Si el identificador en el mensaje es menor, y el proceso ya es
«participante», éste descarta el mensaje de elección.
Si el ID en el mensaje es igual al del proceso que lo recibe, ese
proceso comienza a actuar como el líder.
Algoritmo Chang-Roberts
(Fase 2)
O Cuando un proceso inicia a actuar como el líder,
éste inicia la segunda fase del algoritmo.
1. El líder se marca como «No Participante» y
envía un mensaje «elected» a su vecino
izquierdo, indicando su elección y su ID.
2. Cuando un proceso recibe un mensaje
«elected», se marca como «no participante»,
almacena el ID del proceso líder y pasa
mensaje «elected» tal cual lo recibió.
3. Cuando el mensaje «elected» alcanza al nuevo
proceso líder, éste lo descarta, y la elección
termina.
Complejidad
Chang-Roberts Vs Bully
Bully:  3
Chang-Roberts:  2
Algoritmo de Franklin
O Trabaja en un anillo bidireccional.
O Complejidad de mensaje menor que la de
O
O
O
O
Chang-Roberts.
Procesos con identificadores únicos están
organizados en un orden arbitrario en el anillo.
Cada proceso puede ser, rojo o negro.
Inicialmente cada proceso es rojo.
El algoritmo es síncrono y trabaja en rounds.
Algoritmo de Franklin
Cada proceso rojo envía un mensaje con su ID
a sus dos vecinos y
2. Examina los mensajes que le fueron enviados
por sus vecinos.
1.
1.
2.
Si el proceso i recibe un mensaje con un ID
mayor que el suyo, i abandona la competencia y
se vuelve negro. (sólo pasará mensajes).
El algoritmo termina cuando sólo hay un
proceso rojo en todo el sistema, el nuevo líder.
Complejidad
Chang-Roberts Vs Bully Vs Franklin
Bully:  3
Chang-Roberts:  2
Franklin:   log 
Algoritmo de Franklin
P0
Round 0
Round 1
P5
P2
P2
P2
P7
P1
P7
P1
P7
P6
P1
P9
P9
P9
Nuevo líder: P9
P3
Pi
Sincronizadores
(Synchronizers)
O Modelos asíncronos: difícil de tratar en
aplicaciones reales. (ej., Ex. Mutua, Hilos).
O Es más simple escribir algoritmos en
modelo de procesado síncrono. (lock-step
synchrony).
O Es más fácil probar que son correctos (ej.,
debugging)
O Sincronizadores: transforman un modelo
asíncrono en uno síncrono.
Sincronizadores
(Synchronizers)
O Los algoritmos distribuidos se diseñan con mayor
facilidad en una red síncrona.
O El cómputo se realiza en pasos discretos, round o ticks.
O En cada tick, un proceso puede;
O Recibir mensajes de sus vecinos
O Realizar cálculos locales
O Enviar mensajes a sus vecinos
O Sincronizador: protocolo que transforma un modelo
asíncrono en un modelo de proceso síncrono.
O Simulando los ticks en una red asíncrona.
O Las acciones del algoritmo síncrono son programadas
(scheduled) para ser ejecutadas en los ticks apropiados.
Sistema listo para ejecutar la versión síncrona del
algoritmo distribuido.
Sincronizadores
(Synchronizers)
O Sin importar como se simulen los ticks, un
sincronizador debe asegurar:
O Cada mensaje envíado en tick k debe ser
recibido en el tick k.
El sincronizador ABD
(Asynchronous Bounded Delay)
O Cada proceso tiene un reloj físico.
O El retardo de propagación de mensaje tiene un límite
superior conocido, d.
O c, denota el reloj físico del proceso.
O Uno o más procesos inicializan el reloj, c=0.
O Ejecutan las acciones para el tick 0, y envían una
señal de start a sus vecinos.
O Cada vecino despierta y cuando recibe la señal de
start, inicializa su reloj en 0 y ejecuta las acciones
para el tick 0.
O Antes de ejecutar las acciones del tick (i+1), todos
los procesos deben enviar y recibir todos los mensaje
correspondientes al tick i.
Sincronizador de Awerbuch
O Cuando los relojes físicos no están
sincronizados.
O El límite superior del retardo de propagación
de mensaje se desconoce.
O Sincronizador a,b,g.
O Complejidad de mensaje: b < a
O Complejidad temporal: a < b
O g es una combinación de las anteriores.
Descargar

Ch11 - Cinvestav