4817
правок
Кворумы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
Пожалуй, двумя самыми очевидными системами кворума являются синглтон и множество большинств или, в более общем случае, взвешенных большинств, предложенных Гиффордом [3]. | Пожалуй, двумя самыми очевидными системами кворума являются синглтон и множество большинств или, в более общем случае, взвешенных большинств, предложенных Гиффордом [3]. | ||
'''Синглтон''': система множеств Q = | '''Синглтон''': система множеств <math>\mathcal{Q} = \{ \{ u \} \}</math> для некоторого <math>u \in U</math> является синглтонной системой кворума. | ||
'''Взвешенное большинство''': предположим, что каждому серверу s в совокупности U присвоено количество голосов | '''Взвешенное большинство''': предположим, что каждому серверу <math>s</math> в совокупности <math>U</math> присвоено количество голосов <math>w_s</math>. Тогда система множеств <math>\mathcal{Q} = \{ Q \subseteq U: \sum_{q \in Q} w_q > \big( \sum_{q \in U} w_q \big) / 2 \}</math> является системой кворумов, называемой взвешенным большинством. Когда все веса одинаковы, такую систему называют просто системой большинств. | ||
Примером системы кворумов, которая не может быть определена голосованием, является следующая конструкция решетки: | Примером системы кворумов, которая не может быть определена голосованием, является следующая конструкция решетки: | ||
'''Решетка''': предположим, что совокупность серверов имеет размер n = | '''Решетка''': предположим, что совокупность серверов имеет размер <math>n = k^2</math> для некоторого целого числа <math>k</math>. Разложим совокупность в решетку <math>\sqrt{n} \times \sqrt{n}</math>, как показано на рис. 1. Кворум – это объединение полного ряда и одного элемента из каждого ряда ниже полного ряда. Таким образом, получается система кворумов типа «решетка», размер кворумов которой составляет <math>O(\sqrt{n})</math>. | ||
[[Файл:Quorums_1.png]] | |||
Рисунок 1. Система кворумов типа «решетка» размером 6 x 6, один кворум заштрихован | |||
Маэкава в работе [ ] предлагает систему кворумов, обладающую несколькими желательными свойствами симметрии, в частности тем, что каждая пара кворумов пересекается ровно в одном элементе: | Маэкава в работе [6] предлагает систему кворумов, обладающую несколькими желательными свойствами симметрии, в частности тем, что каждая пара кворумов пересекается ровно в одном элементе: | ||
| Строка 50: | Строка 50: | ||
'''Голосование и связанные с ним понятия''' | '''Голосование и связанные с ним понятия''' | ||
Поскольку в общем случае было бы бессмысленно обращаться к большому кворуму, если его подмножество является кворумом, хорошее определение поможет избежать таких аномалий. Гарсия-Молина и Барбара [2] называют такие хорошо оформленные системы комитетами (coteries), определяя их следующим образом: | Поскольку в общем случае было бы бессмысленно обращаться к большому кворуму, если его подмножество является кворумом, хорошее определение поможет избежать таких аномалий. Гарсия-Молина и Барбара [2] называют такие хорошо оформленные системы комитетами (coteries), определяя их следующим образом: | ||
| Строка 106: | Строка 105: | ||
== Нагрузка и доступность систем кворумов == | |||
Кворумные построения можно сравнивать, проанализировав их поведение в соответствии с приведенными выше показателями. Синглтон имеет нагрузку 1, устойчивость 0 и вероятность отказа Fp = p. Эта система имеет наилучшую вероятность отказа, когда p > j, но в остальном демонстрирует низкие показатели как по доступности, так и по нагрузке. | Кворумные построения можно сравнивать, проанализировав их поведение в соответствии с приведенными выше показателями. Синглтон имеет нагрузку 1, устойчивость 0 и вероятность отказа Fp = p. Эта система имеет наилучшую вероятность отказа, когда p > j, но в остальном демонстрирует низкие показатели как по доступности, так и по нагрузке. | ||