vektorklockor

Vektorklockor, eller vector clocks, är en mekanism för att spåra kausalitet i distribuerade system. De används för att avgöra om en händelse kan ha orsakat en annan och för att särskilja händelser som är samtidiga eller oberoende av varandra.

Varje process i systemet håller en vektor av heltal som har lika många komponenter som antalet processer som deltar. Varje komponent representerar räknaren för en specifik process. Vid varje lokalt ganska händelse ökar processen sin egen komponent med ett och skickar sedan vektorn tillsammans med meddelandet. Vid mottagandet uppdateras mottagarens vektor genom att ta det elementvis största värdet mellan mottagarens nuvarande vektor och den mottagna vektorn, och sedan ökas den mottagande processens egen komponent med ett för att reflektera mottagningshändelsen.

Följden av händelser kan bedömas genom vektorernas ordning. En händelse A i process P_a föregår en händelse B i P_b om och endast om VC(A) ≤ VC(B) och VC(A) ≠ VC(B) (där ≤ är komponentvis jämförelse). Om inget sådant förhållande mellan två händelser kan fastställas är de concurrenta, dvs. de kan ha upplevts utan kända kausalitet.

Fördelar med vektorklockor inkluderar att de fångar kausalitet exakt och tillåter detektering av samtidiga händelser. De är relativt lätta att implementera i små och medelstora system. Begränsningar är att storleken på vektorn växer med antalet processer och att systemet måste känna till antalet deltagande processer eller hantera dynamiska medlemskap, vilket kan vara mindre praktiskt i mycket stora eller mycket dynamiska miljöer.