Логическое время и анализ порядка приема сообщений в распределенных вычислениях

Колосова Ю. И.
Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. Тезисы докл. Междунар. математич. конф 1997. Вып.1. С. 24.

      Асинхронная среда для сообщений в распределенном вычислении может вызвать отклонение реального порядка их приема от предполагаемого. Рассмотрен алгоритм ностпрограммного анализа параллельных историй процессов с целью обнаружения несоответствия порядка приема сообщений отдельным процессом порядку их посылки.
      Используется распространенная модель, в которой распределенное вычисление представлено совокупностью n процессов p_i (i = 1, 2,..., n), где параллельная история процесса p_i описывается множеством событий {e_i1, e_i2,…} в порядке их выполнения. Здесь фиксируются только события посылки или приема сообщения.
      Алгоритм основан на варианте логических часов, показания которых характеризуют отношение “случилось вперед”, обычно обозначаемое и определяемое следующим образом:
       iff: 1) (i = j)∧(q < u) или 2) существует сообщение m такое, что e_ig есть его посылка, а e_ju — его прием или 3) существует событие е_k, такое, что e_ig → е_ks → e_ju.
      Каждое событие e_ig связывается с временной отметкой V(e_ij), которая является n-размерным вектором целых чисел и представляет текущие логические часы. Обновление этих часов производится так, что компонента V(e_ij) [i] равна числу событий посылки сообщения, выполненных в р_i до (и включая) e_ig, а остальные равны числу аналогичных событий, которые случились вперед e_ig в других процессах.
      Для каждой пары событий приема е_ks → е_ку в процессе р_к, для которой событиями посылки являются соответственно e_iq и e_ju, алгоритм установит отклонение в том случае, если e_ju e_iq. Для этого используется известное соотношение:
      
      Доказывается корректность алгоритма, приводятся примеры его полезности.