Алгоритм консенсуса Чандры-Туэга
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Май 2024 г. ) |
Алгоритм консенсуса Чандры-Туэга , опубликованный Тушаром Дипаком Чандрой и Сэмом Туэгом в 1996 году, представляет собой алгоритм для достижения консенсуса в сети ненадежных процессов, оснащенный детектором сильных сбоев . Детектор сбоев — это абстрактная версия таймаутов ; он сигнализирует каждому процессу о возможном сбое других процессов. Детектор устойчивых сбоев — это такой детектор, который никогда не идентифицирует какой-либо конкретный исправный процесс как сбойный после некоторого начального периода замешательства и в то же время в конечном итоге идентифицирует все ошибочные процессы как неудачные (при этом ошибочный процесс — это процесс, который в конечном итоге выходит из строя или выходит из строя, а исправный процесс никогда не дает сбоя). Алгоритм консенсуса Чандры-Туэга предполагает, что количество ошибочных процессов, обозначаемых f , меньше n/2 (т.е. меньшинство), т.е. он предполагает f < n /2, где n — общее количество процессов.
Алгоритм
[ редактировать ]Алгоритм работает в раундах и использует вращающийся координатор: в каждом раунде r процесс, идентичность которого определяется r mod n в качестве координатора выбирается . Каждый процесс отслеживает свое текущее предпочтительное значение решения (первоначально равное входным данным процесса) и последний раунд, в котором он изменил свое значение решения ( временную метку значения ). В каждом раунде выполняются следующие действия:
- Все процессы отправляют (r, предпочтение, метку времени) координатору.
- Координатор ожидает получения сообщений как минимум от половины процессов (включая себя).
- Затем он выбирает в качестве предпочтения значение с самой последней меткой времени среди отправленных.
- Координатор отправляет (r, предпочтение) всем процессам.
- Каждый процесс ожидает (1) получения (r, предпочтения) от координатора или (2) своего детектора сбоев, который идентифицирует координатор как сбойный.
- В первом случае он устанавливает свои собственные предпочтения в соответствии с предпочтениями координатора и отвечает ack(r).
- Во втором случае он отправляет координатору nack(r).
- Координатор ожидает получения ack(r) или nack(r) от большинства процессов.
- Если он получает подтверждение (r) от большинства, он отправляет решение (предпочтение) всем процессам.
- Любой процесс, который впервые получает решение (предпочтение), передает решение (предпочтение) всем процессам, затем определяет предпочтение и завершается.
Обратите внимание, что этот алгоритм используется для принятия решения только по одному значению.
Корректность
[ редактировать ]Определение проблемы
[ редактировать ]Алгоритм, «решающий» проблему консенсуса, должен обеспечивать следующие свойства:
- завершение: все процессы принимают решение о значении;
- соглашение: все процессы принимают одно и то же значение; и
- достоверность: все процессы выбирают значение, которое было входным значением некоторого процесса;
Предположения
[ редактировать ]Прежде чем утверждать, что алгоритм консенсуса Чандры-Туэга удовлетворяет трем вышеперечисленным свойствам, напомним, что этот алгоритм требует n = 2* f + 1 процессов, из которых не более f являются ошибочными.
Кроме того, обратите внимание, что этот алгоритм предполагает наличие детектора сильных сбоев (который доступен и может использоваться для обнаружения сбоя узла). Детектор сильного сбоя — это такой детектор, который никогда не идентифицирует какой-либо конкретный исправный (или правильный) процесс как сбойный после некоторого начального периода путаницы и в то же время в конечном итоге идентифицирует все ошибочные процессы как сбойные.
Доказательство правильности
[ редактировать ]Завершение сохраняется, поскольку в конечном итоге детектор сбоев перестает подозревать какой-либо исправный процесс p, и в конечном итоге p становится координатором. Если алгоритм не завершился до того, как это произошло в каком-то раунде r, то каждый исправный процесс в раунде r ожидает получения предпочтения p и отвечает ack(r). Это позволяет p собрать достаточно подтверждений для отправки решения (предпочтения), что приводит к завершению каждого процесса. Альтернативно, может случиться так, что какой-то неисправный координатор отправит решение только нескольким процессам; но если какой-либо из этих процессов исправен, они передают решение всем остальным процессам, заставляя их принять решение и завершить работу.
Валидность следует из того факта, что каждое предпочтение начинается с входных данных некоторого процесса; в протоколе нет ничего, что могло бы генерировать новые предпочтения.
Соглашение потенциально является наиболее трудным для достижения. Вполне возможно, что координатор в одном раунде r может отправить сообщение о решении из некоторого значения v, которое распространяется только на несколько процессов, прежде чем какой-либо другой координатор в более позднем раунде r' отправит сообщение о решении для некоторого другого значения v. '. Чтобы показать, что этого не происходит, заметим, что прежде чем первый координатор сможет отправить Decision(v), он должен получить ack(r) от большинства процессов; но затем, когда какой-либо более поздний координатор опрашивает большинство процессов, более позднее большинство будет перекрывать более раннее, и v будет самым последним значением. Таким образом, любые два координатора, отправляющие сообщение о решении, отправляют одно и то же значение.