Algoritme de Chandy-Lamport

El algoritme de Chandy-Lamport és un algoritme d'instantànees per a sistemes asíncronos desenrollat per Leslie Lamport i K. Mani Chandy.

L'algoritme de Chandy-Lamport s'utilisa en sistemes distribuïts en l'objectiu d'obtindre una instantànea (conjunt d'estats de procés i canal de comunicació) global i consistent per a registrar-ho com un estat global consistent. L'estat global es construïx a partir de l'iniciativa d'un procés qualsevol del sistema distribuït (iniciador). El mateix Leslie Lamport arreplega en la seua pàgina web cóm va sorgir l'idea, citant textualment en la seua pàgina web personal: "L'algoritme d'instantànees distribuïdes que es descriu ací va sorgir quan vaig visitar a Chandy, que llavors estava en l'Universitat de Texas en Austin. Em va plantejar el problema durant el sopar, pero abdós vàrem tindre massa va vindre per a pensar-ho en eixe moment. Al matí següent, en la ducha, se'm va ocórrer la solució. Quan vaig aplegar a l'oficina de Chandy, ell m'estava esperant en la mateixa solució."

Consideracions Prèvies

Temps llògics i Rellonges vectorials

Davant l'impossibilitat de sincronisar perfectament els rellonges en un sistema distribuït, no es pot usar en ells el temps físic per a obtindre l'orde de qualsevol succés que ocórrega. Per a evitar este problema, Lamport sugerix l'utilisació de temps llògics per a conseguir sincronisació. L'objectiu és associar a tots els successos una marca de temps independent del rellonge físic i poder ordenar-los per mig de relacions “ocorre abans que”. En temps llògics, si a succeïx abans que b, el rellonge és menor, pero si el rellonge de a és menor que el de b, no implica que a haja ocorregut abans que b. Els rellonges vectorials sí conseguixen fer certes abdós suposicions. Un rellonge vectorial per a un sistema de N processos és un vector de N sancers. Cada procés manté el seu propi rellonge vectorial Vaig vore, a on coloca les seues pròpies marques de temps dels seus successos locals. Per a compartir-los, existixen 4 regles bàsiques per a actualisar els rellonges:

• RV1: Inicialment Vaig vore[j]=0 per a j=1, 2, …, N.
• RV2: Ans que ocórrega un event en Pi: Vaig vore[i]=Vaig vore[i]+1.
• RV3: Pi inclou el timestamp t=Vaig vore en cada mensage que envia.
• RV4: Quan Pi té un event de recepció en timestamp t, Vaig vore[j]=max(Vaig vore[j], t[j]) per a j=1,2,…,N.

Estat global i corts consistents

Un estat global consistent és aquell que correspon en un tall consistent. Podem caracterisar l'eixecució d'un sistema distribuït com una série de transaccions entre els estats globals del sistema: s0-s1-s2-s3…

Cort consistent: si l'event de recepció d'un mensage està “dins” del tall, llavors l'event d'enviament de dit mensage també deu estar. Un tall c és consistent si, per a cada succés que conté, també conté tots els successos que “varen succeir abans que”.

Cort consistent per a rellonges llògics vectorials: Un tall c és consistent si, per a cada procés P, el seu rellonge llògic en eixe moment és major o igual que els valors que tenen almagasenats el restant de processos del rellonge de P.

Precondiciones

L'algoritme supon que:

• No fallen ni els canals ni els processos: la comunicació és fiable per lo que tots els mensages es reben intactes i una única volta.
• Els canals són unidireccionals en entrega de tipo FIFO.
• El grafo dels processos i canals està fortament conectat, hi ha canal de comunicació directa entre tots els estats.
• Qualsevol procés pot prendre una instantànea global en qualsevol instant.
• Mentres té lloc una instantànea els processos poden continuar la seua eixecució i comunicació.

Referències

• Chandy, K. M., & Lamport, L. (1985). Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems (TOCS), 3(1), 63-75.[1]
• Archivat el 11 de maig de 2018 archivat en Wayback Machine.
• Tel, G. (2000). Introduction to Distributed Algorithms (2ª ed.). New York: Cambridge University Press.

• Coulouris, G. (2001). Sistemes distribuïts: Conceptes i dissenys. (P. de la F. Redó & C. L. Bell, Trads.) (Edició: 3). Madrit: ADDISON WESLEY.
• Rodrigo Santamaría. Apuntes Sistemes Distribuïts Universitat de Salamanca. | Tema 4 - Temps i Estats