Распределенное взаимное исключение и выбор лидера

Взаимное исключение и выбор лидера — это классические задачи координации: обеспечение того, чтобы не более одного процесса обращалось к критическому ресурсу, и выбор одного выделенного координатора среди равных.

Definition

Распределенное взаимное исключение гарантирует, что не более одного процесса одновременно владеет общим ресурсом, обеспечивая при этом в конечном итоге доступ для всех запрашивающих; выбор лидера детерминированно выбирает ровно один процесс в качестве координатора, при этом все процессы соглашаются с результатом.

Scope

Эта тема охватывает алгоритмы взаимного исключения, основанные на разрешениях (алгоритм временных меток Лэмпорта, Рикарта-Агравалы, кворумный подход Маэкавы) и алгоритмы, основанные на токенах, наряду с их сложностью по количеству сообщений и свойствами справедливости; а также алгоритмы выбора лидера для колец (Чанг-Робертс) и общих сетей (алгоритм «задиры»), включая их предположения об идентификаторах и синхронности. Эти примитивы постоянно используются в службах координации и реплицированных системах.

Core questions

• Как процессы могут сериализовать доступ к общему ресурсу, используя только сообщения?
• Каковы компромиссы между сложностью по количеству сообщений и справедливостью в схемах, основанных на разрешениях, и схемах, основанных на токенах?
• Как выбирается уникальный лидер и как повторно запускается выбор после сбоя лидера?

Key theories

Взаимное исключение, основанное на разрешениях

Алгоритмы, такие как Рикарта-Агравалы, упорядочивают запросы по логическим временным меткам и предоставляют доступ после того, как запрашивающий получил разрешение от всех (или кворума) равных узлов, достигая справедливости с ограниченной стоимостью сообщений на вход в критическую секцию.

Взаимное исключение, основанное на токенах

Уникальный токен циркулирует или запрашивается по требованию, и только его держатель может войти в критическую секцию, что снижает трафик сообщений, но требует механизмов для восстановления потерянного токена после сбоев.

Выбор лидера

Алгоритмы выбора, такие как Чанг-Робертс для колец и алгоритм «задиры» для общих сетей, используют идентификаторы процессов для схождения к единому координатору с наивысшим приоритетом, который признают все корректные процессы.

Clinical relevance

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

History

В статье Лэмпорта 1978 года о логических часах был представлен алгоритм взаимного исключения, основанный на временных метках; Рикарт и Агравала оптимизировали его в 1981 году, Маэкава вскоре после этого ввел кворумы, а алгоритм «задиры» Гарсиа-Молины 1982 года формализовал выбор лидера, предоставив этой области канонические алгоритмы координации.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

Чем распределенное взаимное исключение отличается от блокировки на одной машине?

Отсутствует общая память или центральный менеджер блокировок, на которые можно было бы полагаться, поэтому процессы должны координироваться исключительно путем обмена сообщениями и должны явно обрабатывать задержки сообщений и сбои, что блокировка на одной машине может принимать как должное.