Homework (Week 9) Term 2, 2020 Announcements Course Outline Course Schedule Glossary Maths Resources Moodle - BB Collab Piazza Forum Assignment 0 Spec TeX Guide Web Submission Assignment 1 Spec TeX Guide Web Submission Assignment 2 Spec Web Submission Java Resources Monitors Video Multithreading Video Semaphores Video Volatile Video Web Tutorials Week 1 Homework Monday Board Recording Slides Condensed Slides Thursday Code Slides Condensed Slides Week 2 Homework Thursday Slides Condensed Slides Week 3 Homework Monday Brownies Promela Samples Slides Condensed Slides Thursday Code Slides Condensed Slides Week 4 Homework Monday Slides Condensed Slides Thursday Slides Condensed Slides Week 5 Homework Monday Slides Condensed Slides Thursday Slides Condensed Slides Week 7 Homework Monday Slides Condensed Slides Thursday Slides Condensed Slides Week 8 Homework Monday Slides Thursday Slides Week 9 Homework Monday Slides Thursday Slides Week 10 Notes Homework (Week 9) Table of Contents 1. The Byzantine Generals Algorithm 2. The King Algorithm 3. The Dijkstra-Scholten Algorithm Submission: Due on Thursday, 6th August, 6pm Sydney Time. Please submit using the CSE Give System either online or via this command on a CSE terminal: give cs3151 hw8 hw8.pdf
1 The Byzantine Generals Algorithm In the Byzantine Generals Algorithm, suppose that there is exactly 1 (one) traitor and that Ivan’s data structures are: Who is the traitor? Justify your answer (explain why this general is the traitor and why none of the other generals can be the traitor). What does Ivan decide about Basil’s and John’s plans? What does Ivan decide about the overall majority plan? Using DAJ, construct a minimal scenario leading to the shown Ivan's data structure (in this minimal scenario the traitor's only incorrect messages are the ones in the shown Ivan's data structure). Provide a screenshot of the main window in DAJ. For the scenario constructed in the previous question, provide screenshots of the 4 (four) knowledge trees that DAJ constructs about each of the generals. Note that knowledge trees are called "message trees" in DAJ. Which of these knowledge (message) trees indicate the traitor's incorrect messages? 2 The King Algorithm Compare the Byzantine Generals Algorithm and the King Algorithm in terms of: the minimal number of all generals (both loyal and traitors) required to achieve fault-tolerance in the presence of \(t\) traitors, and the number of messages sent by \(n\) generals. It is sufficient that you provide formulas and big \(\mathcal{O}\) bounds without deriving or proving them. However, discuss what do your comparisons of these formulas imply about which algorithm is better. Based on these comparisons, discuss in which situations the Byzantine Generals Algorithm is more practical and in which situations the King Algorithm is more practical. 3 The Dijkstra-Scholten Algorithm A distributed system with 4 (four) nodes including 1 (one) environment node is depicted with the following directed graph: Using DAJ, construct a scenario for each of the 4 (four) different spanning trees in the above directed graph. These scenarios differ in the order of the sent messages (but note that some orders of sent messages result in the same spanning tree, while you have to find all different spanning trees). For each of these scenarios, only provide a screenshot of the spanning tree that DAJ constructs. 2020-08-06 Thu 03:32 Announcements RSS
