ii CONTENTS
7.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8 Locality Lower Bounds 83
8.1 Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.2 The Neighborhood Graph . . . . . . . . . . . . . . . . . . . . . . 86
9 Social Networks 91
9.1 Small World Networks . . . . . . . . . . . . . . . . . . . . . . . . 92
9.2 Propagation Studies . . . . . . . . . . . . . . . . . . . . . . . . . 98
10 Synchronization 101
10.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
10.2 Synchronizer α . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
10.3 Synchronizer β . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
10.4 Synchronizer γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
10.5 Network Partition . . . . . . . . . . . . . . . . . . . . . . . . . . 106
10.6 Clock Synchronization . . . . . . . . . . . . . . . . . . . . . . . . 108
11 Hard Problems 115
11.1 Diameter & APSP . . . . . . . . . . . . . . . . . . . . . . . . . . 115
11.2 Lower Bound Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 117
11.3 Communication Complexity . . . . . . . . . . . . . . . . . . . . . 120
11.4 Distributed Complexity Theory . . . . . . . . . . . . . . . . . . . 125
12 Stabilization 129
12.1 Self-Stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
12.2 Advanced Stabilization . . . . . . . . . . . . . . . . . . . . . . . . 134
13 Wireless Protocols 139
13.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
13.2 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
13.2.1 Non-Uniform Initialization . . . . . . . . . . . . . . . . . 141
13.2.2 Uniform Initialization with CD . . . . . . . . . . . . . . . 141
13.2.3 Uniform Initialization without CD . . . . . . . . . . . . . 142
13.3 Leader Election . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
13.3.1 With High Probability . . . . . . . . . . . . . . . . . . . . 143
13.3.2 Uniform Leader Election . . . . . . . . . . . . . . . . . . . 143
13.3.3 Fast Leader Election with CD . . . . . . . . . . . . . . . . 144
13.3.4 Even Faster Leader Election with CD . . . . . . . . . . . 145
13.3.5 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . 147
13.3.6 Uniform Asynchronous Wakeup without CD . . . . . . . . 148
13.4 Useful Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
14 Peer-to-Peer Computing 153
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
14.2 Architecture Variants . . . . . . . . . . . . . . . . . . . . . . . . 154
14.3 Hypercubic Networks . . . . . . . . . . . . . . . . . . . . . . . . . 155
14.4 DHT & Churn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
14.5 Storage and Multicast . . . . . . . . . . . . . . . . . . . . . . . . 163
