Как гарантировать заражение всех узлов в протоколах, основанных на сплетнях?

Трудно ответить по двум причинам:

1. На самом деле не существует протокола, основанного на сплетнях. В лучшем случае существуют семейства алгоритмов, основанных на слухах.

2. Алгоритмы на самом деле гарантируют заражение только при определенных предположениях. Например, если, как вы выразились, поскольку "система работает в течение длительного времени" какой-либо данный канал постоянно выходит из строя при каком-то экспоненциальном процессе (весьма вероятный сценарий), то с вероятностью 1 какой-то узел будет полностью изолирован, и никакой протокол может преодолеть это.

Однако IIUC, вы спрашиваете о протоколе со следующими предположениями:

1. Для любой группы узлов V' V существует активная ссылка u V' v V V'.

2. Каждый узел равномерно выбирает d своих соседей на каждом шаге, независимо от их состояния, выбора, сделанного другими узлами, общего состояния обновления и т. д.

В этих условиях вероятность поднятой вами проблемы будет равна 0.

Заражение можно рассматривать как цепь Маркова, где система находится в состоянии i. , если узлы i заражены. Предположим, что какое-то изменение возникло в некотором s V, поэтому система запускается в состоянии i.

• По свойству 1. существует ссылка от i зараженных узлов к одному из n - i других.

• По свойству 2. вероятность выбора этой ссылки не менее 1 / n. Это связано с тем, что узел, звено которого пересекает разрез, имеет не более n соседей, но по крайней мере один сосед пересекает разрез. Даже если его выбор полностью лишен гражданства и информации, есть шанс, что он выберет этого соседа.

Следовательно, вероятность того, что этого не произойдет для j шагов, составляет (1 - d/n)^j. При использовании Union Bound вероятность того, что это произойдет для любого состояния, i не превышает n (1 - 1/n)^j. Возьмем j = n², и получится n e^{- n}; возьмем j = n³, и получится n e^{- n2}. И т.п.

(Конечно, заражение алгоритмом сплетен происходит гораздо раньше; это верхняя граница наихудших возможных условий.)

Итак, если система работает достаточно долго, вероятность того, что какой-то узел не заразится, уменьшается до 0 (очень быстро). Для антиэнтропийных протоколов сплетен этого достаточно. Для некоторых других протоколов, как вы и подозревали, есть шанс, что какая-то нода будет пропущена для какого-то обновления.

Мы не можем дать ответ, потому что вы не понимаете своей проблемы (поэтому вопрос неоднозначен)

• Топология сети неизвестна, но от нее зависит ответ
• Каково условие остановки алгоритма? Он останавливается или нет?

Предположим, что данный узел подключен ко всем другим узлам (это топология), и каждый узел выполняет одно и то же действие, если получает сообщение.

Вы можете упростить свою проблему на более мелкие подзадачи (это подход «разделяй и властвуй»): представьте, что любой узел выполняет только одну попытку (т.е. i = 1).

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

Как только вы получите это, включая повторную попытку i, это будет просто.

Я сделал небольшую симуляцию того, что вы пытаетесь сделать. http://jsfiddle.net/ut78sega/

function gossip(nodes, tries, startNode, reached) {
    var stack = [startNode, tries];
    while(stack.length > 0) {
        var ttl = stack.pop();
        var n = stack.pop();
        reached[n] = 1;
        if(ttl <= 0) { continue; }
        for(var i=0; i < ttl; i++) {
            stack.push(Math.floor(Math.random() * nodes), ttl - 1);
        }
    }
    return reached;
}

• узел – общее количество узлов
• tries – начальное количество случайных выборов.
• startNode — узел, который получает первое сообщение
• достигнуто — хэш-набор узлов, которые были достигнуты в ходе текущей симуляции.

На каждом уровне рекурсии количество попыток уменьшается на одну. Требуется ~9 попыток, чтобы получить 100% покрытие 65536 (2^16) узлов.