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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 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]]

Текущая версия на 19:20, 4 сентября 2022

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