Кворум рушащейся стенки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
'''Кворум рушащейся стенки''' - пример [[Кворум|кворума]], который удовлетворяет следующим правилам:
+
'''Кворум рушащейся стенки''' (Crumbling walls quorum) — пример [[Кворум|кворума]] с подмножествами размера порядка $O(\sqrt n)$ вместо $O(n)$, как у [[Кворум простого большинства|кворума простого большинства]].
* процессы упорядочены в линии по возможности равной длины;
 
* элемент кворума является объединением всех процессов одной полной линии + по одному представителю из каждой нижней линии.
 
  
Пример:
+
Структура:
У нас есть 9 процессов P1..P9 упорядоченных по 3 в каждой строке.
+
# Процессы упорядочены в линии, по возможности равной длины.
Допустим, процесс P1 хочет войти в критическую секцию, тогда ему достаточно опросить следующее множество процессов {P2, P3, P4, P8}.
+
# Минимальный элемент кворума — объединение всех процессов какой-то одной линии плюс по одному представителю из каждой линии ниже.
Или же: процесс P8 хочет войти в критическую секцию, тогда ему достаточно опросить {P7, P9}.
+
 
 +
=== Пример ===
 +
 
 +
 
 +
{|border="1"
 +
|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|300px]]

Текущая версия на 20:35, 2 июня 2019

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