Расчет вероятности отказа системы в распределенной сети

Question

Я пытаюсь создать математическую модель доступности файла в распределенной файловой системе. Я опубликовал этот вопрос в Mathoverflow, но это также может быть классифицировано как CS-вопросы, так что я тоже даю ему шанс.

Система работает так: узел хранит файл (включенный с использованием кодов стирания) в r*b-узлах удаленных узлов, где r-фактор репликации, а B-целочисленная постоянная. Файлы, кодируемые стиранием, имеют свойство, что файл может быть восстановлен, если, по крайней мере, b удаленных узлов доступны и возвращают его часть файла.

Самый простой подход к этому состоит в том, чтобы предположить, что все удаленные узлы не зависят друг от друга и имеют одинаковую доступность p. С этими предположениями доступность файла следует биномиальному распределению, т.е. Биномиальное распределение http://bit.ly/dyjwwe

К сожалению, эти два предположения могут ввести невидимную ошибку, как показано в этой статье: http://deim.urv.cat/~lluis.pamies/uploads/main/icpp09-paper.pdf.

Один из способов преодоления предположения о том, что все узлы имеют одинаковую доступность,-это рассчитать вероятность каждой возможной комбинации доступного/недоцентного узла и взять сумму всех этих результатов (что является своего рода то, что они предлагают в статье выше, Просто формально, чем то, что я только что описал). Вы можете рассматривать этот подход как двоичное дерево с глубиной r*b, и каждый отпуск является одной из возможных комбинаций доступных/не доступных узлов. Доступность файла - то же самое, что вероятность, что вы прибываете в отпуск с> = B доступные узлы. Этот подход более правильный, но имеет вычислительную стоимость Ordo http://bit.ly/cezcap. Анкет Кроме того, это не касается предположения о независимости узлов.

У вас, ребята, есть какие-либо идеи о хорошем приближении, который вводит меньше ошибок, чем биномиальное распределение-апрекксимация, но с более высокой вычислительной стоимостью, чем http://bit.ly/d52mm9 http://bit.ly/cezcap?

Вы можете предположить, что дата доступности каждого узла представляет собой набор кортежей, состоящих из (measurement-date, node measuring, node being measured, succes/failure-bit). Анкет С помощью этих данных вы могли бы, например, рассчитать корреляцию доступности между узлами и дисперсией доступности.

Answer 1

Для большого r а также b Вы можете использовать метод под названием Monte-Carlo Integration, см. EG Интеграция Монте -Карло в Википедии (и/или глава 3.1.2 SICP) для вычисления суммы. Для маленького r а также b и значительно разные вероятности узел p[i] Точный метод превосходит. Точное определение маленький а также большой будет зависеть от нескольких факторов и лучше всего опробовать экспериментально.

Конкретный пример кода: Это очень базовый пример кода (в Python), чтобы продемонстрировать, как такая процедура может работать:

def montecarlo(p, rb, N):
    """Corresponds to the binomial coefficient formula."""
    import random
    succ = 0

    # Run N samples
    for i in xrange(N):
        # Generate a single test case
        alivenum = 0
        for j in xrange(rb):
            if random.random()<p: alivenum += 1
        # If the test case succeeds, increase succ
        if alivenum >= b: succ += 1
    # The final result is the number of successful cases/number of total cases
    # (I.e., a probability between 0 and 1)
    return float(succ)/N

Функция соответствует биномиальному тестовому примеру и запускается N тесты, проверка, если b узлы из r*b узлы живы с вероятностью отказа p. Анкет Несколько экспериментов убедит вас в том, что вам нужны ценности N В диапазоне тысяч образцов, прежде чем вы сможете получить какие -либо разумные результаты, но в принципе сложность O(N*r*b). Анкет Точность результата масштабирует как sqrt(N), т.е., чтобы повысить точность в два раза, вам нужно увеличить N в течение четырех человек. Для достаточно больших r*b Этот метод будет явно превосходным.

Расширение приближения: Очевидно, вам нужно спроектировать тестовый пример такой, что он уважает все свойства системы. Вы предложили пару расширений, некоторые из которых могут быть легко реализованы, а другие не могут. Позвольте мне дать вам пару предложений:

1) В случае отчетливого, но некоррелированного p[i], Изменения вышеуказанного кода минимальны: в головке функции вы проходите массив вместо одного поплавка p и вы замените линию if random.random()<p: alivenum += 1 по

if random.random()<p[j]: alivenum += 1

2) В случае коррелированного p[i] Вам нужна дополнительная информация о системе. Ситуация, о которой я имел в виду в своем комментарии, может быть такой сетью, как это:

A--B--C
   |  |
   D  E
   |
   F--G--H
      |
      J

В таком случае A может быть «корневой узел» и сбой узла D может подразумевать автоматический отказ со 100% вероятностью узлов F, G, H а также J; В то время как неудача узла F автоматически снизит G, H а также J и т.д., по крайней мере, это было так, о котором я говорил в своем комментарии (что является правдоподобной интерпретацией, поскольку вы говорите о структуре вероятностей дерева в первоначальном вопросе). В такой ситуации вам нужно изменить код, который p относится к структуре деревьев и for j in ... Проходит по дереву, пропустив нижние ветви из текущего узла, как только тест не пройдет. Получившимся тестом все еще в alivenum >= b Как и прежде, конечно.

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

4) Зависимость от времени является нетривиальной, но возможной модификацией, если вы знаете, что MTBF/R (среднее время промежутка p либо структуры дерева, либо некоррелированной линейной p[i] по сумме экспоненциальных. Затем вам придется запустить MC-процесс в разное время с соответствующими результатами для p.

5) Если у вас просто есть файлы журнала (как намекают в вашем последнем абзаце), это потребует существенной модификации подхода, который выходит за рамки того, что я могу сделать на этой плате. Логариффилы должны быть достаточно тщательными, чтобы позволить реконструировать модель для сетевого графа (и, следовательно, график p), а также отдельные значения всех узлов p. Анкет В противном случае точность была бы ненадежной. Эти логарифмы также должны быть значительно дольше, чем временные масштабы сбоев и ремонта, предположения, которые могут быть не реалистичными в реальных сетях.

Answer 2

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

Скажи, что у тебя есть N узлы.

1. Разделить их на два набора N/2 узлы.
2. Для каждой стороны вычислите вероятность того, что любое количество узлов ([0,N/2]) вниз.
3. Умножьте и суммируйте их по мере необходимости, чтобы найти вероятность того, что любое число ([0,N]) из полного набора недостигает.

Шаг 2 может быть сделан рекурсивно, а на верхнем уровне вы можете суммировать, как необходимо найти, как часто больше, чем какое -то число снижается.

Я не знаю сложности этого, но если я должен догадаться, я бы сказал на или ниже O(n^2 log n)

---

Механика этого может быть проиллюстрирована на терминале. Скажем, у нас 5 узлов с временем . Анкет Мы можем разделить это на сегменты A с а также B с . Анкет Затем мы можем обработать их, чтобы найти время «n узлов» для каждого сегмента:

Для:

Для B:

Окончательные результаты для этого этапа можно найти путем умножения каждого из aс каждым из bи суммируют соответствующим образом.

v[0] = a[0]*b[0]
v[1] = a[1]*b[0] + a[0]*b[1]
v[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]
v[3] =             a[2]*b[1] + a[1]*b[2] + a[0]*b[3]
v[4] =                         a[2]*b[2] + a[1]*b[3]
v[5] =                                     a[2]*b[3]