Multicast conceptos y soluciones

MULTICAST CONCEPTOS

A FIFO ordered. 

Los mensajes enviados por el mismo transmisor son entregados en el orden en que se enviaron. O sea, si un proceso multicast un mensage m antes de otro m' entonces ningn proceso recibe m' a menos que haya recibido previamente m. 

CAUSAL Orden. 

Es una dependencia entre eventos. (Por eventos se entienden envió y recepción de mensajes or ejecución interna en un proceso). Es como una relación de orden.

Se dice que a -> b si.

1º Un proceso ejecuta a primero y luego b.

2º O  si b es el receptor de un mensaje m enviado por a.

3º o si hay un evento h  en medio que actúa transitivamente es decir a-> h y h->b.

Lema

Si hay Causal Orden entonces ha FIFO Orden.

TOTAL Ordering Si dos procesos p y p' reciben ambos mensajes m y m' entonces p recibe m antes de m' si y solo si q recibe m antes que m'. También se le llama Atomic Multicast.

IMPLEMENTACION FIFO

 Sea Pj[i] una matriz  1 <= i <= N.

• Si Pj envia un multicast  actualiza Set Pj[j] = Pj[j] + 1
• Si Pi recibe un mensage de Pj con un numro S enonces
•  if (S == Pi[j] + 1) entrega el mensage.
• else buffer el multicast hasta que la condicion sea cierta.  

O sea que se espera hasta que acabe los previos multicast m y entonces se lee el mensage.

TOTAL ORDERING

Sea Pi  escogido como un proceso 'lider' que mantiene un sequence.
global, cada Pj j<>i mantiene uno loca.
 
El Lider o Sequencer:

• Maitiene a global sequence number S (valor inicial a0)
• Cuando recibe un Mensage M aumenta S++ y hace multicast del par <M,S> a los demas procesos.

El receptor o los otros procesos:

Manitenen una copia del valor recibido. Si Pi recibe un multicas M de Pj espera con buffer hasta que recibe el valor del <M,S(M)> y si Si= 1+S(M) entonces se entrega el mensage y se actualiza Si = Si+1;

Remarks el par <M,S> implica que el mensage M se envia dos veces.