GupShup Study
 
  
Notes on Theory of Distributed Systems pdf download
Ravi Chopra

Notes on Theory of Distributed Systems pdf download

Ravi Chopra | 30-May-2016 |
Introduction , Coordinated attack , Broadcast and convergecast , Distributed breadth-first search , Leader election , Logical clocks , Synchronizers , Synchronous agreement , Byzantine agreement , Impossibility of asynchronous agreement , Paxos , Failure detectors , Quorum systems , Model , Distributed Shared Memory , Mutual exclusion , The wait-free hierarchy , Atomic snapshots , Lower bounds on perturbable objects , Restricted-use objects , Randomized consensus and test-and-set , Renaming , Motivation , Obstruction-freedom , BG simulation , Topological methods , Approximate agreement , V Self-stabilization , Population protocols and chemical reaction networks , Mobile robots , Beeping ,

Hi friends, here Ravi Chopra uploaded notes for Distributed Systems with title Notes on Theory of Distributed Systems pdf download. You can download this lecture notes, ebook by clicking on the below file name or icon.

1 Introduction 1
1.1 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I Message passing 7
2 Model 9
2.1 Basic message-passing model . . . . . . . . . . . . . . . . . . 9
2.1.1 Formal details . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Network structure . . . . . . . . . . . . . . . . . . . . 11
2.2 Asynchronous systems . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Example: client-server computing . . . . . . . . . . . . 12
2.3 Synchronous systems . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Drawing message-passing executions . . . . . . . . . . . . . . 13
2.5 Complexity measures . . . . . . . . . . . . . . . . . . . . . . . 14
i
CONTENTS ii
3 Coordinated attack 18
3.1 Formal description . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Impossibility proof . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Randomized coordinated attack . . . . . . . . . . . . . . . . . 20
3.3.1 An algorithm . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.2 Why it works . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.3 Almost-matching lower bound . . . . . . . . . . . . . . 23
4 Broadcast and convergecast 24
4.1 Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.1 Basic algorithm . . . . . . . . . . . . . . . . . . . . . . 24
4.1.2 Adding parent pointers . . . . . . . . . . . . . . . . . 26
4.1.3 Termination . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Convergecast . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Flooding and convergecast together . . . . . . . . . . . . . . . 29
5 Distributed breadth-first search 31
5.1 Using explicit distances . . . . . . . . . . . . . . . . . . . . . 31
5.2 Using layering . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3 Using local synchronization . . . . . . . . . . . . . . . . . . . 33
6 Leader election 37
6.1 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.2 Leader election in rings . . . . . . . . . . . . . . . . . . . . . 39
6.2.1 The Le-Lann-Chang-Roberts algorithm . . . . . . . . 39
6.2.1.1 Proof of correctness for synchronous executions 40
6.2.1.2 Performance . . . . . . . . . . . . . . . . . . 40
6.2.2 The Hirschberg-Sinclair algorithm . . . . . . . . . . . 41
6.2.3 Peterson’s algorithm for the unidirectional ring . . . . 42
6.2.4 A simple randomized O(n log n)-message algorithm . . 44
6.3 Leader election in general networks . . . . . . . . . . . . . . . 44
6.4 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.4.1 Lower bound on asynchronous message complexity . . 45
6.4.2 Lower bound for comparison-based algorithms . . . . 46
7 Logical clocks 49
7.1 Causal ordering . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7.2 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.2.1 Lamport clock . . . . . . . . . . . . . . . . . . . . . . 52
7.2.2 Neiger-Toueg-Welch clock . . . . . . . . . . . . . . . . 52
CONTENTS iii
7.2.3 Vector clocks . . . . . . . . . . . . . . . . . . . . . . . 53
7.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
7.3.1 Consistent snapshots . . . . . . . . . . . . . . . . . . . 54
7.3.1.1 Property testing . . . . . . . . . . . . . . . . 55
8 Synchronizers 57
8.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
8.2 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . 58
8.2.1 The alpha synchronizer . . . . . . . . . . . . . . . . . 59
8.2.2 The beta synchronizer . . . . . . . . . . . . . . . . . . 59
8.2.3 The gamma synchronizer . . . . . . . . . . . . . . . . 60
8.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
8.4 Limitations of synchronizers . . . . . . . . . . . . . . . . . . . 61
8.4.1 Impossibility with crash failures . . . . . . . . . . . . 61
8.4.2 Unavoidable slowdown with global synchronization . . 62
9 Synchronous agreement 64
9.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . 64
9.2 Solution using flooding . . . . . . . . . . . . . . . . . . . . . . 65
9.3 Lower bound on rounds . . . . . . . . . . . . . . . . . . . . . 66
9.4 Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
10 Byzantine agreement 69
10.1 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
10.1.1 Minimum number of rounds . . . . . . . . . . . . . . . 69
10.1.2 Minimum number of processes . . . . . . . . . . . . . 69
10.1.3 Minimum connectivity . . . . . . . . . . . . . . . . . . 71
10.1.4 Weak Byzantine agreement . . . . . . . . . . . . . . . 72
10.2 Upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
10.2.1 Exponential information gathering gets n = 3f + 1 . . 74
10.2.1.1 Proof of correctness . . . . . . . . . . . . . . 75
10.2.2 Phase king gets constant-size messages . . . . . . . . . 77
10.2.2.1 The algorithm . . . . . . . . . . . . . . . . . 77
10.2.2.2 Proof of correctness . . . . . . . . . . . . . . 77
10.2.2.3 Performance of phase king . . . . . . . . . . 79
11 Impossibility of asynchronous agreement 80
11.1 Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
11.2 Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
11.3 Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
CONTENTS iv
11.4 Bivalence and univalence . . . . . . . . . . . . . . . . . . . . . 82
11.5 Existence of an initial bivalent configuration . . . . . . . . . . 82
11.6 Staying in a bivalent configuration . . . . . . . . . . . . . . . 83
11.7 Generalization to other models . . . . . . . . . . . . . . . . . 84
12 Paxos 85
12.1 The Paxos algorithm . . . . . . . . . . . . . . . . . . . . . . . 85
12.2 Informal analysis: how information flows between rounds . . 87
12.2.1 Example execution . . . . . . . . . . . . . . . . . . . . 88
12.2.2 Safety properties . . . . . . . . . . . . . . . . . . . . . 88
12.2.3 Learning the results . . . . . . . . . . . . . . . . . . . 90
12.2.4 Liveness properties . . . . . . . . . . . . . . . . . . . . 91
12.3 Replicated state machines and multi-Paxos . . . . . . . . . . 91
13 Failure detectors 93
13.1 How to build a failure detector . . . . . . . . . . . . . . . . . 94
13.2 Classification of failure detectors . . . . . . . . . . . . . . . . 94
13.2.1 Degrees of completeness . . . . . . . . . . . . . . . . . 94
13.2.2 Degrees of accuracy . . . . . . . . . . . . . . . . . . . 94
13.2.3 Boosting completeness . . . . . . . . . . . . . . . . . . 95
13.2.4 Failure detector classes . . . . . . . . . . . . . . . . . . 96
13.3 Consensus with S . . . . . . . . . . . . . . . . . . . . . . . . . 97
13.3.1 Proof of correctness . . . . . . . . . . . . . . . . . . . 98
13.4 Consensus with S and f < n/2 . . . . . . . . . . . . . . . . 99
13.4.1 Proof of correctness . . . . . . . . . . . . . . . . . . . 101
13.5 f < n/2 is still required even with P . . . . . . . . . . . . . 102
13.6 Relationships among the classes . . . . . . . . . . . . . . . . . 103
14 Quorum systems 105
14.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
14.2 Simple quorum systems . . . . . . . . . . . . . . . . . . . . . 105
14.3 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
14.4 Paths system . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
14.5 Byzantine quorum systems . . . . . . . . . . . . . . . . . . . 108
14.6 Probabilistic quorum systems . . . . . . . . . . . . . . . . . . 109
14.6.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 110
14.6.2 Performance . . . . . . . . . . . . . . . . . . . . . . . 110
14.7 Signed quorum systems . . . . . . . . . . . . . . . . . . . . . 111
CONTENTS v
II Shared memory 112
15 Model 114
15.1 Atomic registers . . . . . . . . . . . . . . . . . . . . . . . . . 114
15.2 Single-writer versus multi-writer registers . . . . . . . . . . . 115
15.3 Fairness and crashes . . . . . . . . . . . . . . . . . . . . . . . 116
15.4 Concurrent executions . . . . . . . . . . . . . . . . . . . . . . 116
15.5 Consistency properties . . . . . . . . . . . . . . . . . . . . . . 117
15.6 Complexity measures . . . . . . . . . . . . . . . . . . . . . . . 118
15.7 Fancier registers . . . . . . . . . . . . . . . . . . . . . . . . . 119
16 Distributed shared memory 121
16.1 Message passing from shared memory . . . . . . . . . . . . . 122
16.2 The Attiya-Bar-Noy-Dolev algorithm . . . . . . . . . . . . . . 122
16.3 Proof of linearizability . . . . . . . . . . . . . . . . . . . . . . 124
16.4 Proof that f < n/2 is necessary . . . . . . . . . . . . . . . . . 125
16.5 Multiple writers . . . . . . . . . . . . . . . . . . . . . . . . . . 125
16.6 Other operations . . . . . . . . . . . . . . . . . . . . . . . . . 126
17 Mutual exclusion 127
17.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
17.2 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
17.3 Mutual exclusion using strong primitives . . . . . . . . . . . . 128
17.3.1 Test and set . . . . . . . . . . . . . . . . . . . . . . . . 129
17.3.2 A lockout-free algorithm using an atomic queue . . . . 130
17.3.2.1 Reducing space complexity . . . . . . . . . . 131
17.4 Mutual exclusion using only atomic registers . . . . . . . . . 131
17.4.1 Peterson’s tournament algorithm . . . . . . . . . . . . 131
17.4.1.1 Correctness of Peterson’s protocol . . . . . . 133
17.4.1.2 Generalization to n processes . . . . . . . . . 135
17.4.2 Fast mutual exclusion . . . . . . . . . . . . . . . . . . 136
17.4.3 Lamport’s Bakery algorithm . . . . . . . . . . . . . . 138
17.4.4 Lower bound on the number of registers . . . . . . . . 140
17.5 RMR complexity . . . . . . . . . . . . . . . . . . . . . . . . . 142
17.5.1 Cache-coherence vs. distributed shared memory . . . . 142
17.5.2 RMR complexity of Peterson’s algorithm . . . . . . . 143
17.5.3 Mutual exclusion in the DSM model . . . . . . . . . . 144
17.5.4 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . 146
CONTENTS vi
18 The wait-free hierarchy 147
18.1 Classification by consensus number . . . . . . . . . . . . . . . 148
18.1.1 Level 1: registers etc. . . . . . . . . . . . . . . . . . . 149
18.1.2 Level 2: interfering RMW objects etc. . . . . . . . . . 151
18.1.3 Level 1: objects where the first write wins . . . . . . 152
18.1.4 Level 2m − 2: simultaneous m-register write . . . . . . 154
18.1.4.1 Matching impossibility result . . . . . . . . . 155
18.1.5 Level m: m-process consensus objects . . . . . . . . . 156
18.2 Universality of consensus . . . . . . . . . . . . . . . . . . . . . 157
19 Atomic snapshots 160
19.1 The basic trick: two identical collects equals a snapshot . . . 160
19.2 The Gang of Six algorithm . . . . . . . . . . . . . . . . . . . 161
19.2.1 Linearizability . . . . . . . . . . . . . . . . . . . . . . 162
19.2.2 Using bounded registers . . . . . . . . . . . . . . . . . 163
19.3 Faster snapshots using lattice agreement . . . . . . . . . . . . 166
19.3.1 Lattice agreement . . . . . . . . . . . . . . . . . . . . 166
19.3.2 Connection to vector clocks . . . . . . . . . . . . . . . 167
19.3.3 The full reduction . . . . . . . . . . . . . . . . . . . . 168
19.3.4 Why this works . . . . . . . . . . . . . . . . . . . . . . 169
19.3.5 Implementing lattice agreement . . . . . . . . . . . . . 170
19.4 Practical snapshots using LL/SC . . . . . . . . . . . . . . . . 173
19.4.1 Details of the single-scanner snapshot . . . . . . . . . 174
19.4.2 Extension to multiple scanners . . . . . . . . . . . . . 177
19.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
19.5.1 Multi-writer registers from single-writer registers . . . 177
19.5.2 Counters and accumulators . . . . . . . . . . . . . . . 178
19.5.3 Resilient snapshot objects . . . . . . . . . . . . . . . . 178
20 Lower bounds on perturbable objects 180
21 Restricted-use objects 184
21.1 Implementing bounded max registers . . . . . . . . . . . . . . 184
21.2 Encoding the set of values . . . . . . . . . . . . . . . . . . . . 186
21.3 Unbounded max registers . . . . . . . . . . . . . . . . . . . . 187
21.4 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
21.5 Max-register snapshots . . . . . . . . . . . . . . . . . . . . . . 189
21.5.1 Linearizability . . . . . . . . . . . . . . . . . . . . . . 191
21.5.2 Application to standard snapshots . . . . . . . . . . . 192
CONTENTS vii
22 Common2 195
22.1 Test-and-set and swap for two processes . . . . . . . . . . . . 196
22.2 Building n-process TAS from 2-process TAS . . . . . . . . . . 197
22.3 Obstruction-free swap from test-and-set . . . . . . . . . . . . 198
22.4 Wait-free swap from test-and-set . . . . . . . . . . . . . . . . 200
22.5 Single-use swap objects . . . . . . . . . . . . . . . . . . . . . 202
23 Randomized consensus and test-and-set 205
23.1 Role of the adversary in randomized algorithms . . . . . . . . 205
23.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
23.3 Reduction to simpler primitives . . . . . . . . . . . . . . . . . 208
23.3.1 Adopt-commit objects . . . . . . . . . . . . . . . . . . 208
23.3.2 Conciliators . . . . . . . . . . . . . . . . . . . . . . . . 209
23.4 Implementing an adopt-commit object . . . . . . . . . . . . . 209
23.5 Conciliators and shared coins . . . . . . . . . . . . . . . . . . 210
23.6 A one-register conciliator for an oblivious adversary . . . . . 212
23.7 Sifters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
23.7.1 Test-and-set using sifters . . . . . . . . . . . . . . . . 215
23.7.2 Consensus using sifters . . . . . . . . . . . . . . . . . . 216
23.7.3 A better sifter for test-and-set . . . . . . . . . . . . . 218
23.8 Space bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
24 Renaming 221
24.1 Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
24.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
24.3 Order-preserving renaming . . . . . . . . . . . . . . . . . . . 223
24.4 Deterministic renaming . . . . . . . . . . . . . . . . . . . . . 223
24.4.1 Wait-free renaming with 2n − 1 names . . . . . . . . . 224
24.4.2 Long-lived renaming . . . . . . . . . . . . . . . . . . . 225
24.4.3 Renaming without snapshots . . . . . . . . . . . . . . 226
24.4.3.1 Splitters . . . . . . . . . . . . . . . . . . . . . 226
24.4.3.2 Splitters in a grid . . . . . . . . . . . . . . . 227
24.4.4 Getting to 2n − 1 names in polynomial space . . . . . 229
24.4.5 Renaming with test-and-set . . . . . . . . . . . . . . . 230
24.5 Randomized renaming . . . . . . . . . . . . . . . . . . . . . . 230
24.5.1 Randomized splitters . . . . . . . . . . . . . . . . . . . 231
24.5.2 Randomized test-and-set plus sampling . . . . . . . . 231
24.5.3 Renaming with sorting networks . . . . . . . . . . . . 232
24.5.3.1 Sorting networks . . . . . . . . . . . . . . . . 232
24.5.3.2 Renaming networks . . . . . . . . . . . . . . 233
CONTENTS viii
24.5.4 Randomized loose renaming . . . . . . . . . . . . . . . 235
25 Software transactional memory 237
25.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
25.2 Basic approaches . . . . . . . . . . . . . . . . . . . . . . . . . 238
25.3 Implementing multi-word RMW . . . . . . . . . . . . . . . . 239
25.3.1 Overlapping LL/SC . . . . . . . . . . . . . . . . . . . 240
25.3.2 Representing a transaction . . . . . . . . . . . . . . . 240
25.3.3 Executing a transaction . . . . . . . . . . . . . . . . . 241
25.3.4 Proof of linearizability . . . . . . . . . . . . . . . . . . 241
25.3.5 Proof of non-blockingness . . . . . . . . . . . . . . . . 242
25.4 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
25.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
26 Obstruction-freedom 244
26.1 Why build obstruction-free algorithms? . . . . . . . . . . . . 245
26.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
26.2.1 Lock-free implementations . . . . . . . . . . . . . . . . 245
26.2.2 Double-collect snapshots . . . . . . . . . . . . . . . . . 245
26.2.3 Software transactional memory . . . . . . . . . . . . . 246
26.2.4 Obstruction-free test-and-set . . . . . . . . . . . . . . 246
26.2.5 An obstruction-free deque . . . . . . . . . . . . . . . . 248
26.3 Boosting obstruction-freedom to wait-freedom . . . . . . . . . 250
26.3.1 Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
26.4 Lower bounds for lock-free protocols . . . . . . . . . . . . . . 255
26.4.1 Contention . . . . . . . . . . . . . . . . . . . . . . . . 255
26.4.2 The class G . . . . . . . . . . . . . . . . . . . . . . . . 256
26.4.3 The lower bound proof . . . . . . . . . . . . . . . . . . 258
26.4.4 Consequences . . . . . . . . . . . . . . . . . . . . . . . 262
26.4.5 More lower bounds . . . . . . . . . . . . . . . . . . . . 262
26.5 Practical considerations . . . . . . . . . . . . . . . . . . . . . 263
27 BG simulation 264
27.1 Safe agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 264
27.2 The basic simulation algorithm . . . . . . . . . . . . . . . . . 266
27.3 Effect of failures . . . . . . . . . . . . . . . . . . . . . . . . . 267
27.4 Inputs and outputs . . . . . . . . . . . . . . . . . . . . . . . . 267
27.5 Correctness of the simulation . . . . . . . . . . . . . . . . . . 268
27.6 BG simulation and consensus . . . . . . . . . . . . . . . . . . 269
CONTENTS ix
28 Topological methods 270
28.1 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
28.2 k-set agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 271
28.3 Representing distributed computations using topology . . . . 272
28.3.1 Simplicial complexes and process states . . . . . . . . 273
28.3.2 Subdivisions . . . . . . . . . . . . . . . . . . . . . . . 276
28.4 Impossibility of k-set agreement . . . . . . . . . . . . . . . . . 280
28.5 Simplicial maps and specifications . . . . . . . . . . . . . . . 282
28.5.1 Mapping inputs to outputs . . . . . . . . . . . . . . . 283
28.6 The asynchronous computability theorem . . . . . . . . . . . 283
28.6.1 The participating set protocol . . . . . . . . . . . . . . 285
28.7 Proving impossibility results . . . . . . . . . . . . . . . . . . . 286
28.7.1 k-connectivity . . . . . . . . . . . . . . . . . . . . . . . 287
28.7.2 Impossibility proofs for specific problems . . . . . . . 288
29 Approximate agreement 290
29.1 Algorithms for approximate agreement . . . . . . . . . . . . . 290
29.2 Lower bound on step complexity . . . . . . . . . . . . . . . . 293
III Other communication models 295
30 Self-stabilization 297
30.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
30.2 Token ring circulation . . . . . . . . . . . . . . . . . . . . . . 298
30.2.1 Token ring circulation with m > n states . . . . . . . 299
30.3 Synchronizers . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
30.4 Spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . 301
30.5 Self-stabilization and local algorithms . . . . . . . . . . . . . 302
31 Population protocols and chemical reaction networks 304
31.1 Definition of a population protocol . . . . . . . . . . . . . . . 305
31.2 Stably computable predicates . . . . . . . . . . . . . . . . . . 306
31.2.1 Time complexity . . . . . . . . . . . . . . . . . . . . . 306
31.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 307
31.2.2.1 Leader election . . . . . . . . . . . . . . . . . 307
31.2.2.2 Distributing the output . . . . . . . . . . . . 308
31.2.2.3 Remainder mod m . . . . . . . . . . . . . . . 308
31.2.2.4 Linear threshold functions . . . . . . . . . . 308
31.2.3 Presburger arithmetic and semilinear sets . . . . . . . 309
CONTENTS x
31.2.3.1 Semilinear predicates are stably computable 310
31.2.3.2 Stably computable predicates are semilinear 311
31.3 Random interactions . . . . . . . . . . . . . . . . . . . . . . . 311
32 Mobile robots 314
32.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
32.2 Two robots, no faults . . . . . . . . . . . . . . . . . . . . . . . 316
32.3 Three robots . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
32.4 Many robots, with crash failures . . . . . . . . . . . . . . . . 319
33 Beeping 321
33.1 Interval coloring . . . . . . . . . . . . . . . . . . . . . . . . . 322
33.1.1 Estimating the degree . . . . . . . . . . . . . . . . . . 323
33.1.2 Picking slots . . . . . . . . . . . . . . . . . . . . . . . 323
33.1.3 Detecting collisions . . . . . . . . . . . . . . . . . . . . 323
33.2 Maximal independent set . . . . . . . . . . . . . . . . . . . . 324
33.2.1 Lower bound . . . . . . . . . . . . . . . . . . . . . . . 324
33.2.2 Upper bound with known bound on n . . . . . . . . . 326
33.3 Stone age distributed computing . . . . . . . . . . . . . . . . 326
33.3.1 Synchronizers . . . . . . . . . . . . . . . . . . . . . . . 327
33.3.2 Multi-letter queries . . . . . . . . . . . . . . . . . . . . 327

    Attachment Lists

    If download doesn't start in application like IDM then press Alt + click on download button to start download
  • DS.pdf (Size: 2347.58KB) Dowland
Share With Friends :  

No any Comment yet!