Logické hodiny - Logical clock

A logické hodiny je mechanismus pro zachycení chronologických a kauzálních vztahů v a distribuovaný systém. Distribuované systémy nemusí mít žádné fyzicky synchronní globální hodiny, takže logické hodiny umožňují globální uspořádání událostí z různých procesů v takových systémech. První implementace, Lamport časová razítka, navrhl Leslie Lamport v roce 1978 (Turing Award v roce 2013).

Místní vs globální čas

V systémech logických hodin má každý proces dvě datové struktury: logický místní čas a logický globální čas. Logický místní čas proces používá k označení vlastních událostí a logický globální čas je místní informace o globálním čase. Speciální protokol se používá k aktualizaci logického místního času po každé místní události a logického globálního času, když si procesy vyměňují data.^[1]

Aplikace

Logické hodiny jsou užitečné při výpočtové analýze, návrhu distribuovaného algoritmu, sledování jednotlivých událostí a zkoumání výpočtového pokroku.

Algoritmy

Některé pozoruhodné algoritmy logických hodin jsou:

• Lamport časová razítka, což monotónně zvyšuje softwarové pulty.
• Vektorové hodiny, které umožňují částečné řazení událostí v distribuovaném systému.
• Vektory verzí, objednávat repliky podle aktualizací v optimistický replikovaný systém.
• Matrix hodiny, rozšíření vektorových hodin, které také obsahuje informace o pohledech systému na jiné procesy.

Reference

externí odkazy

• Logický čas distribuovaného systému // Roberto Baldoni, Silvia Bonomi. MIDLAB, Sapienza University of Rome
• Kapitola 3: Logický čas // Ajay Kshemkalyani a Mukesh Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008
• Distribuované systémy 06. Logické hodiny // Paul Krzyzanowski, Rutgers University, podzim 2014