Algoritme van Lamport
Het algoritme van Lamport is een door Leslie Lamport bedachte oplossing om klokken van verschillende computers volgens exact dezelfde frequentie te laten lopen. Dit is van belang om in een gedistribueerd systeem de processen op de verschillende machines met elkaar te communiceren aan de hand van boodschappen.
Het op elkaar afstemmen van de klokken is onmogelijk met klokken die werken op kwartskristallen. Lamport loste dit op door een logische klok te gebruiken. Hij bedacht de eerste versie van dit systeem in 1978.
Werking[bewerken | brontekst bewerken]
Het eerste schema stelt 3 processors voor, elk met een eigen klok. Hier wordt het algoritme van Lamport dus nog niet toegepast. Voor de gebeurtenissen A en B is er geen probleem. De verzendtijd is steeds kleiner dan de aankomsttijd en de tijden van gebeurtenis B zijn steeds groter dan deze van A. Gebeurtenis C komt echter toe op tijdstip 24 terwijl de vertrektijd tijdstip 35 aangeeft, dit klopt dus niet, ook bij gebeurtenis D ziet men dit probleem.
Wanneer men nu een logische klok invoert op dit 2e schema, is te zien dat het probleem opgelost is. Bij de gebeurtenissen A en B is er nog steeds geen probleem. Wanneer gebeurtenis C echter toekomt in proces 1 merkt dit proces dat de tijdstippen niet correct zijn. De aankomsttijd wordt vervangen door de verzendtijd + 1 (of hier 35 + 1) en proces 1 past zijn eigen klok aan naar dit nieuwe getal. Analoog voor gebeurtenis D. Nu is ook te zien dat men door het invoeren van een logische klok steeds de volgorde van de gebeurtenissen kan bepalen.
Wel is er nog de kanttekening dat er in sommige gevallen (zoals hier) een bijkomende eis gesteld wordt dat de gebeurtenissen nooit op hetzelfde logische tijdstip kunnen plaatsvinden. Men bekomt dit door de klok steeds met 1 te verhogen.