Contents

1 Introduction

2 Model and Definitions
2.1 Distributed Decision
2.2 Probabilistic Distributed Decision
2.3 Distributed Verification
2.4 Distributed Decision Hierarchy

3 Distributed Decision in Networks
3.1 LOCAL model
3.2 CONGEST model
3.3 General Interpretation of Individual Outputs

4 Distributed Verification in Networks
4.1 LOCAL model
4.2 Message complexity
4.3 General Interpretation of Individual Outputs

5 Local Hierarchies in Networks
5.1 Unlimited-Size Certificates
5.2 Logarithmic-Size Certificates
5.3 Hierarchies in the congested clique
5.4 Distributed Graph Automata

6 Other Computational Models
6.1 Wait-Free Computing
6.2 Mobile Computing
6.3 Quantum Computing

7 Conclusion