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

Материал из Викиконспекты
(перенаправлено с «Кворум рушашейся стенки»)
Перейти к: навигация, поиск

Кворум рушащейся стенки (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