Lamportovy hodiny

Lamport hodiny je softwarová zařízení zavedena v roce 1978 tím, Leslie Lamportem dát každý proces v asynchronním distribuované systémové informace o come-před kauzální vztah . Jedná se o první typ logických hodin zavedených v počítačové vědě.

Zásada

Každý proces má celé číslo zvané časové razítko . Aktualizuje se podle následujících pravidel:

V důsledku toho, pokud jsou dvě události a a b takové, že a → b ( a předchází b ), pak je časové razítko a menší než čas b. Na druhé straně je konverzace falešná. Tyto vektor hodiny plně vystihnout vztah → na úkor vyššího obsazení paměti.

Logické hodiny se používají v mnoha algoritmech, včetně vzájemného vyloučení v případě distribuovaných systémů.

Poznámky a odkazy

  1. (in) Leslie Lamport , „  Čas, hodiny a uspořádání událostí v distribuovaném systému  “ , Komunikace ACM , sv.  21, n o  7,1978, str.  558-565 ( číst online [PDF] )