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

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

Банковская система. Для иллюстрации применения векторных часов при решении различных задач вернемся к рассмотренной в п. 3.2.2 задаче подсчета полной суммы денег, находящихся на счетах в разных филиалах банка. При решении этой задачи с помощью скалярных часов предполагалось, что всем процессам известен некоторый момент логического времени t, в который процессы будут подсчитывать денежные средства на своих счетах и в каналах между филиалами. Однако сама процедура достижения соглашения между процессами о таком будущем моменте t представляет определенные сложности. Действительно, при использовании механизма скалярных часов процесс не может произвольным образом выбрать значение t для согласования с другими процессами, т.к. не исключено, что на момент выбора t логические часы других процессов ушли далеко вперед, и их текущее логическое время потенциально может превышать любое предлагаемое значение t. Кроме того, если t окажется слишком большим, то придется долго ожидать наступления этого момента.
Использование векторных часов может помочь в решении этой задачи. А именно, для любых двух процессов P_i и P_j в любой момент верно
неравенство V_i[i] ≥ V_j[i], т.е. представление других процессов о ходе выполнения процесса P_i не может опережать ход его собственного выполнения. Поэтому в момент продвижения процессом P_i своего логического локального времени V_i[i] не существует такого процесса P_j, у которого V_j > V_i. Это означает, что текущие показания векторных часов других процессов не могут превосходить показания векторных часов процесса P_i при выполнении в нем внутреннего события. То есть в качестве будущего момента логического времени t процесс P_i может выбрать время своего следующего события.
С использованием механизма векторных часов процедура согласования времени t для подсчета денежных средств могла бы определяться таким образом.

1. 
   Процесс P_i вычисляет векторное время своего следующего, еще не наступившего события t = V_i + (0,…0, 1, 0,…0), и рассылает это значение всем остальным процессам распределенной системы.
   
2. 
   Затем процесс P_i приостанавливает свою работу до тех пор, пока не получит подтверждения от всех других процессов о том, что они приняли значение t. Тем самым гарантируется, что в системе не окажется ни одного процесса, показания часов которого превзойдут t до момента окончания процедуры согласования.
   
3. 
   После того как значение t становится известным всем процессам распределенной системы, процесс P_i увеличивает показания своих логических локальных часов, т.е. V_i становится равным t, и рассылает пустое сообщение всем другим процессам с тем, чтобы показания их векторных часов превзошли t.
   

В остальном алгоритм подсчета денежных средств остается таким же, как и в п. 3.2.2.
Основной недостаток предложенной выше схемы заключается в том, что процесс P_i вынужден приостанавливать свою работу на время информирования других процессов о выбранном значении t. Избежать этого можно с помощью дополнительного (N + 1)-го виртуального процесса, чьи логические часы управляются процессом P_i, предлагающим t. В этом случае P_i может назначить t с помощью увеличения логического локального времени этого (N + 1)-го виртуального процесса, тем самым получая возможность продолжать свою работу наравне со всеми другими процессами распределенной системы.

4.