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

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

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

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

Содержание 11

5.10.1. Протокол обычного консенсуса заполнением............................................ 380
5.10.2. Протокол обычного иерархического консенсуса ...................................... 385
5.10.3. Унифицированный консенсус заполнением............................................... 389
5.10.4. Унифицированный иерархический консенсус .......................................... 392
5.11. Примечания к главе........................................................................................................ 396

Глава 6. Варианты консенсуса .................................400

6.1. Рассылка в едином порядке ........................................................................................... 400
6.1.1. Обзор ........................................................................................................................... 400
6.1.2. Спецификации......................................................................................................... 402
6.1.3. Алгоритм для модели без уведомления об отказах: рассылка  
в едином порядке на основе консенсуса .................................................................... 404
6.2. Византийская рассылка в едином порядке .............................................................. 407
6.2.1. Обзор ........................................................................................................................... 407
6.2.2. Спецификация ......................................................................................................... 408
6.2.3. Алгоритм для модели с уведомлением об отказах и произвольным  
поведением после отказов: Византийская рассылка с ротацией  
отправителя ......................................................................................................................... 408
6.3. Обрывающаяся надежная рассылка ........................................................................... 413
6.3.1. Обзор ........................................................................................................................... 413
6.3.2. Спецификация ......................................................................................................... 414
6.3.3. Алгоритм для модели с остановкой после отказов:  
унифицированная обрывающаяся надежная рассылка на основе  
консенсуса ............................................................................................................................ 414
6.4. Быстрый консенсус........................................................................................................... 417
6.4.1. Обзор ........................................................................................................................... 417
6.4.2. Спецификация ......................................................................................................... 418
6.4.3. Алгоритм для модели без уведомления об отказах:  
от унифицированного консенсуса к унифицированному быстрому  
консенсусу ............................................................................................................................ 419
6.5. Быстрый Византийский консенсус ............................................................................. 422
6.5.1. Обзор ........................................................................................................................... 422
6.5.2. Спецификация ......................................................................................................... 422
6.5.3. Алгоритм для модели с произвольным поведением:  
от Византийского консенсуса к быстрому Византийскому консенсусу ........ 423
6.6. Неблокирующее атомарное подтверждение ............................................................ 425
6.6.1. Обзор ........................................................................................................................... 425
6.6.2. Спецификация ......................................................................................................... 427
6.6.3. Алгоритм для модели с остановкой после отказов:  
неблокирующее атомарное подтверждение на основе консенсуса .................. 427
6.7. Членство в группах ........................................................................................................... 430
6.7.1. Обзор ........................................................................................................................... 430
6.7.2. Спецификация ......................................................................................................... 431

Содержание

6.7.3. Алгоритм для модели с остановкой после отказов: членство  
в группе на основе консенсуса ...................................................................................... 432
6.8. Синхронизация взаимодействий с представлением ............................................. 435
6.8.1. Обзор ........................................................................................................................... 435
6.8.2. Спецификация ......................................................................................................... 436
6.8.3. Алгоритм для модели с остановкой после отказов: синхронизация  
взаимодействий с представлением на основе TRB ................................................ 438
6.8.4. Алгоритм для модели с остановкой после отказов:  
унифицированная синхронизация взаимодействий с представлением ......... 443
6.9. Упражнения ......................................................................................................................... 447
6.10. Решения .............................................................................................................................. 449
6.11. Практикум ......................................................................................................................... 464
6.11.1. Унифицированная рассылка в едином порядке ........................................ 464
6.11.2. Неблокирующее атомарное подтверждение на основе  
консенсуса ............................................................................................................................ 471
6.11.3. Членство в группе на основе консенсуса ..................................................... 474
6.11.4. Синхронизация с представлением на основе TRB ................................... 478
6.12. Примечания к главе........................................................................................................ 485

Глава 7. Заключительные замечания ........................488

7.1. Реализация в Appia ........................................................................................................... 488
7.2. Дополнительные реализации ........................................................................................ 489
7.3. Для дальнейшего чтения ................................................................................................ 491

Использованная литература ....................................493

Список модулей ....................................................501

Список алгоритмов ................................................503

Предметный указатель ...........................................506

Предисловие

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

Содержание

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

Предисловие

Книга знакомит с разными абстракциями распределенного программирования 
и описывает алгоритмы для их реализации. В некотором смысле мы даем прикладному 
программисту библиотеку спецификаций абстрактных интерфейсов, а системному 
программисту – библиотеку алгоритмов для реализации этих специ фи-
каций.
Работая над этой книгой, мы потратили много времени, чтобы сформировать 
коллекцию упражнений и их решений. Мы настоятельно рекомендуем читателям 
проработать эти упражнения. Никакие знания и навыки не могут быть приобретены 
пассивным путем. Это особенно верно в области распределенных вычислений, 
где человеческий разум часто стремится следовать за привлекательными, но ошибочными 
представлениями. Книга также включает решения для всех упражнений, 
чтобы подчеркнуть наше намерение сделать их неотъемлемой частью содержимого 
книги. Многие упражнения просты и могут решаться коллективно. Другие – 
сложнее и требуют больше времени. Как правило, такие упражнения решаются 
индивидуально.

Представление

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

Организация 15

Организация

Эта книга содержит шесть глав в двух частях. Первая часть строит общую платформу.

В главе 1 мы обоснуем необходимость абстракций распределенного программирования, 
обсудив некоторые приложения, где используются эти абстракции. 
В этой главе также будут представлены блочная форма записи и псевдокод, используемые 
для записи алгоритмов в книге.
В главе 2 будут представлены разного рода допущения и предположения о распределенной 
среде. С этой целью мы введем в обиход семейство моделей распределенных 
систем. В основном модели описывают низкоуровневые абстракции, 
на которых будут строиться абстракции более высокого уровня. К числу таких 
абстракций относятся абстракции процесса и связей. Эту главу можно рассматривать 
как справочник для других глав.
Остальные четыре главы составляют вторую часть книги. Каждая глава посвящена 
одной проблеме, содержащей широкий класс абстракций, и разным алгоритмам 
их реализации. Мы будем двигаться от простых абстракций к сложным.
В главе 3 мы введем абстракции обмена данными для распределенного программирования. 
Они описывают широковещательную рассылку сообщений группам 
процессов и предлагают разные гарантии надежности доставки сообщений процессам. 
Например, мы обсудим, как гарантировать, что сообщение, доставленное 
одному процессу, будет доставлено всем другим процессам, даже в случае аварийного 
завершения процесса-отправителя.
В главе 4 мы обсудим абстракции разделяемой памяти как простые формы распределенных 
хранилищ объектов, доступных для чтения и записи. Это могут быть 
файлы в распределенной системе хранения или регистры в памяти многопроцессорного 
компьютера. Мы охватим методы чтения и записи данных клиентами, 
такие, что значения, хранимые множеством процессов, позднее могут быть получены, 
даже если некоторые из процессов потерпели аварию, стерли свои значения 
или записали ошибочные данные.
В главе 5 мы обратимся к абстракциям консенсуса, с помощью которых множество 
процессов может приходить к общему решению, опираясь на исходные 
данные, изначально предложенные процессами. Они могут приходить к тому же 
решению, несмотря на отказы в отдельных процессах, которые могут не только 
завершаться аварийно, но и активно препятствовать принятию общего решения. 
В главе 6 мы рассмотрим варианты консенсуса, которые могут быть получены 
расширением или адаптацией абстракции консенсуса в соответствии с потребностями 
приложений. Сюда входят рассылка в едином порядке (total-order broad-
cast), надежная рассылка с ограничениями, атомарная (неблокирующая) фиксация, 
членство в группах и синхронные взаимодействия.
Распределенные алгоритмы, которые мы будем обсуждать, отличаются не 
только фактическими абстракциями, которые они реализуют, но также набором 
предположений и допущений о распределенной среде. Начальное множество абстракций, 
которое алгоритм считает самим собой разумеющимся, мы назвали мо-

Предисловие

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

Изменения во втором издании

Это издание является полностью пересмотренной версией первого издания. Обновлениям 
подверглась большая часть книги. Но самое большое изменение произошло 
в области охватываемых тем, число которых увеличилось и дополнилось 
темой обеспечения безопасности против злонамеренных действий. Абстракции 
и алгоритмы в модели распределенных вычислений, где допускается вероятность 
злонамеренных действий, известны как Византийская модель сбоев (Byzantine 
fault-tolerance), или модель с произвольным поведением после сбоев.
Первое издание книги называлось «Introduction to Reliable Distributed Program-
ming». Добавление одного слова («secure» – «безопасное») в название и увеличение 
числа соавторов отражает развитие сферы распределенных систем в современном 
мире. Еще в 2006 году, когда вышло первое издание книги, было очевидно, 
что большинство действующих распределенных систем постоянно находится под 
угрозой вторжения и что штатных сотрудников, имеющих доступ к конфиденциальной 
информации, нельзя исключать из списка потенциальных злоумышленников. 
Для создания надежных распределенных систем в настоящее время требуются 
серьезные усилия, с привлечением знаний распределенных алгоритмов, 
методов обеспечения безопасности и из других областей.
С технической точки зрения, были изменены синтаксис модулей и имена некоторых 
событий, чтобы сделать алгоритмы более структурированными. Теперь 
модуль может существовать сразу в нескольких экземплярах внутри алгоритма, 
и в связи с этим каждый экземпляр получает свой уникальный идентификатор. 
Мы считаем, что это упростило представление некоторых важнейших алгоритмов.
В первое издание был включен вспомогательный набор действующих примеров 
реализации алгоритмов на языке Java, использующих фреймворк Appia. Эти примеры 
доступны для загрузки на веб-сайте книги.

Благодарности 17

Ресурсы в Интернете

Дополнительная информация о книге, включая реализацию многих протоколов 
из первого издания, учебные презентации, слайды и список опечаток, доступна на 
веб-сайте книги: http://distributedprogramming.net.

Ссылки

Мы занимаемся исследованием абстракций распределенного программирования 
уже почти два десятилетия. Основой для этой книги послужили работы многих 
исследователей в области распределенных вычислений. Но особенно нам хотелось 
бы отметить Лесли Лэмпорта (Leslie Lamport) и Нэнси Линч (Nancy Lynch), 
сформулировавших интереснейшие проблемы в распределенных вычислениях, 
и ученых из Корнельского университета, занимавшихся исследованиями надежности 
распределенных вычислений, включая Озалпа Бабайоглы (Özalp Babaolu), 
Кена Бирмана (Ken Birman), Кейта Марцзулло (Keith Marzullo), Роберта ван Ре-
неше (Robbert van Rennesse), Рика Шлихтинга (Rick Schlichting), Фреда Шнайдера (
Fred Schneider) и Сэма Туега (Sam Toueg).
Прямое или косвенное отношение к этой книге имеют также многие другие исследователи. 
Мы постарались никого не забыть и добавить ссылки на их работы 
повсюду в этой книге. Все главы заканчиваются примечаниями, где приводятся 
информация по теме и исторические ссылки. Цель этих примечаний состоит в том, 
чтобы подсказать, какие еще работы можно прочитать в дальнейшем, проследить 
историю представленных концепций, а также отдать должное всем, кто причастен 
к их созданию и разработке. В конце книги приводится список книг для будущего 
чтения, посвященных другим аспектам распределенных вычислений.

Благодарности

Мы хотели бы выразить глубокую благодарность нашим студентам и аспирантам 
Федеральной политехнической школы Лозанны (École Polytechnique Fédérale de 
Lausanne, EPFL) и Лиссабонского университета (University of Lisboa, UL) за рецензирование 
рукописей этой книги. На самом деле они не имели выбора и в любом 
случае должны были сдавать экзамены нам! Но они были весьма снисходительны 
к ошибкам и опечаткам, которых было немало в первых версиях книги и сопроводительных 
слайдах, и представили множество очень ценных замечаний.
Парта Дутта (Partha Dutta), Корин Хэри (Corine Hari), Михаль Капалка (Mi-
chal Kapalka), Петр Кузнецов (Petr Kouznetsov), Рон Леви (Ron Levy), Максим 
Монод (Maxime Monod), Бастиан Пошон (Bastian Pochon) и Джаспер Спринг 
(Jesper Spring), аспиранты школы информационных технологий и теории связи 
(School of Computer and Communication Sciences) университета EPFL, Филипе 
Араужо (Filipe Araujo) и Хъюго Миранда  (Hugo Miranda), аспиранты из группы 
«Распределенные алгоритмы и сетевые протоколы» (Distributed Algorithms and 
Network Protocol, DIALNP) кафедры информатики (Departamento de Informatica) 

Предисловие

факультета естественных наук Лиссабонского университета (Faculdade de Ciên-
cias da Universidade de Lisboa), Лейла Халил (Leila Khalil) и Роберт Басмаджан 
(Robert Basmadjian), аспиранты из Ливанского университета в Бейруте (Lebanese 
University), а также Али Годши (Ali Ghodsi), аспирант из Шведского института 
компьютерных наук (Swedish Institute of Computer Science, SICS) в Стокгольме 
предложили массу улучшений к алгоритмам, представленным в книге.
Несколько реализаций для «практической» части книги было разработано 
Александром Пинто (Alexandre Pinto) или с его помощью, ключевым членом проекта 
Appia, при участии некоторых преподавателей и студентов группы DIALNP, 
включая Нуно Крвальо (Nuno Carvalho), Марию Жоао Монтейро (Maria João 
Monteiro) и Луиса Сардинья (Lus Sardinha).
Наконец, мы хотели бы поблагодарить всех наших коллег, которые оказали нам 
любезность, передав свои комментарии к первым рукописям книги. В их числе: 
Феликс Гартнер (Felix Gaertner), Бенуит Гарбинато (Benoit Garbinato) и Мартен 
ван Стин (Maarten van Steen).

Благодарности ко второму изданию

Работа над вторым изданием книги началась в 2009 году, когда Кристиан Качин 
(Christian Cachin), работавший тогда в IBM Research (EPFL), находился в ежегодном 
отпуске. Мы благодарны EPFL и IBM Research за поддержку.
Мы снова хотим сказать спасибо студентам из EPFL и Лиссабонского университета, 
которым довелось работать с книгой, за предложенные улучшения к первому 
изданию. Мы также выражаем свою благодарность студентам из высшего 
технологического института (Instituto Superior Técnico, IST) Лиссабонского технического 
университета (Universidade Técnica de Lisboa), федерального технологического 
института в Цюрихе (ETH Zurich) и EPFL, на чей суд были представлены 
рукописи и дополнительные материалы, включенные во второе издание, за 
их ценные замечания.
Мы благодарны многим внимательным читателям первого издания и тем, кто 
прислал свои комментарии к рукописям второго издания, за подмеченные проблемы 
и предложения по улучшению. В частности, мы благодарны Зинаиде Бе-
ненсон (Zinaida Benenson), Элиссон Бессани (Alysson Bessani), Диего Бьюррун 
(Diego Biurrun), Филиппе Кристову (Filipe Cristóvão), Дэну Добре (Dan Dobre), 
Феликсу Фрейлингу (Felix Freiling), Али Годши (Ali Ghodsi), Сейфу Хариди (Seif 
Haridi), Матусу Харвану (Matus Harvan), Рудигеру Капице (Rüdiger Kapitza), Ни-
колу Кнежевичу (Nikola Kneevi), Андреасу Кнобелю (Andreas Knobel), Михаю 
Летиа (Mihai Letia), Томасу Локеру (Thomas Locher), Хейну Мелингу (Hein Me-
ling), Хьюго Миранде (Hugo Miranda), Луису Пина (Lus Pina), Мартину Шобу 
(Martin Schaub) и Марко Вуколичу (Marko Vukoli).
Кристиан Качин,
Рашид Гуерру,
Луис Родригес