Department of Electrical Engineering and Computer Science MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6 824 Spring 2005 Second Exam Answers 14 Number of students 12 10 8 6 4 2 0 0 10 20 30 40 50 60 Score in Range x x 10 70 80 90 100 The average is 62 The standard deviation is 16 1 I Part One 1 10 points Why does Frangipani distinguish between read locks and write locks Why is that a better approach than having a single kind of lock The read locks allow multiple Frangipani servers to cache and use files and directories at the same time This concurrency will increase total performance for read intensive workloads 2 15 points Look at the pseudo code in Section 3 1 of the Ivy paper Li and Hudak s Memory Coherence in Shared Virtual Memory Systems Observe this code at the end of the Write Server IF I am manager THEN BEGIN lock info p lock invalidate p info p copy set Suppose that the programmer implementing this code accidentally swaps the lock and invalidate so that the implementation looked like this IF I am manager THEN BEGIN invalidate p info p copy set lock info p lock Explain a specific situation in which this erroneous code would cause Ivy to produce incorrect memory contents Host H1 takes a write fault on a page asks the manager for write access and the manager executes the invalidate but has not yet locked Host H2 takes a read fault on the same page and completes the entire read process which involves the manager adding H2 to copy set Now the manager gets the lock on behalf of H1 s write clears copy set and gives ownership of the page to H1 Now H1 can write the page which will result in H2 having a stale copy of the page 2 II Paxos The Reliable Computing Corporation RCC has designed a fault tolerant airline seat reservation service Travel agents send reservation requests to the service over the Internet and the service responds with either a seat reservation or an error indication Obviously it is vital that the service not assign the same seat to two different passengers RCC s system achieves fault tolerance by replicating the reservation state on three servers The state consists of a list of the reservation requests that have been granted in the order that they were granted Each entry in the list contains the seat number the passenger name and a request ID included by the travel agent in each request message The request ID allows the service to recognize retransmitted requests and reply with the information from the record that s already in the list rather than incorrectly allocating a new seat A server can tell which seats have already been reserved by scanning the reservation list RCC uses a replicated state machine to ensure that the servers have identical reservation lists The three servers use Paxos see the notes for Lecture 15 to agree on each new reservation to be added to the list They execute Paxos for each reservation rather than just using Paxos to agree on a new view and primary after each server failure Each value that the servers agree on looks like reservation list entry number 37 assigns seat 32 to passenger Robert Morris with request ID 997 When a server receives a request from a travel agent it scans its reservation list to find the next available seat and the next list entry number and uses Paxos to propose the value for that list entry number The system runs a separate instance of Paxos to agree on the value for each numbered list entry The three servers are S1 S2 and S3 S1 receives a request from a travel agent asking for a seat for Aaron Burr S1 picks Paxos proposal number 101 this is the n in Lecture 15 At about the same time S2 receives a request asking for a seat for Alexander Hamilton S2 picks Paxos proposal number 102 Both servers look at their reservation lists and see that the next entry number is 38 and that the next seat available is seat 33 Both servers start executing Paxos as a leader for reservation list entry number 38 Each of the three sequences below indicates the initial sequence of messages of a possible execution of Paxos when both S1 and S2 are acting as leader Each message shown is received successfully The messages are sent and received one by one in the indicated order No other messages are sent until after the last message shown is received Your job is to answer these questions about the final outcomes that could result from each of the initial sequences Is it possible for the servers to agree on Aaron Burr in seat 33 as entry 38 Is it possible for them to agree on Alexander Hamilton in seat 33 as entry 38 For each of these two outcomes how it could occur or how does Paxos prevent it from occurring 3 S1 S1 PREPARE 101 S1 S1 RESPONSE nil nil S1 S2 PREPARE 101 S2 S1 RESPONSE nil nil S1 S3 PREPARE 101 S3 S1 RESPONSE nil nil S2 S1 PREPARE 102 S2 S2 PREPARE 102 S2 S3 PREPARE 102 the rest of the Paxos messages 3 5 points Answers Only Alexander Hamilton because S2 s PREPARE will cause all servers to ignore S1 s subsequent ACCEPT S1 S1 PREPARE 101 S1 S1 RESPONSE nil nil S1 S2 PREPARE 101 S2 S1 RESPONSE nil nil S1 S3 PREPARE 101 S3 S1 RESPONSE nil nil S1 S3 ACCEPT 101 Aaaron Burr S2 S1 PREPARE 102 S2 S2 PREPARE 102 S2 S3 PREPARE 102 the rest of the Paxos messages 4 5 points Answers Either Aaron Burr or Alexander Hamilton If S2 hears a RESPONSE from S3 S2 will propose Aaron Burr If S2 does not hear a RESPONSE from S3 S2 will propose Alexander Hamilton 4 S1 S1 PREPARE 101 S1 S1 RESPONSE nil nil S1 S2 PREPARE 101 S2 S1 RESPONSE nil nil S1 S3 PREPARE 101 S3 S1 RESPONSE nil nil S1 S3 ACCEPT 101 Aaaron Burr S1 S1 ACCEPT 101 Aaaron Burr S2 S1 PREPARE 102 S2 S2 PREPARE 102 S2 S3 PREPARE 102 the rest of the Paxos messages 5 5 points Answers Only Aaron Burr Any majority of RESPONSEs that S2 hears in Phase 2 will include the value Aaron Burr so S2 will propose Aaron Burr 6 10 points Suppose one of the RCC servers has received an ACCEPT for a particular instance of Paxos i e for a particular reservation list entry but never received any indication about what the final outcome of the Paxos protocol was Outline what steps the server should take to figure out whether agreement was reached and to find out the agreed on value Explain why your procedure is correct even if there are still active leaders executing this instance of Paxos The server should send messages to all the servers asking them whether they accepted an ACCEPT message If a majority of them respond with the same value then agreement has been reached This …