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

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

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

В [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.