Algoritme van Lamport
Van Wikipedia
Wanneer men een gedistribueerd systeem heeft dienen de processen op de verschillende machines met elkaar te communiceren aan de hand van boodschappen. Vermits het onmogelijk is om de kwartskristallen in de klokken van de verschillende computers volgens exact dezelfde frequentie te laten lopen kunnen we nooit zeker zijn dat één proces voor een ander plaatsvindt. Het algoritme van Lamport (door Leslie Lamport, eerste versie van 1978, uitgebreid in 1990) lost dit probleem op door een logische klok te gebruiken.
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 zien we dit pobleem.
Wanneer we nu een logische klok invoeren op dit 2e schema zien we 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 zien we dat we door het invoeren van een logische klok steeds de volgorde van de gebeurtenissen kunnen bepalen.
Wel merken we nog even op dat er in sommige gevallen (zoals hier) een bijkomende eis gesteld wordt dat de gebeurtenissen nooit op hetzelfde logische tijdstip kunnen plaatsvinden. We bekomen dit door de klok steeds met 1 te verhogen.
