8212700
Description
Mind Map by KAREN DE LA CRUZ, updated more than 1 year ago
|
Created by KAREN DE LA CRUZ
almost 8 years ago
|
|
ALGORITMO DE ELECCION
- DEFINICION
- Son algoritmos diseñados para problemas
en los cuales uno de los procesos ha de
realizar una tarea especial: Elección de un
coordinador
- Estos mecanismos se activan cuando el
coordinador ha fallado.
- Estos mecanismos se activan cuando el
coordinador ha fallado.
- Son algoritmos diseñados para problemas
en los cuales uno de los procesos ha de
realizar una tarea especial: Elección de un
coordinador
- OBJETIVO
- Elección única
- Dentro de estos algoritmos
encontramos las siguientes
elecciones:
- ALGORITMO EN ANILLO
- Sobre un anillo lógico de procesos
se emite un mensaje de elección
- Cuando un proceso recibe un
mensaje de elección compara el
identificador recibido con el suyo.
- –Si es menor el recibido y el
proceso no es un participante,
sustituye el identificador en el
mensaje por el suyo y lo
reenvía al vecino y se marca
como participante.
- – Si es mayor el
recibido, reenvía el
mensaje y se marca
como participante.
- – Si es menor el recibido y el
proceso es un participante,
no hace nada (no envía
ningún mensaje).
- –Si el identificador
coincide con el del
proceso, ese proceso es
el líder.
- ESQUEMA DEL ALGORITMO DEL ANILLO
- EJEMPLO DIDACTICO
https://www.youtube.com/watch?v=ZjDbvdwBV4M
- –Si es menor el recibido y el
proceso no es un participante,
sustituye el identificador en el
mensaje por el suyo y lo
reenvía al vecino y se marca
como participante.
- Cuando un proceso recibe un
mensaje de elección compara el
identificador recibido con el suyo.
- Sobre un anillo lógico de procesos
se emite un mensaje de elección
- ALGORITMO DE INVITACIÓN
- DEFINICION
- • Se basan en timeouts: Retrasos de
transmisión pueden causar la
elección de múltiples líderes.
- La pérdida de conexión entre dos
grupos de procesadores puede aislar
permanentemente los procesadores
- La pérdida de conexión entre dos
grupos de procesadores puede aislar
permanentemente los procesadores
- • Se basan en timeouts: Retrasos de
transmisión pueden causar la
elección de múltiples líderes.
- CARACTERISTICAS
- • Definición de grupos de
procesadores con líder
único.
- • Detección y agregación
de grupos
- • Reconocimiento por
parte del líder de los
miembros del grupo.
- • Reconocimiento por
parte del líder de los
miembros del grupo.
- • Detección y agregación
de grupos
- • Definición de grupos de
procesadores con líder
único.
- PASOS
- • Si un procesador detecta
la pérdida del líder,
entonces se declara líder y
forma su propio grupo.
Periódicamente el líder de
cada grupo busca otros
líderes de otros grupos.
- • Dos grupos se unen por
medio de mensajes de
aceptación: - Como respuesta
a mensajes de invitación. – De
forma explícita
- • Dos grupos se unen por
medio de mensajes de
aceptación: - Como respuesta
a mensajes de invitación. – De
forma explícita
- • Si un procesador detecta
la pérdida del líder,
entonces se declara líder y
forma su propio grupo.
Periódicamente el líder de
cada grupo busca otros
líderes de otros grupos.
- ESQUEMA DEL ALGORITMO DE INVITACION
- DEFINICION
- ALGORITMO DEL
MATÓN
- DEFINICION
- Este algoritmo es Tolerante a caídas de
procesos durante la elección:
- – pi conoce a los
que tienen
mayor id
- – pi puede
comunicarse con
cualquier proceso
- – pi conoce a los
que tienen
mayor id
- Este algoritmo es Tolerante a caídas de
procesos durante la elección:
- MENSAJES
- – Election. Para
iniciar una
elección.
- – Answer.
Respuesta un
mensaje Election.
- – Coordinator.
Mensaje para
anunciar al líder
- – Election. Para
iniciar una
elección.
- Algoritmo se inicia cuando pi
detecta caída (timeout) del
líder.
- – Pi inicia la elección enviando
un mensaje Election a todos los
que tienen pid > pi, y espera
algún mensaje Answer.
- – Si ninguno de ellos responde,
entonces pi supone que él tiene
mayor id, y envía un mensaje
Coordinador auto-anunciándose
como nuevo líder
- – Si pi recibe un Answer de lo
que tiene pid > pi, entonces
espera un tiempo T para que
´ese proceso se anuncie como
líder. De lo contario reenvía el
mensaje Election.
- Si pi recibe un Election de un
pid < pi, entonces responde
con un Answer, e inicia una
nueva elección.
- Si pi recibe un Election de un
pid < pi, entonces responde
con un Answer, e inicia una
nueva elección.
- – Si pi recibe un Answer de lo
que tiene pid > pi, entonces
espera un tiempo T para que
´ese proceso se anuncie como
líder. De lo contario reenvía el
mensaje Election.
- – Si ninguno de ellos responde,
entonces pi supone que él tiene
mayor id, y envía un mensaje
Coordinador auto-anunciándose
como nuevo líder
- – Pi inicia la elección enviando
un mensaje Election a todos los
que tienen pid > pi, y espera
algún mensaje Answer.
- DEFINICION
- ALGORITMO EN ANILLO
- Elección única
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.