Византийские генералы. Доказательство невозможности

By Денис Чащин  

Описание

Приведенный в статье «Алгоритм византийских генералов» алгоритм решения задачи о византийских генералах работает только когда n < 3m%2B{1}, где  m — число предателей. Сейчас покажем, что 3m%2B1 является граничным значением. (далее  P — множество передач сообщений генералов, V — множество значений, которые получили генералы). Не получится достигнуть единогласия, если n<3m%2B1 ни только с m%2B1 раундами, но и с бесконечным количеством раундов обмена информацией.

Определения

Рассмотрим несколько необходимых для доказательства определений.

  • Во первых определим сценарий как отображение из множества P* всех непустых строк над P к V.
  • Для каждого p\in{P} определим p-сценарий как отображение подмножества P*, состоящего из строк, начинающихся с p на V.
  • Далее по данному набору N\in{P} нормальных генералов (nonfaulty) и заданному сценарию \sigma{} будем говорить, что \sigma{} согласуется с N, если для любого q\in{N}, p\in{P}, и w\in{P*} (множество всех слов из P) выполнено \sigma{(pqw)}=\sigma{(qw)}. Другими словами \sigma согласуется с N если каждый генерал из N всегда правдиво докладывает все что знает или слышал.
  • Определим понятие интерактивной согласованности. Для каждого p\in{P} зададим F_p — отображение, которое берет p — сценарий \sigma{_p} и генерала q в качестве аргументов и возвращающее значение из V. (другими словами F_p дает значение, которое p считает для элемента вектора интерактивной согласованности, соответствующее q на базисе \sigma{_p}). Будем говорить, что \{F_p|p\in{P}\} обеспечивает интерактивную согласованность для m предателей, если для любой выборки N\in{P}, такой что |N|\ge{n-m} и каждого сценария \sigma{} вывода в согласованного с N:
    1. Для всех p и q из N  F_p(\sigma{_p,q})=\sigma{(q)}
    2. Для всех p и q из N и r\in{P} F_p(\sigma{_p},r)=F_q(\sigma{_q},r)

    где \sigma{_p} и \sigma{_q} — ограничения строк, начинающихся с p и q соответственно. Другими словами пункт 1 требует, чтобы каждый нормальный генерал p правильно вычислял собственное значение каждого нормального генерала q. А пункт 2 требует, чтобы каждые два нормальных ненерала вычисляли одинаковый вектор.

Теорема. Доказательство

Теорема: Если |V|>2 и n\ge{3m}, то не существует \{F_p|p\in{P}\}, которое обеспечивает интерактивную согласованность с m предателями.

Доказательство: Предположим что \{F_p|p\in{P}\} обеспечивает интерактивную согласованность с m  предателями. Так как n<3m, то P можно разбить на три непустых множества A, B и C, каждое из которых будет иметь не более m элементов. Положим v и v^\prime{} — два различных значения из V. Нам нужно построить три сценария \alpha, \beta и \sigma, такие что \alpha согласовано с N=A\cup{C}, \beta согласовано с N=B\cup{C}, и \sigma согласовано с N=A\cup{B}. Элементы из C все будут даны как собственные значения v в \alpha и v^\prime в \beta. Кроме того, \alpha, \beta и \sigma будут построены таким образом, чтобы ни один генерал a из A не мог выделить \alpha из \sigma (т.е. \alpha{_a}=\sigma{_a}) и ни один генерал b из B не мог выделить \beta из \sigma (т.е. \beta{_b}=\sigma{_b}). Из этого будет следовать, что для сценария \sigma генералы из A и B могут быть посчитаны разные значения для элементов из C. Определим сценарии \alpha, \beta и \sigma рекурсивно следующим образом:

  1. Для каждого w\in{P^*} и не заканчивающегося на элемент из C, положим:
    \alpha{(w)}=\beta{(w)}=\sigma{(w)}=v
  2. Для каждого a\in{A}, b\in{B}, c\in{C} положим:
    \alpha{(c)}=\alpha{(ac)}=\alpha{(bc)}=\alpha{(cc)}=v,
    \beta{(c)}=\beta{(ac)}=\beta{(bc)}=\beta{(cc)}=v^\prime,
    \sigma{(c)}=\sigma{(ac)}=\sigma{(cc)}=v, \sigma{(bc)}=v^\prime
  3. Для каждого a\in{A}, b\in{B}, c\in{C}, p\in{P}, w\in{P^*c} (т.е. w — любая строка из P, заканчивающаяся на c), положим:
    \alpha{(paw)}=\alpha{(aw)}, \beta{(paw)}=\alpha{(aw)},
    \alpha{(pbw)}=\beta{(bw)}, \beta{(pbw)}=\beta{(bw)},
    \alpha{(pcw)}=\alpha{(cw)}, \beta{(pcw)}=\beta{(cw)},
    \sigma{(paw)}=\sigma{(aw)},
    \sigma{(pbw)}=\sigma{(bw)},
    \sigma{(acw)}=\sigma{(cw)},
    \sigma{(bcw)}=\beta{(cw)}

Это легко проверить, посмотрев на то что \alpha, \beta и \sigma на самом деле соответствуют с N=A\cup{C}, B\cup{C}, A\cup{B} в указанном порядке. Более того, это пожно показать, приведя простое доказательство с индукцией по длине w, что: \alpha{(aw)}=\sigma{(aw)}, \beta{(bw)}=\sigma{(bw)}.  Для всех a\in{A}, b\in{B} и w\in{P^*}. Теперь из определения интерактивной согласованности следует, что для любого a\in{A}, b\in{B}, c\in{C}, v=\alpha{(c)}=F_a(\alpha{_a},c)=F_a(\sigma{_a},c)=F_b(\sigma{_b},c)=F_b(\beta{_b},c)=v^\prime.

Пришли к противоречию. Значит не существует \{F_p|p\in{P}\}, которое обеспечивает интерактивную согласованность с m предателями.

Ч.и т.д.


One Trackback

  1. [...] m. Доказательство этого факта приведено в статье «Византийские генералы. Доказательство невозможности«. This entry was written by diniska, posted on 11.03.2011 at 1:13 дп, filed under [...]

Post a Comment

Your email is never shared. Required fields are marked *

*
*