程序代写代做代考 html algorithm BenOr Rand After Exam

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