Usuario:Maritza1902/Multidifusión ordenada

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 garantizan 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

• Ordenación FIFO

Si un proceso difunde un mensaje m₁ y luego un mensaje m₂, estos se deberán entregar en el orden en el que fueron enviadas por el emisor, es decir, siempre se entregará m₁ antes que m₂.

• Ordenación causal

Si la difusión de un mensaje m₁ ocurre causalmente antes que la difusión de un mensaje m₂, entonces un proceso correcto entregará m₁ antes que m₂.

• Ordenación total

Si dos procesos correctos P_i y P_j entregan dos mensajes m₁ y m₂, entonces P_i entrega m₁ antes que m₂sí y solo sí P_j entrega m₁ antes que m₂.ç

Implementación de la ordenación FIFO

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:

• S_g^p contador de mensajes que el proceso p ha enviado al grupo g
• R_g^q 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 S_g^p en el mensaje
• Realiza B-multicast del mensaje al grupo g
• Incrementa S_g^p en 1 -> S_g^p = S_g^p + 1

Cuando p recibe un mensaje de q:

• Si S = R_g^q+1 → se comprueba que es el mensaje esperado y p usa OF-entrega fijando R_g^q = S

• Si S > R_g^q+1 → retención del mensaje hasta que los mensajes intermedios hayan sido entregados y se cumpla S = R_g^q+1​

Implementación de la ordenación causal

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 p_i tiene su propio vector de marcas temporales.

Multidifusión ordenada causal

Variables en el proceso p

V_p^g 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 p_j, 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:

• P_j espera hasta que haya entregado todo mensaje enviado por parte de p_j
• P_i espera a que cualquier mensaje que p_j 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:

1. 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.

1. Multidifusión ordenada total por acuerdo (ISIS)

Variables para el proceso q:

A_g^q: mayor número de secuencia acordado para el grupo g n Pgq: mayor número de secuencia propuesto para el grupo g

P_g^q: mayor número de secuencia propuesto para el grupo g

Multidifusión ordenada total ISIS

Implementación

p hace B-multicast<m,i> a g (i identificador único de m)

Cada proceso q responde a p con una propuesta P_g^q =máx(A_g^q, P_g^q )+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 A_g^q = máx(A_g^q, 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

• 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