Кворумы: различия между версиями

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

'''Решетка''': предположим, что совокупность серверов имеет размер <math>n = k^2</math> для некоторого целого числа <math>k</math>. Разложим совокупность в решетку <math>\sqrt{n} \times \sqrt{n}</math>, как показано на рис. 1. Кворум – это объединение полного ряда и одного элемента из каждого ряда ниже полного ряда. Таким образом, получается система кворумов типа «решетка», размер кворумов которой составляет <math>O(\sqrt{n})</math>.

'''FPP''' (мажоритарная избирательная система): Предположим, что совокупность серверов имеет размер <math>n = q^2 + q + 1</math>, где <math>q = p^r</math> для простого <math>p</math>. Известно, что для <math>n</math> существует конечная проективная плоскость с <math>q + 1</math> попарно пересекающимися подмножествами, каждое подмножество имеет размер <math>q + 1</math>, и где каждый элемент содержится в <math>q + 1</math> подмножествах. Тогда множество подмножеств конечной проективной плоскости образует систему кворумов.

Голосование было упомянуто выше как интуитивный способ осмысления техники кворумов. Оказывается, назначения голосов и кворумы не эквивалентны. Гарсия-Молина и Барбара [2] показали, что системы кворумов являются строго более общими, чем голосования, то есть каждое назначение голосов имеет некоторую соответствующую систему кворумов, но не наоборот. На самом деле, для системы с <math>n</math> серверами существует двойное экспоненциальное <math>(2^{2^{cn}})</math> число недоминируемых комитетов и только <math>O(2^{n^2})</math> различных назначений голосов, хотя для <math>n \le 5</math> голосование и недоминируемые комитеты идентичны.

Следующая теорема была доказана в работе [ ] для всех систем кворумов.

Заметим, что устойчивость <math>f</math> составляет не более <math>c(\mathcal{Q}) - 1</math>, так как при отключении членов наименьшего кворума все кворумы будут поражены. Однако возможно, что <math>f</math>-устойчивая система кворумов, несмотря на уязвимость к нескольким конфигурациям <math>f + 1</math> отказов, может пережить множество конфигураций более чем <math>f</math> отказов. Один из способов измерить это свойство системы кворумов – это предположить, что каждый сервер выходит из строя независимо с вероятностью <math>p</math>, а затем определить вероятность <math>F_p</math> того, что ни один кворум не останется полностью живым. Она называется ''вероятностью отказа'' и формально определяется следующим образом:

Пелег и Вул изучили доступность систем кворумов в работе [11]. Хорошая вероятность отказа <math>F_p(\mathcal{Q})</math> для системы кворумов <math>\mathcal{Q}</math> имеет <math>lim_{n \to \infty} F_p(\mathcal{Q}) = 0</math>, когда <math>p < \frac{1}{2}</math>. Заметим, что вероятность отказа любой системы кворумов, чья отказоустойчивость равна <math>f</math>, не ниже <math>e^{- \Omega(f)}</math>. Большинство имеет наилучшую доступность, когда <math>p < \frac{1}{2}</math>; для <math>p = \frac{1}{2}</math> существуют кворумные построения с <math>F_p(\mathcal{Q}) = \frac{1}{2}</math>; для <math>p > \frac{1}{2}</math> синглтон имеет наилучшую вероятность отказа <math>F_p(\mathcal{Q}) = p</math>, но для большинства систем кворумов <math>F_p(\mathcal{Q})</math> стремится к 1.