4817
правок
Кворумы: различия между версиями
Перейти к навигации
Перейти к поиску
→Нагрузка и доступность систем кворумов
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 140: | Строка 140: | ||
В работе [ ] Малхи и Райтер исследуют две вариации маскирующих систем кворумов. Первая, называемая ''диссеминирующими системами кворумов'', подходит для сервисов, которые получают и распространяют ''самопроверяемую'' информацию от корректных клиентов (например, значения с цифровой подписью), которую неисправные серверы, возможно, не могут перераспределить, но не могут необнаружимым образом изменить. Вторая разновидность, называемая ''непрозрачными маскирующими системами кворумов'', похожа на обычные маскирующие кворумы тем, что не предполагает самопроверки данных, и отличается от них тем, что клиентам не требуется знать сценарии отказов, для которых был разработан сервис. Это несколько упрощает клиентский протокол и в случае, если сбои вызваны злоумышленным поведением, раскрывает клиентам меньше информации, которая могла бы послужить руководством для атаки, пытающейся скомпрометировать систему. В [7] также показано, как справиться не только с неисправными серверами, но и с неисправными клиентами. | В работе [7] Малхи и Райтер исследуют две вариации маскирующих систем кворумов. Первая, называемая ''диссеминирующими системами кворумов'', подходит для сервисов, которые получают и распространяют ''самопроверяемую'' информацию от корректных клиентов (например, значения с цифровой подписью), которую неисправные серверы, возможно, не могут перераспределить, но не могут необнаружимым образом изменить. Вторая разновидность, называемая ''непрозрачными маскирующими системами кворумов'', похожа на обычные маскирующие кворумы тем, что не предполагает самопроверки данных, и отличается от них тем, что клиентам не требуется знать сценарии отказов, для которых был разработан сервис. Это несколько упрощает клиентский протокол и в случае, если сбои вызваны злоумышленным поведением, раскрывает клиентам меньше информации, которая могла бы послужить руководством для атаки, пытающейся скомпрометировать систему. В [7] также показано, как справиться не только с неисправными серверами, но и с неисправными клиентами. | ||
| Строка 155: | Строка 155: | ||
'''W(n, | '''W(n, <math>\ell</math>)''': Пусть <math>U</math> – совокупность размера <math>n</math>. <math>W(n, \ell), \ell \ge 1</math> – система <math> \langle \mathcal{Q}, w \rangle</math>, где <math>\mathcal{Q}</math> – система множеств <math>\mathcal{Q} = \{ Q \subseteq U: |Q| = \ell \sqrt{n} \}</math>; <math>w</math> – стратегия доступа, определяемая следующим образом: <math>\forall Q \in \mathcal{Q}, w(Q) = \frac{1}{|Q|}</math>. | ||
Вероятность выбора в соответствии с w двух непересекающихся кворумов меньше e и может быть сделана достаточно малой при соответствующем выборе | Вероятность выбора в соответствии с <math>w</math> двух непересекающихся кворумов меньше <math>e^{- \ell^2}</math> и может быть сделана достаточно малой при соответствующем выборе <math>\ell</math>. Поскольку каждый элемент находится в <math>\big( \ell \sqrt[n - 1]{n} - 1 \big)</math> кворумах, нагрузка <math>L(W(n, \ell))</math> равна <math>\frac{\ell}{\sqrt{N}} = O \big( \frac{1}{\sqrt{N}} \big)</math>. Поскольку для того, чтобы некоторый кворум был доступен, необходимо иметь в наличии только <math>\ell \sqrt{N}</math> серверов, <math>W(n, \ell)</math> устойчива к <math>n - \ell \sqrt{N}</math> сбоям. Вероятность отказа <math>W(n, \ell)</math> меньше <math>e^{-\Omega{n}}</math> для всех <math>p \le 1 - \frac{\ell}{\sqrt{N}}</math>, что является асимптотически оптимальным. Более того, если <math>\frac{1}{2} \le p \le 1 - \frac{\ell}{\sqrt{N}}</math>, то эта вероятность доказуемо лучше, чем у любой (не вероятностной) системы кворумов. | ||