Embed Size (px)
Citation preview
Sistemas Distribuidos
Algoritmos de Coordinación
Florentino Salazar GarcíaCinvestav, Tamaulipas
Instituto Politécnico NacionalCd. Victoria, Tamaulipas
IntroducciónO Para alcanzar sus objetivos, los
Sistemas DistribuidosO 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
P1
P5 P
2
P3
P4
¿Qué?
¿Cómo?
ContenidoO 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
P3
PiElección
Notificación+identificador
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.
P4
P1 P2
P3
PiElección
Notificación
+identificador
Pj
Elección de un nuevo líder
Elección de líder != Exclusión mutua
O SimilitudO Interés: Elegir a uno de los procesos como
privilegiado (cualquier proceso que entre a la sección crítica).
O DiferenciasO 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.
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)
Algoritmo Bully (matón)(García-Molina)
1. 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.
2. 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.
3. 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.
4. 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. Se asume una topología de anillo unidireccional (izquierda).2. Inicialmente, todos los procesos son «no participante».3. 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.4. Cada vez que un proceso envía o pasa un mensaje de elección,
éste se marca como «participante».5. Cuando un proceso recibe un mensaje de elección, compara el ID
en el mensaje con el suyo:1. Si el identificador en el mensaje es mayor, el proceso sólo lo pasa a
su vecino izquierdo.2. 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.
3. Si el identificador en el mensaje es menor, y el proceso ya es «participante», éste descarta el mensaje de elección.
4. 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
Chang-Roberts:
Bully:
Algoritmo de FranklinO Trabaja en un anillo bidireccional.O Complejidad de mensaje menor que la de
Chang-Roberts.O Procesos con identificadores únicos están
organizados en un orden arbitrario en el anillo.
O Cada proceso puede ser, rojo o negro.O Inicialmente cada proceso es rojo.O El algoritmo es síncrono y trabaja en
rounds.
Algoritmo de Franklin1. Cada proceso rojo envía un mensaje con
su ID a sus dos vecinos y2. Examina los mensajes que le fueron
enviados por sus vecinos.1. 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).
2. 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:
Chang-Roberts:
Franklin:
Algoritmo de Franklin
P0
P2
P1
P3P9
P6
P7
P5
PiP1
P1
P0
P2
P2
P3
P3P9 P
9
P6 P6
P7
P7
P5
P5
P0
P7
P9 P9
Round 0
Round 1
Nuevo líder: P9
P7
P2
P2
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 vecinosO Realizar cálculos localesO 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, .dO 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 gO Complejidad de mensaje: < b aO Complejidad temporal: < a bO g es una combinación de las anteriores.
