Блог

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

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

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

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

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

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

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

1. Если ‘a’ и ‘b’ являются событиями одного и того же процесса, и ‘a’ происходит перед ‘b’, то a -> b имеет значение true.

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

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

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