Algorisme de Chandy-Lamport


Temps lògics i Rellotges vectorialesEditar

Davant la impossibilitat de sincronitzar perfectament els rellotges en un sistema distribuït, no es pot usar en ells el temps físic per obtenir l’ordre de qualsevol succés que passi. Per evitar aquest problema, Lamport suggereix la utilització de temps lògics per aconseguir sincronización.El objectiu és associar a tots els successos una marca de temps independent de l’rellotge físic i poder ordenar-mitjançant relacions “ocorre abans que” .Amb temps lògics, si a passa abans que b, el rellotge és menor, però si el rellotge de a és menor que el de b, no implica que a hagi passat abans que b. Els rellotges vectorials si aconsegueixen fer certes les dues suposiciones.Un rellotge vectorial per a un sistema de N processos és un vector de N enters. Cada procés manté el seu propi rellotge vectorial Vi, on col·loca les seves pròpies marques de temps dels seus successos locals. per compartir-los, hi ha 4 regles bàsiques per actualitzar els rellotges:

  • RV1: Inicialment Vi = 0 per j = 1, 2, …, N.
  • RV2: Abans que passi un esdeveniment en Pi: Vi = Vi + 1.
  • RV3 : Pi inclou el timestamp t = Vaig veure en cada missatge que envia.
  • RV4: Quan Pi té un esdeveniment de recepció amb timestamp t, Vi = max (Vi, t) per j = 1,2, …, N.

Estat global i talls consistentesEditar

Un estat global consistent és aquell que correspon amb un tall consistent. Podem caracteritzar l’execució d’un sistema distribuït com una sèrie de transaccions entre els estats globals de sistema: s0-s1-s2-s3 … a

Tall consistent: si l’esdeveniment de recepció d’un missatge està “dins” de el tall, llavors l’esdeveniment d’enviament del missatge també ha d’estar. Un tall c és consistent si, per a cada succés que conté, també conté tots els successos que “van succeir abans que”.

tall consistent per a rellotges lògics vectorials: Un tall c és consistent si, per a cada procés p, seu rellotge lògic en aquest moment és més gran o igual que els valors que tenen emmagatzemats la resta de processos de l’rellotge de p.

Deixa un comentari

L'adreça electrònica no es publicarà. Els camps necessaris estan marcats amb *