BenOr Rand After Exam
Mopup
Radu Nicolescu Department of Computer Science University of Auckland
30 Oct 2020
1/12
BenOr Rand After Exam
1 BenOr
2 Randomisation
3 Life after 711
4 Exam
2/12
BenOr Rand After Exam
BenOr
• BenOr 1983: “Theorems” but NO proof: F < • Lynch 1996: Proof F < N/3
• Aguilera, Toueg 2012: Proof! F < N/2
• Randomisation!
√
N
4/12
BenOr Rand After Exam
Randomisation
• Very powerful technique
• But convergence in probability only!
• Extremely unlike odds may still eventuate!
• Cf. Aeschyllus – the father of tragedy (theatrical drama)
6/12
BenOr Rand After Exam
Aeschyllus – the father of tragedy
• Wiki: Aeschyllus was killed outside the city by a tortoise dropped by an eagle (possibly a lammergeier or Cinereous vulture, which do open tortoises for eating by dropping them on hard objects) which had mistaken his bald head for a rock suitable for shattering the shell.
7/12
BenOr Rand After Exam
Termination detection
• Piggybacks on top on any diffusing algorithm (single source)
• Works via a dynamic tree, potentially growing and shrinking
for each message
• Termination is detected by the initiator when the tree has disappeared
9/12
BenOr Rand After Exam
FLP vs CAP
• How to understand CAP Theorem? https://yourblog879.wordpress.com/2018/01/17/ how-to-understand-cap-theorem/
• Eric Brewer
CAP Twelve Years Later: How the ”Rules” Have Changed https://www.infoq.com/articles/ cap-twelve-years-later-how-the-rules-have-changed/
• Daniel Abadi
DBMS Musings (PACELC theorem) https://dbmsmusings.blogspot.com/2010/04/ problems-with-cap-and-yahoos-little.html
10/12
BenOr Rand After Exam
Exam
• 6 out of 7 questions – NO plussage, so mention which answers should be considered
• A few side topics only marginally touched in the lectures, but should be doable if we have really understood the main topic
• Questions asking short proofs are possible
12/12