Алгоритм Чанди – Лэмпорта

Алгоритм Чанди-Лампорта — это алгоритм моментального снимка , который используется в распределенных системах для записи согласованного глобального состояния асинхронной системы. Он был разработан и назван в честь Лесли Лэмпорта и К. Мани Чанди . ^{[ 1 ]}

История

Согласно сайту Лесли Лэмпорта , алгоритм снимков был описан, когда они посетили Ченди, который находился в Техасском университете (Остин) . Он изложил проблему за ужином, но они выпили слишком много вина, чтобы думать об этом. На следующее утро, находясь в душе, они нашли решение. Когда они прибыли в офис Ченди, он ждал ее с тем же решением. Они считали этот алгоритм прямым применением основных идей статьи 27, озаглавленной « Время, часы и порядок событий в распределенной системе». ^{[ 2 ]}

Определение

Предположения алгоритма следующие:

Сбоев нет, все сообщения приходят в целости и сохранности только один раз.
Каналы связи являются однонаправленными и FIFO. упорядочены по принципу
Между любыми двумя процессами в системе существует путь связи.
Любой процесс может инициировать алгоритм моментального снимка.
Алгоритм моментальных снимков не мешает нормальному выполнению процессов
Каждый процесс в системе записывает свое локальное состояние и состояние входящих каналов.

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

Некоторые предположения алгоритма можно облегчить, используя более надежный протокол связи, такой как TCP/IP . Алгоритм можно адаптировать таким образом, чтобы одновременно создавалось несколько снимков.

Алгоритм

Алгоритм Чанди – Лэмпорта работает следующим образом:

Процесс-наблюдатель (процесс, делающий снимок):
1. Сохраняет собственное локальное состояние
2. Отправляет сообщение запроса моментального снимка, содержащее токен моментального снимка, всем остальным процессам.
Процесс, впервые получающий токен моментального снимка в любом сообщении:
1. Отправляет процессу-наблюдателю собственное сохраненное состояние.
2. Прикрепляет токен моментального снимка ко всем последующим сообщениям (чтобы облегчить распространение токена моментального снимка).
Когда процесс, который уже получил токен моментального снимка, получает сообщение, не содержащее токен моментального снимка, этот процесс пересылает это сообщение процессу-наблюдателю. Это сообщение, очевидно, было отправлено до того, как снимок был «отрезан» (поскольку оно не содержит токена снимка и, следовательно, должно было быть получено до того, как токен снимка был отправлен), и его необходимо включить в снимок.

На основе этого наблюдатель создает полный снимок: сохраняется сохраненное состояние для каждого процесса и все сообщения «в эфире».

Ссылки

^ Лесли Лэмпорт, К. Мани Чанди: Распределенные снимки: определение глобальных состояний распределенной системы . В: Транзакции ACM в компьютерных системах 3 . № 1 февраля 1985 г. ( PDF; 1 МБ )
^ «Сочинения Лесли Лэмпорт» . lamport.azurewebsites.net . Проверено 24 августа 2024 г.

[1] Лесли Лэмпорт, К. Мани Чанди: Распределенные снимки: определение глобальных состояний распределенной системы . В: Транзакции ACM в компьютерных системах 3 . № 1 февраля 1985 г. ( PDF; 1 МБ )

[2] «Сочинения Лесли Лэмпорт» . lamport.azurewebsites.net . Проверено 24 августа 2024 г.

[ 1 ]

[ 2 ]