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

Примеры использования

Для иллюстрации применения скалярных часов при решении различных задач рассмотрим следующие примеры.
Банковская система. Вернемся к представленной в п. 1.5.1 задаче подсчета полной суммы денег, находящихся на счетах в разных филиалах банка. Как и прежде будем предполагать, что банковская система не позволяет вносить дополнительные денежные средства на счет филиала и снимать их наличными, а лишь осуществляет перевод различных сумм из одного филиала банка в другой с помощью сообщений. Будем считать, что в каждом филиале работает ровно один процесс P_i, который отсылает бесконечно много сообщений каждому другому процессу распределенной системы. Удовлетворить этому требованию несложно: процесс всегда может отправить "пустое" сообщение с переводом $0 в другой филиал. Для простоты будем считать, что все каналы обладают свойством FIFO.
Однако теперь, чтобы избежать трудностей, указанных в п. 1.5.1, мы будем подсчитывать денежные средства, опираясь не на физическое время, отсчитываемое компьютерами филиалов, а на введенное выше логическое время. А именно, общую сумму денег будем определять в момент логического времени t  Z_≥0, т.е. после наступления всех событий с отметками времени, меньшими или равными t, и до наступления событий с отметками времени, строго большими, чем t, где t – время, известное всем процессам. Для этого потребуем, чтобы каждый процесс P_i записывал состояние своего счета непосредственно перед выполнением первого события e_i, для которого L(e_i) > t. Такое событие обязательно должно наступить, т.к. по нашему предположению в каждом процессе происходит бесконечно много событий. Чтобы учесть денежные средства, находящиеся в состоянии передачи между филиалами, необходимо
определить все сообщения, у которых события отправки имеют время меньшее или равное t, а события получения – время, превышающее t. Для этого, начиная с первого события e_i, имеющего время L(e_i) > t, т.е. начиная именно с того события, перед которым процесс зафиксировал состояние своего счета, каждый процесс P_i должен записывать все поступающие ему сообщения с отметками логического времени L_msg ≤ t. Когда из канала C_ji придет первое сообщение с отметкой времени L_msg > t, процесс P_i зафиксирует состояние канала C_ji на момент времени t, подсчитывая денежную сумму, переданную по этому каналу в записанных сообщениях. Сообщение с отметкой времени L_msg > t обязательно должно поступить, т.к. по нашему предположению процесс P_j отправляет бесконечно много сообщений процессу P_i. Общая сумма денег будет определяться подсчетом всех денежных средств, записанных в зафиксированных состояниях счетов и каналов.
Чтобы показать, что представленный алгоритм дает правильный результат, рассмотрим произвольное выполнение R банковской системы. Перестановка Ȓ событий выполнения R в порядке, задаваемом отметками скалярного времени, представляет собой выполнение, эквивалентное R, т.е. с точки зрения процессов невозможно понять, какое из этих выполнений происходит на самом деле. Работа рассматриваемого алгоритма заключается в том, что он делает снимок глобального состояния S в выполнении Ȓ сразу после всех событий, имеющих время t, т.е. записывает состояние всех процессов и каналов на этот момент. Поэтому, очевидно, что в результате его работы будет получена корректная сумма денег, циркулирующих в банковской системе.
На рис. 3.2 представлен пример выполнения банковской системы, использующей скалярные часы. Слева показана начальная сумма денег на счете каждого филиала. Размер денежного перевода указан на стрелке, обозначающей передачу сообщения.

Рис. 3.2. Пример выполнения банковской системы, использующей скалярные часы.

Предположим, что подсчитать общую сумму денег требуется в момент времени t = 5, что на рис. 3.2 обозначено штриховой линией, проходящей через временные оси каждого из процессов. При подсчете денег на своем счете процесс P₁ получит результат, равный $10 – $1 – $3 =
$6. На счете процесса P₂ окажется $20 + $1 – $2 + $3 – $5 = $17. Cчет процесса P₃ будет составлять $30 + $2 – $4 = $28. Кроме того, процесс P₁ обнаружит в канале C₃₁ сообщение с переводом $4, а процесс P₃ – в канале C₂₃ сообщение с переводом $5. Общая сумма будет составлять $6 + $17 +
$28 + $4 + $5 = $60, что является верным результатом.
На рис. 3.3 представлено эквивалентное выполнение банковской системы, в котором все события упорядочены согласно отметкам скалярного времени. Штриховая линия на рис. 3.3 соответствует штриховой линии на рис. 3.2 и демонстрирует результаты работы алгоритма, а именно, зафиксированные состояния процессов и каналов. Нетрудно видеть, что в выполнении на рис 3.3 совокупность этих состояния есть не что иное, как глобальное состояние системы, в которой она находится после наступления всех событий со временем 5 и до наступления любого события со временем 6.

Рис. 3.3. Выполнение банковской системы, эквивалентное выполнению на рис. 3.2.