Syllabus
Introduction-Synchronous Network Model-Failures-Inputs and Outputs-Executions-Proof Methods-Complexity Measures-Randomization- Algorithms in General Synchronous networks-Leader Election in a General Network-Breadth First Search- Shortest Paths- Minimum Spanning Tree-Maximal Independent Set- Distributed Consensus with Link Failures-The Coordinated Attack Problem-Deterministic Version-Randomized Version- -Distributed Consensus with Process Failures-Algorithms for Stopping Failures-Algorithms for Byzantine Failures-Number of Processes for Byzantine Agreement-Byzantine Agreement in General Graphs-Weak Byzantine Agreement-Number of Rounds with Stopping Failures-Asynchronous System Model-I/O Automata-Operations on Automata-Fairness-Inputs and Outputs for Problems-Properties and Proof Methods-Complexity Measures-Indistinguishable Executions-Randomization-Asynchronous Shared Memory model-Shared Memory Systems-Environment Model-Indistinguishable States-Shared Variable Types-Complexity Measures-Failures-Randomization- Resource Allocation-Problem-Nonexistence of Symmetric Dining Philosophers Algorithms-Right-Left Dining Philosophers Algorithm-Randomization.Introduction to block chains.