Введение в надежное и безопасное распределенное программирование

Введение в надежное и безопасное 
распределенное программирование

Кристиан Качин, Рашид Гуерру, Луис Родригес

Introduction to 
Reliable and Secure 
Distributed Programming

Christian Cachin, Rachid Guerraoui, Lus Rodrigues

Введение в надежное  
и безопасное распределенное 
программирование

Москва, 2023

Кристиан Качин, Рашид Гуерру, Луис Родригес

2-е издание, электронное

УДК 004.42
ББК 32.973
К31

К31
Качин, Кристиан.
Введение в надежное и безопасное распределенное программирование / К. Качин, Р. Гуерру, Л. Родригес ; пер. с англ. А. Н. Киселёва. — 2-е изд., эл. — 1 файл pdf : 513 с. — Москва : 
ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; 
экран 10". — Текст : электронный.
ISBN 978-5-89818-626-5

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

УДК 004.42 
ББК 32.973

Электронное издание на основе печатного издания: Введение в надежное и безопасное распределенное программирование / К. Качин, Р. Гуерру, Л. Родригес ; пер. с англ. А. Н. Киселёва. — Москва : ДМК Пресс, 2015. — 512 с. — 
ISBN 978-5-97060-369-7. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, 
правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-626-5
© Springer-Verlag Berlin Heidelberg 2011, 2006 
© Оформление, перевод, ДМК Пресс, 2016

Содержание

Предисловие ......................................................... 13

Глава 1. Введение ................................................... 19

1.1. Обоснование...........................................................................................................................19
1.2. Абстракции распределенного программирования ...................................................21
1.2.1. Естественно распределенные системы ...............................................................22
1.2.2. Искусственно распределенные системы ...........................................................25
1.3. Сквозной аргумент ..............................................................................................................26
1.4. Программные компоненты ...............................................................................................27
1.4.1. Композиционная модель .........................................................................................27
1.4.2. Программный интерфейс .......................................................................................30
1.4.3. Модули ..........................................................................................................................32
1.5. Классы алгоритмов ..............................................................................................................36
1.6. Практикум ..............................................................................................................................37
1.6.1. Модуль Print ...............................................................................................................37
1.6.2. Модуль BoundedPrint ..............................................................................................39
1.6.3. Объединение модулей..............................................................................................43
1.6.4. Эксперимент ................................................................................................................44
1.7. Примечания к главе .............................................................................................................45

Глава 2. Базовые абстракции .................................... 46

2.1. Распределенные вычисления ...........................................................................................47
2.1.1. Процессы и сообщения ............................................................................................47
2.1.2. Автоматы и шаги ........................................................................................................47
2.1.3. Безопасность и живучесть ......................................................................................49
2.2. Абстракции процессов ........................................................................................................51
2.2.1. Отказы процессов ......................................................................................................51
2.2.2. Аварии ...........................................................................................................................51
2.2.3. Пропуск данных .........................................................................................................53
2.2.4. Аварии с восстановлением .....................................................................................53
2.2.5. Перехват сообщений .................................................................................................56
2.2.6. Произвольное поведение ........................................................................................56
2.3. Криптографические абстракции .....................................................................................58
2.3.1. Хэш-функции ..............................................................................................................58
2.3.2. Коды аутентификации сообщений ......................................................................58
2.3.3. Цифровые подписи ...................................................................................................59
2.4. Абстракции связи .................................................................................................................60
2.4.1. Отказы связи ...............................................................................................................61
2.4.2. Связи с приемлемыми потерями .........................................................................63

Содержание

2.4.3. Связи с повторами.....................................................................................................63
2.4.4. Идеальные связи ........................................................................................................65
2.4.5. Идеальные связи с журналированием ...............................................................67
2.4.6. Идеальная связь с аутентификацией ..................................................................70
2.4.7. Об абстракциях связей ............................................................................................72
2.5. Предположения о синхронности ....................................................................................74
2.5.1. Асинхронные системы .............................................................................................74
2.5.2. Синхронные системы ...............................................................................................75
2.5.3. Частичная синхронность ........................................................................................77
2.6. Абстракция времени ............................................................................................................78
2.6.1. Обнаружение отказов ..............................................................................................78
2.6.2. Идеальное обнаружение отказа ............................................................................79
2.6.3. Выбор лидера ..............................................................................................................82
2.6.4. Эвентуально идеальный датчик отказов ...........................................................84
2.6.5. Эвентуальный выбор лидера .................................................................................87
2.6.6. Византийский выбор лидера .................................................................................91
2.7. Модели распределенных систем .....................................................................................94
2.7.1. Комбинации абстракций .........................................................................................95
2.7.2. Подготовка ...................................................................................................................96
2.7.3. Кворумы ........................................................................................................................97
2.7.4. Измерение стоимости алгоритмов ......................................................................98
2.8. Упражнения ............................................................................................................................99
2.9. Решения ................................................................................................................................ 100
2.10. Практикум ......................................................................................................................... 103
2.10.1. Передаваемое событие ........................................................................................ 103
2.10.2. Сообщение .............................................................................................................. 104
2.10.3. Связь «точка-точка» с приемлемыми потерями ....................................... 105
2.10.4. Идеальная связь «точка-точка» ...................................................................... 105
2.10.5. Идеальный датчик отказов ............................................................................... 106
2.11. Примечания к главе........................................................................................................ 108

Глава 3. Надежная рассылка ....................................111

3.1. Обоснование........................................................................................................................ 111
3.1.1. Клиент-серверные вычисления ......................................................................... 111
3.1.2. Системы со множеством участников ............................................................... 112
3.2. Негарантированная рассылка ....................................................................................... 113
3.2.1. Спецификация ......................................................................................................... 113
3.2.2. Алгоритм простой рассылки ............................................................................... 114
3.3. Обычная надежная рассылка ........................................................................................ 115
3.3.1. Спецификация ......................................................................................................... 115
3.3.2. Алгоритм для модели с остановкой после отказов: ленивая  
надежная рассылка ............................................................................................................ 116
3.3.3. Алгоритм для модели без уведомления об отказах: жадная  
надежная рассылка ............................................................................................................ 118

Содержание 7

3.4. Унифицированная надежная рассылка ..................................................................... 120
3.4.1. Спецификация ......................................................................................................... 120
3.4.2. Алгоритм для модели с остановкой после отказов:  
унифицированная надежная рассылка с подтверждением всеми .........................121
3.4.3. Алгоритм для модели без уведомления об отказах:  
унифицированная надежная рассылка с подтверждением большинством ..... 124
3.5. Рассылка с повторами ...................................................................................................... 125
3.5.1. Спецификация ......................................................................................................... 125
3.5.2. Алгоритм для модели с восстановлением после отказов: простая  
рассылка с повторами ...................................................................................................... 126
3.6. Негарантированная рассылка с журналированием............................................... 127
3.6.1. Обзор ........................................................................................................................... 127
3.6.2. Спецификация ......................................................................................................... 128
3.6.3. Алгоритм для модели с восстановлением после отказов: простая  
рассылка с журналированием ....................................................................................... 129
3.7. Унифицированная надежная рассылка с журналированием ............................. 130
3.7.1. Спецификация ......................................................................................................... 130 
3.7.2. Алгоритм для модели с восстановлением после отказов:  
Унифицированная надежная рассылка с подтверждением  
большинством и журналированием ............................................................................ 131
3.8. Вероятностная рассылка ................................................................................................. 132
3.8.1. Масштабируемость надежной рассылки ........................................................ 133
3.8.2. Распространение эпидемии ................................................................................ 134
3.8.3. Спецификация ......................................................................................................... 134
3.8.4. Рандомизированный алгоритм: жадная вероятностная рассылка ........ 135
3.8.5. Рандомизированный алгоритм: ленивая вероятностная рассылка ...... 138
3.9. Рассылка в порядке FIFO и причинная рассылка ................................................. 142
3.9.1. Обзор ........................................................................................................................... 142
3.9.2. Спецификация порядка FIFO ........................................................................... 143
3.9.3. Алгоритм для модели без уведомления об отказах: рассылка  
с использованием последовательных номеров ....................................................... 143
3.9.4. Спецификация причинно-следственного порядка ..................................... 144
3.9.5. Алгоритм для модели без уведомления об отказах: рассылка  
в причинно-следственном порядке без ожидания ................................................. 146
3.9.6. Алгоритм для модели с остановкой после отказов: сборка мусора  
причинно-следственного прошлого ............................................................................ 148
3.9.7. Алгоритм для модели без уведомления об отказах:  
причинно-следственная рассылка с ожиданием .................................................... 150
3.10. Византийская согласованная рассылка .................................................................. 152
3.10.1. Обоснование .......................................................................................................... 153
3.10.2. Спецификация ...................................................................................................... 154
3.10.3. Алгоритм для модели с произвольным поведением:  
эхо-рассылка с аутентификацией ................................................................................ 155

Содержание

3.10.4. Алгоритм для модели с произвольным поведением:  
эхо-рассылка с подписанными сообщениями ......................................................... 158
3.11. Византийская надежная рассылка ............................................................................ 160
3.11.1. Спецификация ...................................................................................................... 160
3.11.2. Алгоритм для модели с произвольным поведением: двойная  
эхо-рассылка с аутентификацией ................................................................................ 161
3.12. Византийские широковещательные каналы ......................................................... 164
3.12.1. Спецификации ...................................................................................................... 164
3.12.2. Алгоритм для модели с произвольным поведением:  
Византийский согласованный канал .......................................................................... 166
3.12.3. Алгоритм для модели с произвольным поведением:  
Византийский надежный канал ................................................................................... 167
3.13. Упражнения....................................................................................................................... 167
3.14. Решения .............................................................................................................................. 169
3.15. Практикум ......................................................................................................................... 178
3.15.1. Простая рассылка ................................................................................................. 178
3.15.2. Ленивая надежная рассылка ............................................................................ 181
3.15.3. Унифицированная надежная рассылка с подтверждением всеми ...... 184
3.15.4. Унифицированная надежная рассылка с подтверждением  
большинством ..................................................................................................................... 187
3.15.5. Вероятностная надежная рассылка ............................................................... 188
3.15.6. Рассылка в причинно-следственном порядке без ожидания ................ 191
3.15.7. Рассылка в причинно-следственном порядке без ожидания  
и с уборкой мусора ............................................................................................................ 197
3.15.8. Рассылка в причинно-следственном порядке с ожиданием ................. 204
3.16. Примечания к главе........................................................................................................ 208

Глава 4. Разделяемая память ..................................210

4.1. Введение ............................................................................................................................... 211
4.1.1. Разделяемое хранилище в распределенной системе .................................. 211
4.1.2. Регистр ....................................................................................................................... 211
4.1.3. Завершенность и предшествование ................................................................. 214
4.2. Обычный регистр (1, N) .................................................................................................. 216
4.2.1. Спецификация ......................................................................................................... 216
4.2.2. Алгоритм для модели с остановкой после отказов: обычный  
регистр «Чтение в одном – запись во всех» ............................................................. 217
4.2.3. Алгоритм для модели без уведомления об отказах: обычный  
регистр с голосованием большинством ..................................................................... 220
4.3. Атомарный регистр (1, N)............................................................................................... 223
4.3.1. Спецификация ......................................................................................................... 223
4.3.2. Преобразование обычного регистра (1, N) в атомарный  
регистр (1, N)  ...................................................................................................................... 226

Содержание 9

4.3.3. Алгоритм атомарного регистра для модели с остановкой после  
отказов: чтение с записью – запись во всех .............................................................. 231
4.3.4. Алгоритм атомарного регистра для модели без уведомления  
об отказах: чтение с записью – запись в большинстве ......................................... 233
4.4. Атомарный регистр (N, N)  ............................................................................................. 235
4.4.1. Несколько пишущих процессов ........................................................................ 235
4.4.2. Спецификация ......................................................................................................... 236
4.4.3. Преобразование атомарного регистра (1, N) в атомарный  
регистр (N, N) ...................................................................................................................... 237
4.4.4. Алгоритм для модели с остановкой после отказов:  
чтение с записью – запись с проверкой во всех ...................................................... 241
4.4.5. Алгоритм для модели без уведомления об отказах:  
чтение с записью – запись с проверкой в большинстве ....................................... 244
4.5. Обычный регистр (1, N) с журналированием ......................................................... 247
4.5.1. Предшествование в модели с восстановлением после отказов .............. 247
4.5.2. Спецификация ......................................................................................................... 248
4.5.3. Алгоритм для модели с восстановлением после отказов:  
голосование большинством с журналированием ................................................... 250
4.6. Византийский безопасный регистр (1, N) ................................................................ 253
4.6.1. Спецификация ......................................................................................................... 254
4.6.2. Алгоритм для модели с произвольным поведением после отказов:  
Византийский маскирующий кворум ........................................................................ 255
4.7. Византийский обычный регистр (1, N) ..................................................................... 257
4.7.1. Спецификация ......................................................................................................... 258
4.7.2. Алгоритм для модели с произвольным поведением:  
Аутентификация данных Византийским кворумом .............................................. 258
4.7.3. Алгоритм для модели с произвольным поведением после отказов:  
Византийский кворум с двухфазной записью ......................................................... 261
4.8. Византийский атомарный регистр (1, N) .................................................................. 268
4.8.1. Спецификация ......................................................................................................... 268
4.8.2. Алгоритм для модели с произвольным поведением после отказов:  
Византийский кворум со слушателями ..................................................................... 269
4.9. Упражнения ......................................................................................................................... 273
4.10. Решения .............................................................................................................................. 274
4.11. Практикум ......................................................................................................................... 280
4.11.1. Обычный регистр (1, N) ..................................................................................... 280
4.11.2. Атомарный регистр (1, N) ................................................................................. 284
4.11.3. Атомарный регистр (N, N) ................................................................................. 288
4.12. Примечания к главе........................................................................................................ 292

Глава 5. Консенсусы ...............................................296

5.1. Обычный консенсус ......................................................................................................... 297
5.1.1. Спецификация ......................................................................................................... 297

Содержание

5.1.2. Алгоритм для модели с остановкой после отказов: консенсус  
заполнением ........................................................................................................................ 298
5.1.3. Алгоритм для модели с остановкой после отказов: иерархический  
консенсус .............................................................................................................................. 302
5.2. Унифицированный консенсус ...................................................................................... 305
5.2.1. Спецификация ......................................................................................................... 305
5.2.2. Алгоритм для модели с остановкой после отказов:  
унифицированный консенсус с заполнением ......................................................... 306
5.2.3. Алгоритм для модели с остановкой после отказов:  
унифицированный иерархический консенсус ........................................................ 308
5.3. Унифицированный консенсус для модели с уведомлением об отказах ......... 311
5.3.1. Обзор ........................................................................................................................... 311
5.3.2. Смена эпох ................................................................................................................ 312
5.3.3. Консенсус эпохи ...................................................................................................... 316
5.3.4. Алгоритм для модели с уведомлением об отказах: консенсус  
с лидером .............................................................................................................................. 322
5.4. Консенсус с журналированием .................................................................................... 325
5.4.1. Спецификация ......................................................................................................... 325
5.4.2. Смена эпох с журналированием ........................................................................ 327
5.4.3. Консенсус эпохи с журналированием ............................................................. 328
5.4.4. Алгоритм для модели с восстановлением после отказов:  
консенсус с лидером и журналированием ................................................................ 332
5.5. Рандомизированный консенсус ................................................................................... 333
5.5.1. Спецификация ......................................................................................................... 334
5.5.2. Общая монета .......................................................................................................... 335
5.5.3. Рандомизированный алгоритм для модели без уведомления  
об отказах: рандомизированный двоичный консенсус ........................................ 336
5.5.4. Рандомизированный алгоритм для модели без уведомления  
об отказах: рандомизированный консенсус с большой областью выбора ..... 341
5.6. Византийский консенсус ................................................................................................ 343
5.6.1. Спецификация ......................................................................................................... 343
5.6.2. Византийская смена эпох .................................................................................... 346
5.6.3. Византийский консенсус эпохи ......................................................................... 348
5.6.4. Алгоритм для модели с уведомлением об отказах и произвольным  
поведением после отказов: Византийский консенсус с лидером ..................... 360
5.7. Византийский рандомизированный консенсус ...................................................... 362
5.7.1. Спецификация ......................................................................................................... 362
5.7.2. Рандомизированный алгоритм для модели с произвольным  
поведением после отказов: Византийский рандомизированный  
двоичный консенсус ......................................................................................................... 362
5.8. Упражнения ......................................................................................................................... 367
5.9. Решения ................................................................................................................................ 369
5.10. Практикум ......................................................................................................................... 380