Homework (Week 9) Term 2, 2021 Announcements Course Outline Course Schedule Ed Forum Glossary Maths Resources Moodle - Lecture Recordings 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 Thursday Slides Condensed Thursday Slides Wednesday Slides Condensed Wednesday Slides Week 2 Homework Thursday Code Thursday Notes Thursday Slides Condensed Thursday Slides Wednesday Code Week 3 Homework Promela Code Thursday Code Thursday Slides Condensed Thursday Slides Wednesday Slides Condensed Wednesday Slides Week 4 Homework Thursday Code Thursday Slides Condensed Thursday Slides Wednesday Code and Notes Wednesday Slides Condensed Wednesday Slides Week 5 Homework Thursday Slides Condensed Thursday Slides Wednesday Code and Notes Wednesday Slides Condensed Wednesday Slides Week 7 Homework Thursday Notes Thursday Slides Condensed Thursday Slides Wednesday Notes Wednesday Slides Condensed Wednesday Slides Week 8 Homework Thursday Slides Condensed Thursday Slides Wednesday Code Wednesday Slides Condensed Wednesday Slides Week 9 Homework Thursday Notes Thursday Slides Wednesday Notes Wednesday Slides Condensed Wednesday Slides Week 10 Old Exams Thursday Slides Wednesday Notes Wednesday Slides Old Exam Papers final05s2 final06s2 final07s2 final08s2 final09s2 final10s2 final11s2 final13s2 final14s2 final17s2 Homework (Week 9) Table of Contents 1. The Byzantine Generals Algorithm (6 marks) 2. The Dijkstra-Scholten Algorithm (4 marks) 3. Byzantine fault tolerance (3 marks) Submission: Due on Sunday, 8th 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
This assignment uses Ben-Ari's DAJ tool, a visual aid for studying distributed algorithms, It is available for download at https://github.com/motib/daj. Clone the repository, then run the tool by executing java -jar daj.jar
1 The Byzantine Generals Algorithm (6 marks) 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 data structure for Ivan. In this minimal scenario, the traitor's only incorrect messages should be 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 Dijkstra-Scholten Algorithm (4 marks) 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. 3 Byzantine fault tolerance (3 marks) The threat model we've considered for Byzantine fault tolerance assumes that traitors may lie about their own plan, and lie about the plans of others. Otherwise, they follow the protocol: they are honest about their own identity and send the expected messages. Suppose we allow traitors to lie about their identity, and send as many messages as they want. For example, in the Byzantine Generals algorithm, the traitor Zoë could send the following message pretending to be Leo.
send(Basil,Leo,R)
In the Byzantine Generals algorithm with four generals, can a single such traitor cause a split final decision? Explain why or why not. 2021-08-05 tor 15:45 Announcements RSS
