распределённые вычисления

[Olej]

Principles of Distributed Computing (lecture collection) (англ.)
ETH Zurich – ITET – TIK – Distributed Computing Group – Lectures – Podc_allstars

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

Обратите внимание, что порядок лекций является более или менее произвольным. Каждая глава - это, в основном, независимое изложение, с редкими ссылками на другие главы.

(перевод мой ... по-быстренькому )

Всё это очень похоже на продолжение обсуждения уже существующей темы параллельность + синхронизации (примеры) ... но то уже старая тема, а здесь новый материал, поэтому продолжим здесь.

[Olej]

Principles of Distributed Computing (lecture collection) (англ.)
ETH Zurich – ITET – TIK – Distributed Computing Group – Lectures – Podc_allstars

Здесь можете скачать всё отдельной книгой (PDF): Principles of Distributed Computing.

Обратите внимание, что порядок лекций является более или менее произвольным. Каждая глава - это, в основном, независимое изложение, с редкими ссылками на другие главы.

Настолько обширное изложение, что для обзора выложу сюда оглавление:

Contents
1 Vertex Coloring 5
1.1 Problem & Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Coloring Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Tree Algorithms 15
2.1 Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Convergecast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 BFS Tree Construction . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 MST Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Leader Election 23
3.1 Anonymous Leader Election . . . . . . . . . . . . . . . . . . . . . 23
3.2 Asynchronous Ring . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Synchronous Ring . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 Distributed Sorting 33
4.1 Array & Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Sorting Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Counting Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Shared Memory 47
5.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Mutual Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Store & Collect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.2 Splitters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.3.3 Binary Splitter Tree . . . . . . . . . . . . . . . . . . . . . . 53
5.3.4 Splitter Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 55
6 Shared Objects 59
6.1 Centralized Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Arrow and Friends . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.3 Ivy and Friends . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7 Maximal Independent Set 71
7.1 MIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.2 Original Fast MIS . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.3 Fast MIS v2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8 Locality Lower Bounds 85
8.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.2 Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.3 The Neighborhood Graph . . . . . . . . . . . . . . . . . . . . . . 89
9 Social Networks 95
9.1 Small World Networks . . . . . . . . . . . . . . . . . . . . . . . . 96
9.2 Propagation Studies . . . . . . . . . . . . . . . . . . . . . . . . . 102
10 Synchronization 107
10.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.2 Synchronizer α . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
10.3 Synchronizer β . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.4 Synchronizer γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
10.5 Network Partition . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.6 Clock Synchronization . . . . . . . . . . . . . . . . . . . . . . . . 114
11 Hard Problems 121
11.1 Diameter & APSP . . . . . . . . . . . . . . . . . . . . . . . . . . 121
11.2 Lower Bound Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 123
11.3 Communication Complexity . . . . . . . . . . . . . . . . . . . . . . 126
11.4 Distributed Complexity Theory . . . . . . . . . . . . . . . . . . . . 131
12 Wireless Protocols 135
12.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
12.2 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
12.2.1 Non-Uniform Initialization . . . . . . . . . . . . . . . . . 137
12.2.2 Uniform Initialization with CD . . . . . . . . . . . . . . . 137
12.2.3 Uniform Initialization without CD . . . . . . . . . . . . . 139
12.3 Leader Election . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.3.1 With High Probability . . . . . . . . . . . . . . . . . . . . 139
12.3.2 Uniform Leader Election . . . . . . . . . . . . . . . . . . . 140
12.3.3 Fast Leader Election with CD . . . . . . . . . . . . . . . . 141
12.3.4 Even Faster Leader Election with CD . . . . . . . . . . . . 141
12.3.5 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . 144
12.3.6 Uniform Asynchronous Wakeup without CD . . . . . . . . . . 144
12.4 Useful Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
13 Stabilization 149
13.1 Self-Stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
13.2 Advanced Stabilization . . . . . . . . . . . . . . . . . . . . . . . . 154
14 Labeling Schemes 159
14.1 Adjacency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
14.2 Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
14.3 Road Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
15 Peer-to-Peer Computing 167
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
15.2 Architecture Variants . . . . . . . . . . . . . . . . . . . . . . . . . 168
15.3 Hypercubic Networks . . . . . . . . . . . . . . . . . . . . . . . . . 169
15.4 DHT & Churn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
15.5 Storage and Multicast . . . . . . . . . . . . . . . . . . . . . . . . 178
16 Dynamic Networks 185
16.1 Synchronous Edge-Dynamic Networks . . . . . . . . . . . . . . . 185
16.2 Problem Definitions . . . . . . . . . . . . . . . . . . . . . . . . 186
16.3 Basic Information Dissemination . . . . . . . . . . . . . . . . . . 187
16.4 Small Messages . . . . . . . . . . . . . . . . . . . . . . . . . . 190
16.4.1 k-Verification . . . . . . . . . . . . . . . . . . . . . . . . 190
16.4.2 k-Committee Election . . . . . . . . . . . . . . . . . . . . 191
16.5 More Stable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 193
17 All-to-All Communication 197
18 Consensus 205
18.1 Impossibility of Consensus . . . . . . . . . . . . . . . . . . . . . . 205
18.2 Randomized Consensus . . . . . . . . . . . . . . . . . . . . . . 210
19 Multi-Core Computing 215
19.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
19.1.1 The Current State of Concurrent Programming . . . . . . 215
19.2 Transactional Memory . . . . . . . . . . . . . . . . . . . . . . . . 217
19.3 Contention Management . . . . . . . . . . . . . . . . . . . . . . . 218
20 Dominating Set 227
20.1 Sequential Greedy Algorithm . . . . . . . . . . . . . . . . . . . . 228
20.2 Distributed Greedy Algorithm . . . . . . . . . . . . . . . . . . . . 229
21 Routing 237
21.1 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
21.2 Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
21.3 Routing in the Mesh with Small Queues . . . . . . . . . . . . . . . . . 239
21.4 Hot-Potato Routing . . . . . . . . . . . . . . . . . . . . . . . . . . .240
21.5 More Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
22 Routing Strikes Back 245
22.1 Butterfly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
22.2 Oblivious Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
22.3 Offine Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

Какой шикарный материал!