Кворум рушащейся стенки

Материал из Викиконспекты
Перейти к: навигация, поиск

Кворум рушащейся стенки (Crumbling walls quorum) — пример кворума с подмножествами размера порядка $O(\sqrt n)$ вместо $O(n)$, как у кворума простого большинства.

Структура:

  1. Процессы упорядочены в линии, по возможности равной длины.
  2. Минимальный элемент кворума — объединение всех процессов какой-то одной линии плюс по одному представителю из каждой линии ниже.

Пример[править]

P1 P2 P3
P4 P5 P6
P7 P8 P9

Тогда кворумом может являться такое семейство (если замкнуть его по взятию надмножества):

  • {1, 2, 3, 4, 9}
  • {4, 5, 6, 8}
  • {7, 8, 9}

Большой пример[править]

Если у нас есть 32 процесса, то можно выбрать вот такой кворум из 8 процессов (пример из статьи "Crumbling walls: a class of practical and efficient quorum systems" от D Peleg):

Crumbling-walls.png