Согласование множеств

Ключевые слова и синонимы

Распределенная координация

Постановка задачи

Краткая история вопроса

Задача согласования k множеств является парадигмой задач о координации. Определенная при помощи систем, состоящих из процессов, склонных к отказам, она является простым обобщением задачи о консенсусе (которая соответствует случаю k = 1). Эта задача была предложена в 1993 году Сомой Чаудхури [2] для изучения того, как число вариантов выбора (k), допустимых для процессов, связано с максимальным числом процессов, которые могут привести к аварийному завершению. (После аварийного завершения процесс больше не выполняет никаких действий; оно представляет собой преждевременную остановку).

Определение

Пусть S – система, состоящая из n процессов, в которой до t процессов могут завершиться аварийно и в которой каждый процесс имеет входное значение (называемое предлагаемым значением). Задача определяется тремя следующими свойствами (т. е. любой алгоритм, решающий эту задачу, должен удовлетворять данным трем свойствам):

1. Завершение. Каждый процесс без отказов вычисляет значение.

2. Достоверность. Вычисленное значение является предлагаемым значением.

3. Согласование. Вычисляется не более k различных значений.

Тривиальный случай

Легко заметить, что эта задача может быть решена тривиально, если верхняя граница на число отказов процессов (t) меньше допустимого числа вариантов k, также называемого степенью координации. (Тривиальное решение заключается в наличии t + 1 заранее определенных процессов, которые отправляют свои предлагаемые значения всем процессам, и процесс вычисляет первое значение, которое он когда-либо получает). Таким образом, в дальнейшем неявно предполагается k < t.

Основные результаты

Основные результаты в синхронных системах

Синхронная модель

В этой модели вычислений каждое выполнение представляет собой последовательность раундов. Они обозначаются последовательными целыми числами – 1, 2 и т.д. Для процессов номер текущего раунда представляется в виде глобальной переменной, глобальное увеличение которой влечет за собой их собственный локальный прогресс. Во время раунда процесс сначала передает сообщение, затем получает сообщения и, наконец, выполняет локальные вычисления. Фундаментальное свойство синхронности, которое обеспечивает процессам синхронная система, заключается в следующем: сообщение, отправленное в раунде r, принимается процессом-получателем в том же раунде r. Если в текущем раунде процесс при отправке сообщения приходит к аварийному завершению, то это сообщение получает произвольное (не известное заранее) подмножество процессов.

Основные результаты

Задача согласования k множеств всегда может быть решена в синхронной системе. Основной результат заключается в определении минимального числа раундов ([math]\displaystyle{ R_t }[/math]), необходимых для вычислений с помощью безошибочных процессов в наихудшем сценарии (такой сценарий имеет место, когда в каждом раунде ровно k процессов приходят к аварийному завершению). В работе [3] было показано, что [math]\displaystyle{ R_t = \lfloor \frac{t}{k} \rfloor + 1 }[/math]. Очень простой алгоритм, реализующий эту нижнюю границу, изображен на рис. 1.

    Function k-set_agreement([math]\displaystyle{ v_i }[/math])
(1) [math]\displaystyle{ est_i \gets v_i; }[/math]
(2) when [math]\displaystyle{ r = 1, 2, ..., \lfloor \frac{t}{k} \rfloor + 1 }[/math] do % r: номер раунда %
(3) begin_round
(4)      отправить [math]\displaystyle{ (est_i) }[/math] всем; % включая сам [math]\displaystyle{ p_i }[/math] %
(5)      [math]\displaystyle{ est_i \gets min( \{  }[/math] значения [math]\displaystyle{ (est_i) }[/math], полученные в ходе текущего раунда r});
(6) end_round;
(7) возврат [math]\displaystyle{ (est_i) }[/math]

Рисунок 1. Простой синхронный алгоритм согласования k множеств (код для [math]\displaystyle{ (p_i) }[/math])

Отказы случаются, однако на практике они редки. Обозначим за f количество процессов, приводящих к аварийному завершению в данном прогоне алгоритма, [math]\displaystyle{ 0 \le f \le t }[/math]. Нас интересуют синхронные алгоритмы, которые завершаются максимум за [math]\displaystyle{ R_t }[/math] раундов в случае, когда на текущем прогоне аварийно завершаются t процессов, но которые позволяют безошибочным процессам выполнить вычисление за гораздо меньшее число раундов, если отказов мало. Такие алгоритмы называются алгоритмами с ранним принятием решений. В [4] было показано, что при наличии f аварийных завершений процессов любой алгоритм согласования k множеств с ранним принятием решений имеет прогоны, на которых ни один процесс не принимает решение до раунда [math]\displaystyle{ R_f = min(\lfloor \frac{f}{k} \rfloor + 2, \lfloor \frac{t}{k} \rfloor + 1) }[/math]. Эта нижняя граница показывает неизбежно присущий им компромисс, устанавливающий связь между степенью координации k, максимальным количеством отказов процесса t, фактическим количеством отказов процесса f и наилучшей достижимой временной сложностью. Алгоритмы согласования k множеств с ранним принятием решений для синхронной модели можно найти в [4, 12].

Другие модели возникновения отказов

В модели с отказом из-за пропуска отправки процесс является сбойным, если он приводит к аварийному завершению или забывает отправить сообщения. В модели с отказом из-за любого пропуска процесс является сбойным, если он приводит к аварийному завершению или забывает отправить либо получить сообщения. (Отказ из-за пропуска отправки моделирует отказ выходного буфера, а отказ из-за пропуска получения – отказ входного буфера). Эти модели возникновения отказов были предложены в работе [11].

Понятие сильного завершения для задач о согласовании множеств было введено в [13]. На интуитивном уровне понятно, что это свойство требует, чтобы как можно больше процессов вычислили решение. Назовем хорошим процесс, который не приводит к аварийному завершению и не имеет отказов из-за пропуска. Алгоритм согласования множеств имеет сильное завершение, если при его выполнении все хорошие процессы обязательно вычисляют решение. (Только те процессы, которые приходят к аварийному завершению во время выполнения алгоритма или не получают достаточно сообщений, могут остаться без вычисленного решения).

Алгоритм согласования k множеств с ранним принятием решений для модели с отказом из-за любого пропуска был описан в [13]. Этот алгоритм, которому требуется t < n/2 времени, приводит хороший процесс к принятию решения и остановке максимум за [math]\displaystyle{ R_f = min(\lfloor \frac{f}{k} \rfloor + 2, \lfloor \frac{t}{k} \rfloor + 1) }[/math] раундов. При этом процесс, который не является хорошим, выполняется не более [math]\displaystyle{ R_f(not good) = min(\lceil \frac{f}{k} \rceil + 2, \lceil \frac{t}{k} \rceil + 1) }[/math] раундов.

Поскольку [math]\displaystyle{ R_f }[/math] является нижней границей для числа раундов в модели отказов с аварийным завершением, предыдущий алгоритм показывает, что это значение также является нижней границей для вычисления решения безошибочными процессами в более строгой модели с отказом из-за любого пропуска. Доказательство того, что [math]\displaystyle{ R_f(not good) }[/math] представляет собой верхнюю границу числа раундов, которые должен выполнить процесс, не являющийся хорошим, пока не найдено.

В [13] было показано, что для заданной степени координации k Значение [math]\displaystyle{ t \lt \frac{k}{k+1} n }[/math] является верхней границей числа отказов процессов в случае, когда требуется решить задачу о согласовании k наборов в синхронной системе, подверженной отказам из-за любого пропуска. Алгоритм согласования k множеств, реализующий эту границу, был описан в работе [13]. Этот алгоритм требует, чтобы процессы выполнили R = t + 2 - k раундов перед вычислением решения. Доказательство (или опровержение) того, что R является нижней границей, когда [math]\displaystyle{ t \lt \frac{k}{k+1} n }[/math], по-прежнему является открытым вопросом. Еще одной нерешенной задачей является алгоритм согласования k множеств с ранним принятием решений для [math]\displaystyle{ t \lt \frac{k}{k+1} n }[/math] и k > 1.

Основные результаты в асинхронных системах

Невозможность

Фундаментальным результатом распределенных вычислений является невозможность разработки детерминированного алгоритма, решающего задачу согласования k множеств в асинхронных системах в случае [math]\displaystyle{ k \le t }[/math] [1, 7, 15]. По сравнению с невозможностью решения задачи асинхронного консенсуса, несмотря на аварийное завершение одного процесса, эта невозможность основана на углубленных комбинаторных соображениях. Эта невозможность открыла новые направления в исследовании связи между распределенными вычислениями и топологией. Топологический подход позволил выявить связи, увязывающие асинхронное согласование k множеств с другими задачами распределенных вычислений, такими как задача переименования [5].

Обход невозможности

Было исследовано несколько подходов для обхода упомянутой невозможности; эти подходы аналогичны тем, которые использовались для обхода невозможности асинхронного консенсуса, несмотря на аварийные завершения процесса.

Один из подходов заключается в замене детерминированного алгоритма на рандомизированный. В этом случае свойство завершения формулируется следующим образом: «вероятность вычисления решения правильным процессом стремится к 1, когда число раундов стремится к [math]\displaystyle{ + \infty }[/math]». Этот подход рассматривался в работе [9].

Также был предложен другой подход, основанный на детекторах отказов. Грубо говоря, детектор отказов предоставляет каждому процессу список процессов, которые предположительно были аварийно завершены. В качестве примера можно привести класс детекторов отказов, обозначаемый [math]\displaystyle{ \Diamond S_x} }[/math], который включает все детекторы отказов, такие, что через некоторое конечное (но неизвестное) время (1) любой список содержит аварийно завершенные процессы и (2) существует множество Q процессов x, такое, что Q содержит один правильный процесс, и этот правильный процесс больше не подозревается процессами из Q (заметим, что правильные процессы могут подозреваться периодически или даже всегда). Строгие границы для задачи о согласовании k множеств в асинхронных системах с такими детекторами отказов, предположенные в [9], были доказаны в [6]. Более точно, такой класс детекторов отказов позволяет решить задачу согласования k множеств для [math]\displaystyle{ k \ge t - x + 2 }[/math] [9] и не может решить ее при k < t - x + 2 [6].

Еще один исследованный подход включал комбинацию детекторов отказов и условий [8]. Условие представляет собой набор входных векторов, и каждый входной вектор содержит одну запись на процесс. Записи входного вектора, связанного с прогоном, содержат значения, предложенные процессами в этом прогоне. В принципе такой подход гарантирует, что безошибочные процессы всегда вычисляют решение в случаях, когда фактический входной вектор принадлежит условию, которым инстанциирован алгоритм согласования k множеств.

Применение

Задача согласования множеств была введена для изучения взаимосвязи между количеством отказов и степенью синхронизации в асинхронной системе; таким образом, она имеет в основном теоретический характер. Эта задача рассматривается как каноническая, когда речь идет об асинхронной вычислимости при наличии отказов. Тем не менее, можно представить себе практические задачи, решения которых основаны на задаче согласования множеств (например, распределение небольших совместно используемых ресурсов – таких как частоты вещания – в сети).

См. также

• Невозможность асинхронного консенсуса
• Детекторы отказов
• Переименование
• Топологический подход в распределенных вычислениях

Литература

1. Borowsky, E., Gafni, E.: Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations. In: Proc. 25th ACM Symposium on Theory of Computation, California, 1993, pp. 91-100

2. Chaudhuri, S.: More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Inf. Comput. 105, 132-158(1993)

3. Chaudhuri, S., Herlihy, M., Lynch, N., Tuttle, M.: Tight Bounds for k-Set Agreement. J. ACM 47(5), 912-943 (2000)

4. Gafni, E., Guerraoui, R., Pochon, B.: From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement. In: Proc. 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 714-722. ACM Press, New York (2005)

5. Gafni, E., Rajsbaum, S., Herlihy, M.: Subconsensus Tasks: Renaming is Weaker than Set Agreement. In: Proc. 20th Int'l Symposium on Distributed Computing (DISC'06). LNCS, vol. 4167, pp. 329-338. Springer, Berlin (2006)

6. Herlihy, M.P., Penso, L.D.: Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors. Distrib. Comput. 18(2), 157-166 (2005)

7. Herlihy, M.P., Shavit, N.: The Topological Structure of Asynchronous Computability. J. ACM 46(6), 858-923 (1999)

8. Mostefaoui, A., Rajsbaum, S., Raynal, M.: The Combined Power of Conditions and Failure Detectors to Solve Asynchronous Set Agreement. In: Proc. 24th ACM Symposium on Principles of Distributed Computing (PODC'05), pp. 179-188. ACM Press, New York (2005)

9. Mostefaoui, A., Raynal, M.: k-Set Agreement with Limited Accuracy Failure Detectors. In: Proc. 19th ACM Symposium on Principles of Distributed Computing, pp. 143-152. ACM Press, New York (2000)

10. Mostefaoui, A., Raynal, M.: Randomized Set Agreement. In: Proc. 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA'01), Hersonissos (Crete) pp. 291-297. ACM Press, New York (2001)

11. Perry, K.J., Toueg, S.: Distributed Agreement in the Presence of Processor and Communication Faults. IEEE Trans. Softw. Eng. SE-12(3), 477^82 (1986)

12. Raipin Parvedy, P., Raynal, M., Travers, C.: Early-stopping k-set agreement in synchronous systems prone to any number of process crashes. In: Proc. 8th Int'l Conference on Parallel Computing Technologies (PaCT'05). LNCS, vol. 3606, pp. 49-58. Springer, Berlin (2005)

13. Raipin Parvedy, P., Raynal, M., Travers, C.: Strongly-terminating early-stopping k-set agreement in synchronous systems with general omission failures. In: Proc. 13th Colloquium on Structural Information and Communication Complexity (SIROCCO'06). LNCS, vol. 4056, pp. 182-196. Springer, Berlin (2006)

14. Raynal, M., Travers, C.: Synchronous set agreement: a concise guided tour (including a new algorithm and a list of open problems). In: Proc. 12th Int'l IEEE Pacific Rim Dependable Computing Symposium (PRDC’2006), pp. 267-274. IEEE Society Computer Press, Los Alamitos (2006)

15. Saks, M., Zaharoglou, F.: Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SI AM J. Comput. 29(5), 1449-1483 (2000)