Невозможность асинхронного консенсуса: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим распределенную систему, состоящую из множества ''процессов'', которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляет собой | Рассмотрим распределенную систему, состоящую из множества ''процессов'', которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляет собой мультимножество сообщений, где каждое сообщение адресовано некоторому процессу. Процесс – это машина состояний, которая может выполнять три вида ''шагов''. | ||
• На шаге ''отправки'' (step) процесс помещает сообщение в сеть. | • На шаге ''отправки'' (step) процесс помещает сообщение в сеть. | ||
| Строка 15: | Строка 15: | ||
В ''задаче о достижении консенсуса'' каждый процесс начинает работу с частного ''входного'' значения, | В ''задаче о достижении консенсуса'' каждый процесс начинает работу с частного ''входного'' значения, взаимодействует с остальными, а затем останавливается с найденным значением ''решения''. Такие значения должны удовлетворять следующим свойствам: | ||
• ''Согласованность'': значения решений всех процессов должны совпадать. | • ''Согласованность'': значения решений всех процессов должны совпадать. | ||
• ''Допустимость'': каждое значение решения должно быть | • ''Допустимость'': каждое значение решения должно быть входным значением некоторого процесса. | ||
• ''Завершение'': каждый процесс без сбоев должен принять решение за конечное число шагов. | • ''Завершение'': каждый процесс без сбоев должен принять решение за конечное число шагов. | ||