lamporttidsklokker

Lamport-tidsklockor, eller Lamportklokor, är en mekanism för att tilldela händelser i ett distribuerat system ett logiskt tidsstämplvärde som kan användas för att bestämma en delvis ordning mellan händelser baserad på begreppet “happens before”. De introducerades av Leslie Lamport 1978 och är enkla att implementera utan synkronisering av verklig tid. I en sådan lösning hålls en lokal räknare i varje process.

Hur de fungerar: vid varje händelse inom en process ökas den lokala räknaren med ett. När ett meddelande skickas bifogas det aktuella värdet av räknaren som tidsstämpel. När mottagaren tar emot meddelandet uppdaterar den sin egen räknare till max(nuvarande värde, mottaget tidsstämplingsvärde) och ökar sedan med 1 för att registrera mottagelsehändelsen. På så sätt får varje händelse i varje process ett stigande heltal.

Följder och tolkning: om en händelse A påverkar kallat B (A happens before B), så är Lamport-tidsstämpeln L(A) strikt mindre än L(B). Detta ger en total ordning per process men säkerställer inte en global total ordning över alla processer. Händelser som inte är causally relaterade (konkurrenta) kan få valfria ordningar, vilket innebär att tidsstämplarna inte kan avgöra deras verkliga inbördes relation.

Användningsområden och begränsningar: Lamport-tidsklockor används för att ordna händelser i loggar, rekonsiliering i distribuerade databaser och felsökning där en enkel logisk tidsreferens räcker. De fångar dock inte hela den injicera partial-ordningen mellan samtidiga händelser; för att fånga denna fullständiga relation används ofta vektortidsstämplar som ger en bättre bild av kopplingar mellan händelser. Lamport-klockor saknar koppling till verklig tid och är inte avsedda att exakt mäta kronologiska tider över olika noder.