CHANDY-LAMPORT para la creacion de SNAPSHOTS

Algoritmo para la creacion de snapshoots es decir 'registrar' una foto del estado de cada proceso y cada canl en un entorno sin relog global que es lo normal en sistemas distribuidos.

1. Elecicion del iniciador Pi graba su propio estado.
2. El iniciador genera un mensage especia llamado "Marker" o marcador.
3.  for j=1 to N except i Pi 
1. se envia el mensaje a cada Cij canal (N-1) canalse.
4. Se empieza a grabar por cda uno de los canales de entrada a Pi Cji (j <> i)
5.  Si un proceso Pi recibe un marker por un canal Cki
1. if( es el prmer Marker)
• Pi graba su propio estado y marca Cki como vacio.
2. for j=1 to N exceto i y  K(o sea todos los demas)
• Pi envia un Marker a un canal de salida Cik. 
• Se empieza a grabar por cda uno de los canales de entrada de Pi Cki excepto i,k.
6. else ya se ha recibido un mensaje asi que el se marca el canal Cki y se graban todos los mensages desde que se empezo a grabar Cki y se envian al concetrdor.

Aunque parece lioso basicamente consiste en enviar una señala un canal y el que escucha por ese canal empieza a grabar ese canal. Despues transmte markadores a los otros procesos para que hagan lo mismo. el tema para cuando todos los canales han recibido señal y cada canal se detiene cuando recibe un marcador de ese canal, al final se recogen los mensages intermedios  y se recolectan.

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.