Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 638984)
Контекстум
Электро-2024

Введение в надежное и безопасное распределенное программирование (5000,00 руб.)

0   0
Первый авторКачин К.
АвторыРодригес Л. , Гуерру Р.
ИздательствоМ.: ДМК Пресс
Страниц513
ID835199
АннотацияВ современных вычислениях программы нередко объединяют несколько процессов. Основная проблема, возникающая при создании таких распределенных программ, состоит в том, чтобы заставить все процессы вместе работать над решением общей задачи, даже в случае отказов некоторых из них. Данная книга содержит введение в абстракции распределенного программирования и знакомит с фундаментальными алгоритмами и их реализациями в нескольких распределенных окружениях. Перед читателем будут раскрыты важные проблемы распределенных вычислений и основные алгоритмические приемы их решения. На подробных примерах читатель сможет понять, как с помощью этих приемов конструировать распределенные приложения. Обсуждение каждой темы завершается множеством упражнений и их решений. Издание предназначено для студентов высших учебных заведений, аспирантов, а также программистов, занимающихся разработкой высоконадежных распределенных приложений.
ISBN978-5-89818-626-5
УДК004.42
ББК32.973
Качин, К. Введение в надежное и безопасное распределенное программирование / Л. Родригес, Р. . Гуерру; К. Качин .— Москва : ДМК Пресс, 2023 .— 513 с. — ISBN 978-5-89818-626-5 .— URL: https://rucont.ru/efd/835199 (дата обращения: 15.06.2024)

Предпросмотр (выдержки из произведения)

Введение_в_надежное_и_безопасное_распределенное_программирование.pdf
Стр.5
Стр.6
Стр.7
Стр.8
Стр.9
Стр.10
Стр.11
Стр.12
Стр.13
Введение_в_надежное_и_безопасное_распределенное_программирование.pdf
УДК 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
Стр.5
Содержание Предисловие ......................................................... 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
Стр.6
6  Содержание 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
Содержание  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
Стр.8
8  Содержание 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
Содержание  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
Стр.10
10  Содержание 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
Содержание  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
Стр.12
12  Содержание 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
Стр.13

Облако ключевых слов *


* - вычисляется автоматически
Периодика по подписке
Антиплагиат система Руконтекст