Введение в распределенные

Полностью упорядоченная групповая рассылка. Обратимся теперь к рассмотренной в п. 1.5.3 задаче полного упорядочивания сообщений групповой рассылки. Пусть существует группа процессов, рассылающих друг другу широковещательные сообщения, которые требуется доставить всем процессам данной группы, включая отправителей этих сообщений, причем в порядке, одинаковом для всех процессов. Каждую такую рассылку будем рассматривать как одно атомарное событие соответствующего процесса, и будем считать, что все каналы обладают свойством FIFO.
Чтобы обеспечить единый для всех процессов порядок доставки широковещательных сообщений можно воспользоваться механизмом скалярных часов Лэмпорта, позволяющим задать линейный порядок на множестве событий рассылки этих сообщений. В этом случае останется лишь убедиться, что каждый процесс имеет необходимую информацию о событиях рассылки, происходящих в других процессах. Для этого каждый процесс локально поддерживает очередь, в которую помещает все принимаемые широковещательные сообщения и упорядочивает их по возрастанию значений отметок времени, содержащихся в этих сообщениях. Затем сообщения доставляются одно за другим по порядку из очереди каждого процесса. Здесь под отметкой времени сообщения m будем подразумевать упорядоченную пару (L(m), i), где L(m) – логическое время события рассылки этого сообщения, i – идентификатор процесса- отправителя. Линейный порядок таких отметок времени будет определяться правилом, введенным в п. 3.2.1.
Следует обратить внимание, что из-за задержек передачи сообщений, возможна ситуация, когда в начале очередей двух различных процессов будут находиться разные сообщения от разных отправителей. Эта ситуация проиллюстрирована на рис. 3.4. Локальная очередь каждого процесса изображена прямоугольником рядом с его временной осью. Видно, что имеется некоторый временной интервал, в течение которого сообщение m₁ уже получено процессами P₁ и Р₂, а сообщение m₂ – процессами Р₃ и P₄, но оба сообщения еще не дошли до остальных процессов данной группы. В течение этого временного интервала процессы Р₁ и Р₂ считают, что первым в очереди является сообщение m₁, а процессы Р₃ и Р₄ считают, что первым является сообщение m₂. При этом процессам, уже получившим широковещательное сообщение, не ведомо, направлено ли им еще какое-либо сообщение, и стоит ли ждать его прихода. Поэтому прежде чем процесс примет решение о доставке сообщения m, стоящего в начале его собственной очереди, он должен получить гарантии, что в каналах не осталось ни одного сообщения с отметкой времени меньшей, чем отметка времени сообщения m. Благодаря свойству FIFO каналов связи это условие будет выполнено, когда процесс получит сообщения от всех остальных процессов в группе с отметками времени большими, чем отметка времени сообщения m. Для этого при получении широковещательного сообщения каждый процесс должен разослать всем процессам соответствующее подтверждение. Очевидно, отметка времени подтверждения будет больше, чем отметка времени самого сообщения, на которое это подтверждение высылается. Поэтому рано или поздно каждый процесс сможет получить от всех остальных процессов сообщения с отметками времени большими, чем отметка времени сообщения m, и, следовательно, доставить m и приступить к его обработке.

Рис. 3.4. Пример формирования очередей в процессах.

Следует еще раз обратить внимание, что подтверждения используются исключительно для информирования процессов о том, что в каналах не осталось ни одного сообщения, которое может потеснить сообщение m в их очередях и занять первое место. Поэтому при приеме широковещательного сообщения процесс может не отправлять соответствующее подтверждение, если к этому моменту он уже разослал свое собственное широковещательное сообщение с отметкой времени большей, чем отметка времени принимаемого сообщения.

Таким образом, механизм работы скалярных часов Лэмпорта гарантирует, что никакие два сообщения не будут иметь одинаковые отметки времени. При этом линейный порядок отметок времени будет определять общий порядок доставки сообщений групповой рассылки.

3.