Department of Electrical Engineering and Computer Science MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6 824 Distributed System Engineering Spring 2009 Quiz II Solutions All problems are open ended questions In order to receive credit you must answer the question as precisely as possible The quiz is designed to take 80 minutes but you have two hours to complete it If you finish early we included some light additional reading Write your name on this cover sheet AND at the bottom of each page of this booklet Some questions may be much harder than others Read them all through first and attack them in the order that allows you to make the most progress If you find a question ambiguous be sure to write down any assumptions you make Be neat If we can t understand your answer we can t give you credit THIS IS AN OPEN BOOK OPEN NOTES QUIZ I xx 40 Name II xx 16 III xx 25 IV xx 12 V xx 7 Total xx 100 max 99 median 81 77 3 11 3 00 5 1 96 9 0 9 91 86 5 0 8 81 8 5 7 76 71 0 5 7 66 6 0 5 6 61 56 5 51 0 5 5 46 4 41 0 5 4 36 3 0 3 31 26 5 0 2 21 2 5 1 16 11 10 6 5 1 Grade histogram for Quiz 2 10 9 8 7 6 5 4 3 2 1 0 6 824 SPRING 2009 Quiz 2 Solutions Page 3 of 10 I Short Questions 1 8 points The Storm authors tired of pesky researchers infiltrating their botnet want to prevent it from being subverted in the future They propose two defenses to address the attacks used by the Spamalytics authors and hire you to evaluate their designs For the purposes of this problem assume that you have no scruples Assume that the Storm authors have a secure way to distribute keys to proxies and workers Which of the following changes would address the attack described in the Spamalytics paper Circle all that apply For each proposal that won t work explain why not If they both work identify the one you think is better for the Storm authors and give a specific argument why it is superior a Each master adds a MAC to messages for each proxy using a key it shares with that proxy Each proxy adds a MAC to messages for each worker using a key it shares with that worker Proxies and workers verify the MACs on messages they receive b The masters use their private keys to sign the tasks intended for each worker Workers verify the signatures on messages they receive Both changes address the attack described in the paper wherein the researchers run the unmodified proxy and only intercept and rewrite network traffic So which one is better You could have argued that MACs are better because they solve the problem and are much cheaper than signatures which reduces the load on the master Alternatively you could have argued that signatures are better because they would prevent more sophisticated attacks where the proxies themselves are modified 2 8 points After seeing the 6 824 Lab 9 demos Ben Bitdiddle decides to implement his extent service on top of Chord for better scalability He implements Chord as described in the paper He uses the extent numbers as keys and stores each extent at the Chord node that is responsible for the extent s key He notices that when a new node is joining gets sometimes fail and report that extents are missing Give a specific example to illustrate the problem and describe a simple way to fix it Assume that there are no failures network partitions or multiple concurrent joins This can happen when a new node joins the ring but has not yet transferred the extents from its successor Several fixes are possible but the simplest is probably the one suggested by the paper where clients retry periodically if Chord can t find the requested extent Name Page 4 of 10 6 824 Spring 2009 Quiz 2 Solutions 3 8 points Suppose we took a system that uses SUNDR and made it extra secure by replicating the SUNDR server with BFT In what ways does this provide stronger security than just using SUNDR alone One answer is that if between 1 and f replicas are compromised BFT SUNDR provides sequential consistency instead of fork consistency Another possible answer is that BFT SUNDR provides availability when between 1 and f replicas are compromised whereas with SUNDR alone a single compromised server can prevent clients from making progress 4 8 points Consider the application described in Example 1 in the PNUTS paper Describe how you would write this application with the PNUTS primitives read any read critical read latest write and test and set write You only need to discuss the two operations in the example publishing photos and updating the access control list Explain why your implementation would avoid the problem discussed in the example One possible solution acl photos read any latest version write acl mom while test and set write latest version photos new photo latest version photos read latest photos This ensures that the ACL update is applied before the photo is published Since PNUTS only guarantees per row consistency the photo list and the ACL must also be in the same row 5 8 points Ben is designing a new web browser Chromium and considering which features to include to achieve world domination After reading the Coral paper he wonders if he could add something to the browser to simplify the design of the Coral CDN and reduce latency for users Describe the additional functionality the web browser should have to achieve Ben s goals and explain how it achieves them A good strategy is for the browser to do the measurement and proxy selection itself rather than relying on a layer of indirection the resolver to do it This simplifies the resolver and results in more accurate measurement the system no longer needs the assumption that proxies that are close to the resolver are close to the client It also means that dnssrv does not need to verify that HTTP proxies are live before returning them See the last paragraph of Section 3 1 6 824 SPRING 2009 Quiz 2 Solutions Page 5 of 10 II Paxos Recall the following snippets from the Paxos pseudocode in lab 7 if node receives prepare instance n if instance instance h return oldinstance instance values instance if node gets accept instance n v if instance instance h return oldinstance instance values instance 6 8 points Many students noticed that the return type of acceptreq was an integer and couldn t encode an oldinstance response It was claimed on the mailing lists that it was okay to simply reject the accept message in the above scenario instead of modifying the return type of acceptreq to return an oldinstance response Explain why this modification is correct If a quorum of nodes are in a later