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

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

История

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

Определение

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

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

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

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

Алгоритм

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

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

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

Ссылки

1. Лесли Лампорт, К. Мани Чанди: Распределенные снимки: определение глобальных состояний распределенной системы. В: ACM Transactions on Computer Systems 3. Nr. 1, февраль 1985 г. (PDF; 1 МБ)
2. "Трудности Лесли Лэмпорта". lamport.azurewebsites.net . Получено 2024-08-24 .