О распределенных логических часах, алгоритме Лампорта

Привет всем, я хотел бы спросить о логических часах в распределенной системе. Алгоритмы Лампорта определяют, что когда события a в процессе Pi отправляют сообщение, а события b в процессе Pj получают это сообщение, тогда можно определить, что события a произошли до b. Предположим, что до того, как процесс Pj получил сообщение в событиях b, в Pj произошли события c (таким образом, c произошло до b) и он отправил сообщение процессу Pi, а затем процесс Pi получил сообщение в событиях d после события a, тогда мы имеем событие c , как и а, произошло до d.

Мой вопрос: как определить связь между событием a (первое событие произошло в процессе Pi) и событием c (первое событие произошло в процессе Pj)? Как позволить процессам Pi и Pj согласовать порядок событий a и c?

Алгоритм Лампорта: http://en.wikipedia.org/wiki/Lamport_timestamps


synchronization logic distributed-system clock
person Hawker    schedule 15.10.2011    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Ответ прост. Основываясь на алгоритме Лампорта, вы не можете определить какие-либо отношения между событиями a и c. Все, что мы знаем, это:

a -> b и c -> d и a -> d и c -> b

но вы не можете заключить ни a -> c, ни c -> a вот и все.

person Gupta    schedule 08.11.2011

arrow_upward
0
arrow_downward

Важно, чтобы процессы совпадали в том порядке, в котором происходят события. Для синхронизации логических часов Лэмпорт определил отношение, называемое предыдущим вхождением. Выражение a -> b читается как a предшествующее b. Эту взаимосвязь возникновения можно увидеть в 2 ситуациях:

  1. Если «a» и «b» являются событиями одного и того же процесса, и «a» происходит раньше «b», то истинно a -> b.

  2. Если 'a' — это событие, при котором процесс отправляет сообщение, а 'b' — это событие получения сообщения другим процессом, то a->b также верно.

Как работает алгоритм?

Каждое сообщение имеет время отправки отправителя. Таким образом, приемник изменяет время, если его время меньше времени передатчика. Таким образом, алгоритм синхронизирует часы получателя. Каждое сообщение, отправленное другому процессу, будет содержать единицу времени, в течение которой сообщение было отправлено, и, таким образом, часы проверяются.

person Pineda Hernández Isaac Jair    schedule 10.07.2021