Distributed algorithm: Tutorials
See also:
Overview
by Omura Shingo
by kumagi
Fault injection test (e.g. Japsen test), etc.
by kumagi
Faults, FLP, two phase commit, Paxos, Raft, etc.
Translated article by Alvaro Videla
Lecture slide by Roger Wattenhofer
Blogs
By Ittai Abraham
Outline of the lecture by Japsen
Blog about distributed algorithm including Paxos, CAP etc.
Medium by Preethi Kasireddy
From FLP, DLS, pBFT to Nakamoto
Textbooks
Ajay D. Kshemkalyani (University of Illinois at Chicago), Mukesh Singhal (University of Kentucky)
Martin Kleppmann, O’Reilly Media (2017)
Yale Uni, James Aspnes
Roger Wattenhofer (ETH)
Properties
Basics of Safety & Liveness Properties
Bowen Alpern (IBM) and Fred B. Schneider (Cornell)
Bowen Alpern (IBM) and Fred B. Schneider (Cornell)
$ L(m) = L(Safe (m)) \cap L(Live (m))
Network assumption
CYNTHIA DWORK, NANCY LYNCH (MIT), LARRY STOCKMEYER (IBM)
Proposed a protocol called DLS
https://gyazo.com/02911fb9fef4c7b4c2b354a89ac835ef
https://gyazo.com/d8c7d03d37364fa703053438ccf00632
Semi-synchronous
Yue Guo, Rafael Pass, Elaine Shi (Thunder Research and Cornell)
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