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

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

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