Вычисление нижней грани

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

Как известно из курса математики, если (X, £) – частичный порядок, то c называют нижней гранью a и b, если c £ a, c £ b, и " d: (d £ a & d £ b Þ d £ c). Допустим, что X таково, что нижняя грань всегда существует; в этом случае нижняя грань является единственной и обозначается как a Ù b. Так как Ù – бинарный оператор, коммутативный и ассоциативный, то операция может быть обобщена на конечные множества: inf { a ₁,..., a_k } = a ₁ Ù... Ù a_k.

Задача вычисления нижней грани в распределенной системе формулируется следующим образом. Каждый процесс на сайте q содержит вход a_q, являющийся элементом частично упорядоченного множества X. Потребуем, чтобы определенные процессы вычисляли значение inf { a_q } по всем сайтам и чтобы эти процессы знали, когда вычисление завершается. Они записывают результат вычисления в переменную out и после этого не могут изменять ее значение.

Событие write, которое заносит значение в out, рассматривается в алгоритме вычисления нижней грани как событие return (OK).

Любой волновой алгоритм может быть использован для вычисления нижней грани.

Это можно показать следующим образом. Допустим, что дан волновой алгоритм A. Назначим каждому процессу q дополнительную переменную v_q, которой придадим начальное значение a_q. Во время волны эти переменные переприсваиваются следующим образом. Всякий раз, когда процесс q посылает сообщение, текущее значение v_q включается в сообщение. Всякий раз, когда процесс q получает сообщение со значением v, переменной v_q присваивается значение v_q Ù v. Когда в процессе p происходит событие return (OK), текущее значение v_p заносится в out_p.

Теперь нужно показать, что в результат заносится правильное значение. Обозначим правильный ответ через L, т.е. L = inf { a_q }. Для события a в процессе q обозначим через v ^(a) значение v_q сразу после выполнения a. Так как начальное значение v_q равно a_q, и в течение волны оно только уменьшается, неравенство v ^(a) £ a_q сохраняется для каждого события a в q. Из присваивания v следует, что для событий a и b, a p b Þ v ^(a) ³ v ^(b). Кроме того, так как v всегда вычисляется как нижняя грань двух уже существующих величин, неравенство L £ v выполняется для всех величин в течение волны. Таким образом, если d – событие return (OK) в p, значение v ^(d) удовлетворяет неравенству L £ v ^(d) и, так как событию d предшествует хотя бы одно событие в каждом процессе q, v ^(d) £ a_q для всех q. Отсюда следует, что L = v ^(d).

Известна теорема о нижней грани:Если · – бинарный оператор на множестве X,причем он:

1) коммутативен, т.е. a · b = b · a,

2) ассоциативен, т.е.(a · b) · c = a · (b · c),

3) идемпотентен, т.е. a · a = a,

то существует отношение частичного порядка £ на X такое, что · – функция нижней грани.

Среди операторов, удовлетворяющих этим трем критериям – логическая конъюнкция и дизъюнкция, минимум и максимум целых чисел, наибольший общий делитель и наименьшее общее кратное целых чисел, пересечение и объединение множеств. Отсюда следует, что операции &, Ú, min, max, НОД, НОК,ÇиÈнад величинами, локальными по отношению к сайтам, могут быть вычислены за одну волну.