5 Coordinación

+

Sistemas Distribuidos
Coordinación y acuerdo
Caleb Betancourt

+ Coordinación y acuerdo
• 
• 
• 
• 
• 

Introducción
Exclusión mutua distribuida
Elección distribuida
Multidifusión
Consenso distribuido

2

+

3

Introducción
n 

Dado un conjunto de procesos en un SD, vamos a necesitar
n 
n 

n 

Formas de coordinación y acuerdo
n 
n 
n 
n 

n 

Coordinar sus acciones
Llegar a un acuerdo enuno o más valores

Acceso a recursos: exclusión mutua distribuida
Selección de líderes: algoritmos de elección
Comunicación distribuida: algoritmos de multidifusión
Toma de decisiones: algoritmos de consenso

Hay que tener en cuenta
n 
n 

Sincronismo (timeouts conocidos) o asincronismo
Fallos: en un sistema asíncrono, es imposible garantizar el acuerdo si
hay cualquier tipo de fallo

+

4Introducción
Asunciones respecto a fallos (canales)
n 

Asumimos canales de comunicación fiables
n 
n 
n 

n 

Siempre terminan enviando los mensajes
En un sistema síncrono, además con un límite de tiempo
El fallo de un proceso no evita que el resto puedan comunicarse

Algunas otras características que no consideraremos
n 
n 
n 
n 

Asimetría: la comunicación es posible de p a q, pero no al revésIntransitividad: comunicación posible de p a q y de q a r, pero
no de p a r
Partición de red: ha fallado un router y la comunicación es
posible a ambos lados, pero no entre ambos lados
Estas características y otras son propias de redes punto a punto
como Internet

+

5

Introducción
Asunciones respecto a fallos (procesos)
n 

Los proceso fallan por caídas o arbitrariamente

n 

Proceso correcto
n 

n Aquél que no muestra fallos en ningún punto de la ejecución

Detector de fallo
n 

Objeto local a cada proceso que ejecuta un algoritmo de detección
de fallos en colaboración con sus equivalentes en otros procesos

n 

Detector no fiable: sospechoso/no sospechoso de haber fallado

n 

Detector fiable: fallido/no sospechoso

n 

Detección inexacta: sospechar de un proceso que no ha fallado

n Detección incompleta: no sospechar de un proceso que ha fallado

+

6

Introducción
Implementación de un detector de fallos
El proceso p envía “estoy aquí” cada T unidades de tiempo?
(D=estimación del tiempo máximo de transmisión de un mensaje)?
Si q no recibe de p un mensaje “estoy aquí” tras T+D?
p pasa a ser sospechoso para q?

n 

Elección de D
n 
n 
n 

n 

Demasiado pequeño à sobrecarga en lared
Demasiado grande à lentitud en detectar procesos sospechosos
Posible opción: elección de timeouts adaptativos que reflejen las
condiciones de tráfico/retraso observadas en la red

En sistemas síncronos (D conocido), esta implementación da
lugar a un detector fiable

+ Coordinación y acuerdo
• 
• 
• 
• 
• 

Introducción
Exclusión mutua distribuida
Elección distribuida
Multidifusión
Consensodistribuido

7

+

8

Exclusión mutua distribuida
n 

Sección crítica (SC): porción de código que permite el
acceso a un recurso compartido por varios procesos

n 

Exclusión mutua: el acceso a la sección crítica se regula por
medio de variables compartidas, por ejemplo semáforos

n 

Exclusión mutua distribuida: el acceso a la sección crítica
se basa en paso de mensajes

n 

Asunciones
n 
n 
n n 

Sistema asíncrono
Los procesos no fallan
La entrega de mensajes es fiable
Los procesos acceden a los recursos a través de una SC

+

9

Exclusión mutua distribuida
Algoritmo básico

1. 

entrarSC()

// bloqueo del proceso si SC ocupada

2. 

accesoRecursos() // uso de recursos compartidos

3. 

salirSC()

// liberación de procesos bloqueados

+

10

Exclusión mutua distribuida
Requisitos
n EM1: Seguridad
n 

n 

A lo sumo un proceso puede estar ejecutándose a la vez en la SC

EM2: Pervivencia
n 

Las peticiones de entrada/salida de la SC al final son concedidas
n 

n 

Sin interbloqueos ni inanición

EM3: Ordenación
n 

Si una petición para entrar en la SC ocurrió “antes que” otra,
entonces la entrada en la SC se garantiza en ese orden

+

11

Exclusión mutua distribuida
Criterios...