Топологический подход в распределенных вычислениях: различия между версиями

Комплекс 0-связен, если он является связным в теоретико-графовом смысле; комплекс k-связен, если он не имеет дыр в размерности k или более низких. Определение k-связности может показаться сложным, но, к счастью, рассуждения о связности можно проводить комбинаторно, используя следующее элементарное следствие из последовательности Майера-Вьеториса.

'''Теорема 2. Если <math>\mathcal{K}</math> и <math>\mathcal{L}</math> – комплексы, такие, что <math>\mathcal{K}</math> и <math>\mathcal{L}</math> k-связны, а <math>\mathcal{K} \cap \mathcal{L}</math> (k-1)-связен, то <math>\mathcal{K} \cup \mathcal{L}</math> k-связен.'''

Множество n + 1 последовательных ''процессов'' взаимодействует между собой, посылая друг другу сообщения или выполняя операции над общими объектами. В любой момент процесс может претерпеть ''сбой'': он останавливается и больше не делает никаких шагов. Существует ограничение f на количество процессов, которые могут окончиться сбоями. Разные модели различаются по своим предположениям о времени. На одном конце спектра находится ''синхронная модель'', в которой вычисления производятся в виде последовательности раундов. В каждом раунде процесс отправляет сообщения другим процессам, получает сообщения, отправленные ему другими процессами в этом раунде, и меняет свое состояние. (Либо не обменивается сообщениями, а выполняет операции над общими объектами). Все процессы выполняют шаги с одинаковой скоростью, все сообщения доставляются за одно и то же время. На противоположном конце располагается ''асинхронная модель'', в которой нет ограничений на время, которое может пройти между шагами процесса, и на время, которое может потребоваться для доставки сообщения. Между этими крайностями находится ''полусинхронная модель'', в которой время выполнения шагов процесса и время доставки сообщений могут меняться, но ограничены постоянными верхней и нижней границами. Доказательство нижней границы в любой из этих моделей требует глубокого понимания глобальных состояний, которые могут возникнуть в ходе выполнения протокола, и того, как эти глобальные состояния связаны между собой.

В задаче согласования k множеств [5] процессы должны: (1) выбрать значение решения после конечного числа шагов, (2) выбрать в качестве значения решения некоторое входное значение процесса и (3) коллективно выбрать не более k различных значений решения. При k = 1 эта задача обычно называется ''задачей о консенсусе'' [16].