Department of Electrical Engineering and Computer Science MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6 824 Distributed System Engineering Spring 2011 Quiz II Solutions Grade histogram for Quiz II 8 7 6 5 4 3 2 1 min 60 max 100 median 85 average 83 11 00 1 96 5 9 91 0 9 86 5 8 81 0 8 76 5 7 71 0 7 66 5 6 61 0 6 56 51 5 5 0 6 824 Spring 2011 Quiz II Solutions I Page 2 of 9 Paxos 1 5 points Circle the earliest point at which Paxos has agreed on a value There s a copy of the Paxos algorithm below A A leader receives prepare ok messages from a majority B A majority send accept ok messages with the same n C A leader receives accept ok messages from a majority with the n the leader expects D A majority of nodes receive decided messages Answer B Once a majority has received and accepted a given value v then all future proposed values will also be v 2 5 points It is possible for two Paxos leaders for the same Paxos instance to both see prepare ok messages from a majority of nodes Describe a scenario in which this happens Answer Yes Suppose there are four nodes n1 4 n1 sends out prepare messages with n 10 and gets replies from all nodes Then n1 crashes After a while node n2 s hearbeat times out and decides to become a leader for the same Paxos instance and sends out prepare messages with n 11 n2 will likely receive responses from n2 n3 and n4 a majority of nodes state must persist across reboots n p highest prepare seen n a v a highest accept seen proposer v choose n unique and higher than any n seen so far send prepare n to all servers including self if prepare ok n a v a from majority v v a with highest n a choose own v otherwise send accept n v to all if accept ok n from majority send decided v to all acceptor s prepare n handler if n n p n p n reply prepare ok n a v a acceptor s accept n v handler if n n p n a n v a v reply accept ok n 6 824 Spring 2011 Quiz II Solutions II Page 3 of 9 Two phase Commit 3 5 points Ben is building a replicated storage system There is just one client and the client performs just one storage operation read or write at a time waiting for each operation to complete before starting the next Ben wishes to store the data on two servers in order that the system be available that it continue operating even if one server fails He wants to ensure that the data on the two servers stay identical and is worried about the possibility that only one of the two servers might execute a client write Ben wonders whether making the writes at the two servers atomic using two phase commit as in Lecture 11 would be a good idea to ensure both or nothing behavior In the design he has in mind the client acts as the transaction coordinator TC The client would execute a write as described in lecture client sends write RPCs to server1 and server2 client waits for replies to both write RPCs client sends prepare messages to server1 and server2 if both repond yes client sends commit messages to server1 and server2 The system uses the timeout recovery scheme explained in lecture Ben thinks about this design for a while and eventually realizes that two phase commit as described in Lecture 11 is fundamentally not suited to providing availability via replication Please explain why Answer If one of the two servers is down two phase commit will abort every write this defeats Ben s goal of availability 4 5 points Halfway down page 386 of Liskov and Scheifler s Guardians and Actions paper about Argus the text says that a parent inherits the locks of a committing subaction Suppose instead that a commiting subaction released any locks it held that its parent did not also hold Explain how that would result in actions not being indivisible See the top of page 384 for a definition of indivisibility Answer Here s a situation in which action A1 executes in a way that another action A2 sees something other than the state before or after A1 i e the system does not provide indivisibility Suppose atomic objects X and Y both start out with value 0 Action A1 sets X to 1 in one sub action and then sets Y to 1 in a second sub action and then commits If A1 doesn t inherit the first sub action s lock on X then action A2 could execute between A1 s two sub actions and observe X 1 and Y 0 which is not the state before or after A1 6 824 Spring 2011 Quiz II Solutions Page 4 of 9 5 10 points Here s a simplified version of some code in Figure 2 of the Argus paper from the add user handler action drop add user user reg add user user drop end This code first sends an RPC to a maildrop server to create storage for the user s mail messages then sends an RPC to the registry asking it to add an entry to its table mapping each user name to the maildrop server that holds the user s mail messages Suppose the RPC to the registry server times out no reply is received If this code were using the YFS RPC package it would not know whether the registry server had received and processed the RPC So it would not know whether to recover by asking the maildrop server to delete the server correct if the registry server didn t receive the RPC or whether to leave the user s entry on the maildrop server correct if the registry server did receive the RPC Explain how Argus handles the above situation Answer Argus uses two phase commit to ensure that either both the maildrop server and the registry server add the user or neither does Both servers modify a shadow copy of their data when they execute the RPC If both RPCs succeed and the action finishes normally then Argus will execute two phase commit to tell both servers to copy the shadow data to the real data storage If one of the RPCs fails or anything else causes the action to abort then Argus will tell all servers that participated to abort their part of the action and throw away the shadow copy of the data 6 824 Spring 2011 Quiz II Solutions III Page 5 of 9 PNUTS You re running a PNUTS system see the paper by Cooper et al Records X and Y both start with value zero Here are two functions that use the API described in Section 2 2 of the PNUTS paper fn1 x1 read any X x1 x1 1 write X x1 X x1 write Y x1 …