Изменения

Перейти к: навигация, поиск

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

310 байт добавлено, 20:35, 2 июня 2019
Нет описания правки
[[Категория: Параллельное программирование]]
'''Кворум рушащейся стенки''' - (Crumbling walls quorum) — пример [[Кворум|кворума]]с подмножествами размера порядка $O(\sqrt n)$ вместо $O(n)$, который удовлетворяет следующим правилам:* процессы упорядочены в линии по возможности равной длины; * элемент как у [[Кворум простого большинства|кворума является объединением всех процессов одной полной линии + по одному представителю из каждой нижней линиипростого большинства]].
ПримерСтруктура:У нас есть 9 # Процессы упорядочены в линии, по возможности равной длины.# Минимальный элемент кворума — объединение всех процессов P1..P9 упорядоченных какой-то одной линии плюс по 3 в одному представителю из каждой строкелинии ниже.Допустим, процесс === Пример ===  {|border="1"|P1 хочет войти в критическую секцию, тогда ему достаточно опросить следующее множество процессов {|P2, |P3, |-|P4, |P5|P6|-|P7|P8|P9|}.Или жеТогда кворумом может являться такое семейство (если замкнуть его по взятию надмножества): процесс P8 хочет войти в критическую секцию* {1, 2, 3, 4, 9}* {4, 5, 6, тогда ему достаточно опросить 8}* {P77, 8, P99=== Большой пример ===Если у нас есть 32 процесса, то можно выбрать вот такой кворум из 8 процессов (пример из статьи "Crumbling walls: a class of practical and efficient quorum systems" от D Peleg): [[Файл:crumbling-walls.png|300px]]
292
правки

Навигация