Usuario:Maritza1902/Taller
La multidifusión como gestión adecuada para la comunicación a grupos requiere de una infraestructura de soporte (middleware) en el cual se identifiquen los grupos, se entregue los mensajes a todos los miembros. Además de garantizar la fiabilidad y el orden de entrega de los mensajes.
El algoritmo de multidifusión fiable sobre IP-multicast no garantiza que los mensajes lleguen siempre en el mismo orden y esto puede ser un problema para las aplicaciones que requieren un orden.
Los tipos de ordenación más frecuentes son la ordenación total, causal y la ordenación FIFO.
Tipos de ordenación
[editar]- Ordenación FIFO Si un proceso difunde un mensaje m1 y luego un mensaje m2, estos se deberán entregar en el orden en el que fueron enviadas por el emisor, es decir, siempre se entregará m1 antes que m2.
- Ordenación causal Si la difusión de un mensaje m1 ocurre causalmente antes que la difusión de un mensaje m2, entonces un proceso correcto entregará m1 antes que m2.
- Ordenación total Si dos procesos correctos Pi y Pj entregan dos mensajes m1 y m2, entonces Pi entrega m1 antes que m2sí y solo sí Pj entrega m1 antes que m2.ç
Implementación de la ordenación FIFO
[editar]Una multidifusión con ordenación FIFO tiene dos operaciones: OF-Multicast y OF-Entrega.
Se utilizarán las siguientes variables en el proceso P:
- Sgp contador de mensajes que el proceso p ha enviado al grupo g
- Rgq número de secuencia del último mensaje que p ha recibido del proceso q enviado al grupo g
Cuando se realiza la operación OF-multicast de p para el grupo g
- Adjuntar Sgp en el mensaje
- Realiza B-multicast del mensaje al grupo g
- Incrementa Sgp en 1 -> Sgp = Sgp + 1
Cuando p recibe un mensaje de q:
- Si S = Rgq+1 → se comprueba que es el mensaje esperado y p usa OF-entrega fijando Rgq = S
- Si S > Rgq+1 → retención del mensaje hasta que los mensajes intermedios hayan sido entregados y se cumpla S = Rgq+1[1]
Implementación de la ordenación causal
[editar]Este algoritmo tiene en cuenta la relación “sucedió antes que" y se emplean las operaciones de ordenamiento causal: OC-multicast y OC-entrega, cada proceso pi tiene su propio vector de marcas temporales.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b7/Orden_casual.png/220px-Orden_casual.png)
Variables en el proceso p
[editar]Vpg vector con el no de mensajes recibidos de cada proceso
Para enviar un mensaje mediante OC-multicast al grupo g, el proceso suma 1 a su entrada en el vector de marcas temporales y envía el mensaje mediante B-multicast a g junto con su marca de tiempo.
Cuando un proceso pi B-entrega un mensaje pj, tiene que colocarlo en la cola de retención antes de realizar la OC-entrega: primero debe asegurarse de haber entregado todos los mensajes que sucedieron antes, esto se comprueba de las siguientes maneras:
- Pj espera hasta que haya entregado todo mensaje enviado por parte de pj
- Pi espera a que cualquier mensaje que pj hubiese entregado hasta el instante de tiempo en el que envió el mensaje.
Implementación de la ordenación total
La manera básica de implementar la ordenación total es asignar identificadores totalmente ordenados a los mensajes que se multidifunden de tal forma que todo proceso realice la misma ordenación basada en esos identificadores.
Existen dos métodos para asignar identificadores a los mensajes:
- Secuenciador
El proceso elegido como secuenciador es el encargado de ordenar los mensajes.
Cuando un proceso desea enviar un mensaje m con OT-multicast este se envía al secuenciador.
El secuenciador le asigna un número de secuencia de forma creciente y consecutiva a los mensajes que B-entrega y lo envía a todos los procesos del grupo.
El secuenciador anuncia la secuencia de números mediante B-multicast al grupo g de mensajes con el ordenamiento.
Un mensaje permanecerá retenido en la cola indefinidamente hasta que pueda efectuarse OT-entrega de acuerdo con el correspondiente número de secuencia.
- Multidifusión ordenada total por acuerdo (ISIS)
Variables para el proceso q:
Agq: mayor número de secuencia acordado para el grupo g n Pgq: mayor número de secuencia propuesto para el grupo g
Pgq: mayor número de secuencia propuesto para el grupo g
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Multidifusi%C3%B3n_ordenada_total_ISIS.png/220px-Multidifusi%C3%B3n_ordenada_total_ISIS.png)
Implementación
[editar]p hace B-multicast<m,i> a g (i identificador único de m)
Cada proceso q responde a p con una propuesta Pgq =máx(Agq, Pgq )+1
- Se asigna al mensaje m el no de secuencia Pgq de modo provisional
- Se coloca y ordena en la cola de retención según ese no provisional
p recoge todos los números de secuencia propuestos y selecciona el mayor (a) como acordado
- Cada proceso fija Agq = máx(Agq, a) y se lo asigna al mensaje i
- Reordena la cola si difiere al propuesto
- Cuando el mensaje al inicio de la cola tenga no acordado, se entrega
Bibliografía
[editar]- AUTORES, VARIOS (2015). «15. Coordination and Agreement». ''Distributed Systems, Concepts and Design'' (en inglés) (5ª edición). Pearson pp. 646-660 ISBN 978-1-4479-3017-4.
- Sistemas Distribuidos - Coordinación y Acuerdo
- Alberto Lafuente, Mikel Larrea. UPV- EHU Comunicación a grupos
- Rodrigo Santamaría. Apuntes Sistemas Distribuidos Universidad de Salamanca. Tema 5 - Coordinación y acuerdo
- ↑ Coulouris, George F. (2012). Distributed systems : concepts and design. Addison-Wesley / Pearson Education Ltd. ISBN 978-1-4479-3017-4. OCLC 899731054. Consultado el 27 de junio de 2020.