Согласование множеств: различия между версиями

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

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

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

Отказы случаются, однако на практике они редки. Обозначим за f количество процессов, приходящих к аварийному завершению в данном прогоне алгоритма, <math>0 \le f \le t</math>. Нас интересуют синхронные алгоритмы, которые завершаются максимум за <math>R_t</math> раундов в случае, когда на текущем прогоне аварийно завершаются t процессов, но которые позволяют безошибочным процессам выполнить вычисление за гораздо меньшее число раундов, если отказов мало. Такие алгоритмы называются ''алгоритмами с ранним вычислением решений''. В [4] было показано, что при наличии f аварийных завершений процессов любой алгоритм согласования k множеств с ранним вычислением решений имеет прогоны, на которых ни один процесс не вычисляет решение до раунда <math>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>R_f = min(\lfloor \frac{f}{k} \rfloor + 2, \lfloor \frac{t}{k} \rfloor + 1)</math> раундов. При этом процесс, который не является хорошим, выполняется не более <math>R_f(not good) = min(\lceil \frac{f}{k} \rceil + 2, \lceil \frac{t}{k} \rceil + 1)</math> раундов.

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

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

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

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

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

* [[Детекторы отказов]]