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

  (4)      ''отправить'' <math>(est_i)</math> ''всем''; % включая сам <nath>p_i</math> %

Отказы случаются, однако на практике они редки. Обозначим за f количество процессов, приводящих к аварийному завершению в данном прогоне алгоритма, 0 < f < t. Нас интересуют синхронные алгоритмы, которые завершаются максимум за <math>R_t</math> раундов в случае, когда на текущем прогоне аварийно завершаются t процессов, но которые позволяют безошибочным процессам выполнить вычисление за гораздо меньшее число раундов, если отказов мало. Такие алгоритмы называются алгоритмами с ранним принятием решений. В [ ] было показано, что при наличии f аварийных завершений процессов любой алгоритм согласования k множеств с ранним принятием решений имеет прогоны, на которых ни один процесс не принимает решение до раунда Rf = min(bkfc + 2; bktc + 1). Эта нижняя граница показывает неизбежно присущий им компромисс, устанавливающий связь между степенью координации k, максимальным количеством отказов процесса t, фактическим количеством отказов процесса f и наилучшей достижимой временной сложностью. Алгоритмы согласования k множеств с ранним принятием решений для синхронной модели можно найти в [4, 12].

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

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

Алгоритм согласования k множеств с ранним принятием решений для модели с отказом из-за любого пропуска был описан в [13]. Этот алгоритм, которому требуется t < n/2 времени, приводит хороший процесс к принятию решения и остановке максимум за Rf = min(bkfc + 2; bktc + 1) раундов. При этом процесс, который не является хорошим, выполняется не более Rf(not_good) = min(dkfe + 2, [|j + 1) раундов.

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

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