Distributed algorithm: Tutorials
See also:
State Machine Replication, Atomic Broadcast
Byzantine Agreement/Broadcast
Failure detection
CAP, ACID, BASE
Overview
分散システムの限界について知ろう (slide)
by Omura Shingo
本当は恐ろしい分散システムの話 (slide)
by kumagi
Fault injection test (e.g. Japsen test), etc.
分散システムについて語らせてくれ (slide)
by kumagi
Faults, FLP, two phase commit, Paxos, Raft, etc.
分散システムについて語るときに我々の語ること
Translated article by Alvaro Videla
Part 2: Fault-Tolerance Distributed Systems 2014
Lecture slide by Roger Wattenhofer
Blogs
Decentralized Thoughts
By Ittai Abraham
An introduction to distributed systems
Outline of the lecture by Japsen
The Paper Trail
Blog about distributed algorithm including Paxos, CAP etc.
CryptoRef
Notions of security assumptions
How Does Distributed Consensus Work?
Medium by Preethi Kasireddy
From FLP, DLS, pBFT to Nakamoto
Textbooks
Distributed Computing: Principles, Algorithms, and Systems
Ajay D. Kshemkalyani (University of Illinois at Chicago), Mukesh Singhal (University of Kentucky)
Lecture slides for this book
Chapter 14: Consensus and Agreement
Designing Data-Intensive Applications The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
Martin Kleppmann, O’Reilly Media (2017)
Notes on Theory of Distributed Systems CPSC 465/565: Spring 2019
Yale Uni, James Aspnes
Principles of Distributed Computing
Roger Wattenhofer (ETH)
Properties
Basics of Safety & Liveness Properties
Lecture Slides from Imperial College London
Defining liveness (1985)
Bowen Alpern (IBM) and Fred B. Schneider (Cornell)
Article (Japanese), Slide
Recognizing safety and liveness (1987)
Bowen Alpern (IBM) and Fred B. Schneider (Cornell)
$ L(m) = L(Safe (m)) \cap L(Live (m))
Network assumption
Consensus in the Presence of Partial Synchrony
CYNTHIA DWORK, NANCY LYNCH (MIT), LARRY STOCKMEYER (IBM)
Proposed a protocol called DLS
https://gyazo.com/02911fb9fef4c7b4c2b354a89ac835ef
HoneybadgerBFT CCS 2016 presentation
https://gyazo.com/d8c7d03d37364fa703053438ccf00632
Effciency of SemiSynchronous versus Asynchronous Network (1992)
Semi-synchronous
Synchronous, with a Chance of Partition Tolerance
Yue Guo, Rafael Pass, Elaine Shi (Thunder Research and Cornell)
Video @CRYPTO'19, Video @DIMACS 2019, Video @MIT Bitcoin Expo 2019
Another "weak synchrony"
Allows the message delay bound ∆, at any point in time, to be violated for a set of honest replicas
Best-possible partition tolerance: honest and online majority, tolarates 1/2 corruption
#Layer1 #Tutorials