Wattenhofer R. Principles of Distributed Computing

Zurich: ETH, 2016. — 321 p.What is Distributed Computing?Course OverviewProblem & Model
Coloring TreesBroadcast
Convergecast
BFS Tree Construction
MST ConstructionAnonymous Leader Election
Anonymous Ring
Lower Bounds
Synchronous RingArray & Mesh
Sorting Networks
Counting NetworksModel
Mutual Exclusion
Problem Definition
Splitters
Binary Splitter Tree
Splitter MatrixCentralized Solutions
Arrow and Friends
Ivy and FriendsMIS
Original Fast MIS
Fast MIS v
ApplicationsModel
Locality
The Neighborhood GraphSocial Networks
Small World Networks
Propogation StudiesBasics
The Local Synchronizer Alpha
The Global Synchronizer Beta
The Hybrid Synchronizer Gamma
Network Partition
Clock SynchronizationDiameter & APSP
Lower Bound Graphs
Communication Complexity
Distributed Complexity TheoryBasics
Uniform Initialization with CD
With High Probability
Uniform Leader Election
Even Faster Leader Election with CD
Uniform Asynchronous Wakeup without CD
Useful FormulasSelf-Stabilization
Advanced StabilizationAdjacency
Rooted Trees
Road NetworksClient/Server
PaxosConsensus
Impossibility of Consensus
Randomized Consensus
Shared CoinByzantine Agreement
Validity
How Many Byzantine Nodes?
The King Algorithms
Lower Bound on Number of Rounds
Asynchronous Byzantine AgreementAgreement with Authentication
ZyzzyvaQuorum Systems
Load and Work
Grid Quorum Systems
Fault Tolerance
Byzantine Quorum SystemsConsistency, Availability and Partitions
Bitcoin
Smart Contracts
Weak ConsistencyConsistent Hashing
Hypercubic Networks
DHT & ChurnPrisoner's Dilemma
Selfish Caching
Braess' Paradox
Rock-Paper-Scissors
Mechanism DesignSynchronous Edge-Dynamic Networks
Problem Definitions
Basic Information Dissemination
k-Verification
k-Committee Election
More Stable GraphsAll-to-All CommunicationThe Current State of Concurrent Programming
Transaction Memory
Contention ManagementDominating Set
Sequential Greedy Algorithm
Distributed Greedy AlgorithmArray
Mesh
Routing in the Mesh with Small Queues
Hot-Potato RoutingButterfly
Oblivious Routing
Offline Routing