|
Изоморфизм. Если события распределенного вычисления отмечаются с помощью механизма векторных часов, то для любых двух событий ei и ej' с векторными отметками времени V(ei) и V(ej'), соответственно, имеем:
ei → ej' V(ei) < V(ej'),
ei || ej' V(ei) || V(ej').
Необходимое условие для ei → ej' обеспечивается правилами продвижения векторного времени процесса.
Для доказательства того, что V(ei) < V(ej') является достаточным условием для ei → ej', вначале покажем, что если события ei и ej' различны, то
ei →/ ej' V(ej')[i] < V(ei)[i].
Неформально, можно сказать, что в этом случае событие ej' "не знает" о событии ei, а "знает" лишь о каком-то событии, предшествующим событию ei в процессе Pi (если V(ej')[i] ≠ 0).
Действительно, если i = j, т.е. ei и ej' – события одного процесса Pi, то из ei →/ ej' следует, что ej' произошло раньше ei. Поэтому на основании Правила 1 продвижения локального времени процесса Pi имеем V(ej')[i] < V(ei)[i]. Теперь предположим, что i ≠ j, т.е. события ei и ej' происходят в разных процессах. В этом случае V(ei)[i] представляет собой значение локального времени процесса Pi в момент наступления события ei. Очевидно, процесс Pj не мог получать это значение через поступающие к нему сообщения, т.к. ei →/ ej', т.е. V(ej')[i] < V(ei)[i].
Отсюда имеем, что ei →/ ej' ¬(V(ei) < V(ej')), что равносильно V(ei) < V(ej') ei → ej', т.е. V(ei) < V(ej') является достаточным условием для ei → ej'.
Истинность утверждения ei || ej' V(ei) || V(ej') следует из определений параллельных событий и несравнимых векторных отметок времени.
Таким образом векторные часы являются изоморфизмом, т.е. взаимно однозначным соответствием, сохраняющим порядок, между множеством событий распределенного вычисления (E, →) и множеством их векторных отметок времени (V, <).
Стоит отметить, что если кроме векторных отметок времени событий ei и ej' еще известны процессы Pi и Pj, в которых эти события происходили (т.е. мы знаем значения i и j), то проверка на наличие причинно- следственной зависимости между событиями может быть упрощена согласно следующим выражениям:
ei → ej' V(ei)[i] ≤ V(ej')[i],
ei || ej' (V(ei)[i] > V(ej')[i]) ˄ (V(ei)[j] < V(ej')[j]).
Первое выражение свидетельствует о том, что событие ej' "знает" о наступлении события ei в процессе Pi. Второе выражение говорит о том, что на момент наступления события ej' процесс Pj "не знает" о событии ei в процессе Pi (первая часть этого выражения), равно как и процесс Pi "не знает" о событии ej' в процессе Pj на момент наступления ei (вторая часть этого выражения). Поэтому при известных значениях i и j двух событий ei и ej' достаточно сравнить всего два компонента их векторных отметок времени.
Строгая непротиворечивость. Векторные часы являются строго непротиворечивыми, что позволяет по отметкам времени двух событий судить о том, оказывают ли эти события потенциальное влияние друг на друга или нет. Поэтому, в отличие от скалярных часов, позволяющих построить одно из эквивалентных выполнений распределенной системы, векторные часы могут быть использованы для определения всех возможных выполнений.
Свойство строгой непротиворечивости логических часов является очень важным: благодаря ему векторные часы широко применяются при построении распределенных алгоритмов. Например, механизм векторных часов используется в коммуникационных сетях, сохраняющих причинно- следственный порядок доставки сообщений, в хранилищах данных, поддерживающих причинную непротиворечивость, а также применяется для отладки распределенных программ (англ. distributed debugging) и при установке непротиворечивых точек восстановления (англ. checkpoints) распределенной системы в случае сбоя.
Основным недостатком механизма векторных часов является необходимость хранить для каждого события и пересылать в каждом сообщении отметки времени, состоящие из N целых чисел, что может приводить к значительным накладным расходам, особенно, в случае большого числа N процессов, работающих в распределенной системе. Однако было показано, что векторами меньшей длины для определения причинно-следственной зависимости между событиями по их отметкам времени обойтись невозможно. А именно, если события распределенного вычисления системы, состоящей из N процессов, отобразить в пространство векторов длины n так, чтобы V(ei) < V(ej') было необходимым и достаточным условием для ei → ej', то неизбежно будем иметь n ≥ N.
Do'stlaringiz bilan baham: |
