An Introduction to Distributed Algorithms

Valmir C. Barbosa9780262024129, 0-262-02412-8

An Introduction to Distributed Algorithms takes up some of the main concepts and algorithms, ranging from basic to advanced techniques and applications, that underlie the programming of distributed-memory systems such as computer networks, networks of workstations, and multiprocessors. Written from the broad perspective of distributed-memory systems in general it includes topics such as algorithms for maximum flow, program debugging, and simulation that do not appear in more orthodox texts on distributed algorithms.Moving from fundamentals to advances and applications, ten chapters – with exercises and bibliographic notes – cover a variety of topics. These include models of distributed computation, information propagation, leader election, distributed snapshots, network synchronization, self- stability, termination detection, deadlock detection, graph algorithms, mutual exclusion, program debugging, and simulation. All of the algorithms are presented in a clear, template- based format for the description of message-passing computations among the nodes of a connected graph. Such a generic setting allows the treatment of problems originating from many different application areas.The main ideas and algorithms are described in a way that balances intuition and formal rigor – most are preceded by a general intuitive discussion and followed by formal statements as to correctness complexity or other properties.

---

Table of contents :
An Introduction to Distributed Algorithms……Page 1
Dedication……Page 2
Table of Contents……Page 3
Preface……Page 4
Acknowledgments……Page 5
Part Overview……Page 7
1.1 Distributed-memory systems……Page 8
1.2 Communication processors……Page 11
1.3 Routing and flow control……Page 12
1.4 Reactive message-passing programs……Page 15
1.5 Handling infinite-capacity channels……Page 18
Theorem 1.1……Page 19
1.6 Processor allocation……Page 22
1.6.1 The static approach……Page 23
1.6.2 Task migration……Page 25
1.8 Exercises……Page 27
1.9 Bibliographic notes……Page 28
2.1 Full asynchronism and full synchronism……Page 31
Theorem 2.1…….Page 37
Lemma 2.2…….Page 38
Theorem 2.3…….Page 39
2.2 Computations on anonymous systems……Page 42
Theorem 2.4…….Page 43
Theorem 2.6…….Page 45
2.2.2 Boolean-function computations……Page 47
2.2.3 Another algorithm for local orientation……Page 51
2.3 The role of knowledge in distributed computations……Page 56
2.4 Exercises……Page 59
2.5 Bibliographic notes……Page 60
3.1 Events, orders, and global states……Page 61
3.2 The complexity of distributed computations……Page 69
3.2.1 Communication and time complexities……Page 70
3.2.2 Local and global measures……Page 72
3.3 Full asynchronism and full synchronism……Page 73
3.4 The role of synchronism in distributed computations……Page 77
Theorem 3.1…….Page 79
3.5 Exercises……Page 81
3.6 Bibliographic notes……Page 82
Overview……Page 83
4.1.1 Basic algorithms……Page 84
Theorem 4.1……Page 88
4.1.2 Handling multiple concurrent instances……Page 89
4.2 Graph connectivity……Page 90
4.3 Shortest distances……Page 93
Theorem 4.3……Page 95
4.4 Exercises……Page 98
4.5 Bibliographic notes……Page 99
Overview……Page 100
5.1 Leader election……Page 101
Corollary 5.2…….Page 105
Theorem 5.3…….Page 110
5.2.1 An algorithm……Page 111
Theorem 5.5…….Page 115
5.2.2 Some centralized alternatives……Page 116
5.3 Network synchronization……Page 117
5.3.1 General synchronizers……Page 118
5.3.2 Important special cases……Page 123
5.4 Exercises……Page 126
5.5 Bibliographic notes……Page 127
Part 2: Advances and Applications……Page 129
Overview……Page 130
6.1 Self-stabilization……Page 131
6.2 Termination detection……Page 135
6.2.1 General computations……Page 136
6.2.2 Diffusing computations……Page 141
Theorem 6.1…….Page 145
6.3.1 The computation……Page 147
6.3.2 An algorithm……Page 150
6.4 Exercises……Page 155
6.5 Bibliographic notes……Page 156
Overview……Page 157
7.1.1 The problem……Page 158
7.1.2 An algorithm……Page 159
Lemma 7.1…….Page 160
Theorem 7.2…….Page 171
7.2 Maximum flows in networks……Page 172
7.2.1 The problem……Page 173
7.2.2 Two synchronous algorithms……Page 175
7.4 Bibliographic notes……Page 186
8.1 Algorithms for mutual exclusion……Page 188
Theorem 8.1…….Page 191
Theorem 8.2…….Page 197
8.2 Sharing multiple resources……Page 199
8.3 The dining philosophers problem……Page 200
8.3.1 An algorithm……Page 201
Theorem 8.3…….Page 205
8.3.2 Operation under heavy loads……Page 206
Theorem 8.4…….Page 208
Corollary 8.5…….Page 209
Theorem 8.6…….Page 210
8.4 The drinking philosophers problem……Page 211
8.5 Exercises……Page 216
8.6 Bibliographic notes……Page 217
9.1 Preliminaries……Page 218
9.2 Techniques for program re-execution……Page 219
9.3.1 Fundamentals……Page 222
9.3.2 A trace-based technique……Page 225
9.3.3 A trace-independent approach……Page 230
Lemma 9.2…….Page 232
Theorem 9.3…….Page 234
Theorem 9.4…….Page 237
Theorem 9.5…….Page 243
Theorem 9.6…….Page 248
9.5 Bibliographic notes……Page 249
10.1 Physical and logical processes……Page 251
10.2 Time-stepped simulation……Page 255
10.3.1 A first algorithm……Page 260
10.3.2 Conditional events……Page 267
10.4 Optimistic event-driven simulation……Page 269
Corollary 10.3…….Page 274
10.5 Hybrid timing and defeasible time-stepping……Page 275
10.6 A general framework……Page 276
10.7 Exercises……Page 277
10.8 Bibliographic notes……Page 278
Bibliography……Page 280
Author Index……Page 305
P……Page 306
Z……Page 307
Subject Index……Page 308
D……Page 309
I……Page 310
N……Page 311
S……Page 312
T……Page 313
List of Figures……Page 314
List of Listings……Page 316