Sr-6-wyk-1.0-Slajd17
Znaczniki czasu Lamporta
Znaczniki czasu Lamporta zostały opracowane jako sposób pomiaru czasu logicznego. Każdemu zdarzeniu a przypisana jest pewna wartość czasu C(a ). Jeżeli weźmiemy dwa zdarzenia a i b , przy czym a poprzedza zdarzenie b , to powinna zachodzić nierówność C(a )< C(b ).
W podejściu Lamporta wykorzystano bezpośrednio koncepcję relacji uprzedniości zdarzeń. Każdy wysłany komunikat zawiera czas swojego nadania. Odbiorca, który odbierze wiadomość porównuje czas jej nadania z własnym czasem. Jeśli zegar odbiorcy wskazuje czas mniejszy od czasu nadania komunikatu, przesuwa swój zegar w przód do wartości równej czasowi nadania powiększonej o pewną wartość d . Dodanie d wymusza postęp czasu pomiędzy każdą parą zdarzeń.
Rozszerzeniem tego algorytmu jest dodanie po przecinku do każdej wartości zegara np. numeru procesu. Robi się tak, gdyż w normalnych warunkach dwa zdarzenia mogłyby posiadać znaczniki czasowe o tej samej wartości. Dodatkowa informacja pozwala na rozróżnienie zdarzeń. Na przykład zdarzenie, które wystąpiło w procesie 4 w chwili gdy wartość jego zegara logicznego wynosiła 120, będzie oznaczone znacznikiem (120, 4).
Zegar Lamporta spełnia kilka ważnych warunków. Jeżeli a poprzedza b , to C(a )< C(b ). Należy pamiętać, że implikacja taka nie zachodzi w odwrotną stronę. Algorytm Lamporta całkowicie porządkuje wszystkie zdarzenia w systemie.
