Department of Electrical Engineering and Computer Science MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6 824 Spring 2005 Midterm Exam Answers 20 Number of students 15 10 5 0 60 70 80 90 100 110 120 Score in Range x x 10 130 140 150 The average is 117 The standard deviation is 19 1 Cite as Robert Morris course materials for 6 824 Distributed Computer Systems Engineering Spring 2006 MIT OpenCourseWare http ocw mit edu Massachusetts Institute of Technology Downloaded on DD Month YYYY I Part One 1 10 points Suppose you re running Mach 3 0 on a MIPS R3000 You re getting tired of how slow your 15 year old CPU is You hear that Anderson et al authors of the Interaction pa per have started a company that sells a MIPS R3000 compatible CPU called the Mathom2000 The Mathom2000 runs operating system primitives about 100 times as fast as the R3000 and application code at the same speed as the R3000 If you upgraded to the Mathom2000 approximately how much faster overall would your programs run Explain your answer based on evidence presented in the Interaction paper Based on Table 7 applications spend 5 20 of their running time in OS primitives On the 2x Mathom2000 a program that runs in x seconds on the R3000 will take 05x 100 95x to 100 1 95 x 100 to 8x 9505x to 802x seconds The corresponding speedup is approximately x 1 8 x 100 5 20 If my programs follow similar behavior as the ones in Table 7 I can x expect an overall speedup of 5 20 when I upgrade to the Mathom2000 2 10 points Look at Figure 3 of Backtracking Intrusions by King and Chen The paper says that GraphGen ignores the event at time 7 Why is that correct Why couldn t the contents of le 2 have been part of the attack The result of the attack is that le X has the wrong contents so GraphGen should include all events that can affect the contents of le X The event at time 6 is the one that directly changes the contents of le X The event at time 7 does not affect the contents of le X because it happens after the event that directly modi ed the contents of le X The contents of le 2 were not read at any point in time before the write to le X or the creation of any processes that affect le X File 2 might have been part of the attack but its contents did not have any effect on the contents of le X II Part Two Porcupine 3 10 points Look at Figure 6 of the Porcupine paper by Saito et al When skew is zero most of the policies process about 700 to 800 messages per second Suppose the CPUs were replaced with CPUs ten times as fast Approximately how many more messages per second would the system be able to process Why Each of the nodes in the Figure 6 experiments has a single slow disk Therefore the disk is most likely to be the bottleneck at each node According to Table 1 the CPU utilization of a single server running at maximum throughput is only 15 in the no replication case Hence increasing the speed of the CPUs will increase the message throughput by less than 15 2 Cite as Robert Morris course materials for 6 824 Distributed Computer Systems Engineering Spring 2006 MIT OpenCourseWare http ocw mit edu Massachusetts Institute of Technology Downloaded on DD Month YYYY 4 10 points Look at the S1 and S2 policies in Figure 6 when skew is 1 0 As you can see the data points are hard to read Based on the explanations in the rest of the paper how many messages second would you expect S1 to process with skew of 1 0 And how much faster than S1 would you expect S2 to be Explain your answers With skew of 1 0 all messages are handled by one machine so the result for S1 should be the same as for the maximum throughput for one node with a single disk with no replication which according to Figure 4 is 23 messages second S2 should double the message throughput of S1 since S2 spreads the load over two servers 5 10 points Suppose you run a Porcupine experiment like D1 in Figure 6 with skew of 1 0 However when the system is rst started all the users mailbox fragments are placed on the same server node N0 Towards the beginning of the experiment approximately how many messages second will the Porcupine cluster be able to process Towards the end If there is a change in performance explain when this change occurs and what speci c steps Porcupine takes as it is running that lead to the change Towards the beginning the throughput should be similar to the maximum throughput of a single node 23 messages second because all messages are handled by node N0 The D1 policy will only append new mail to a user s existing mailbox fragment However after a user deletes all mail which deletes the fragment the next arriving mail message will be placed in a new fragment on an unloaded server This gradual load balancing causes throughput to increase to the level of ordinary D1 with skew 1 0 6 10 points Figure 6 suggests that the dynamic spread policy is only useful when skew is high The authors generate the high skew workloads by using user names that all hash to the same value How valuable would dynamic spread be in real life Are there any speci c situations that are likely to occur in which the dynamic spread policy would signi cantly increase performance Dynamic spread would be useful if a small fraction of the users received a large fraction of the mail III Part Three OK Auctions You ve been hired as a consultant by OK Auctions to help make their web site secure OK Auctions runs an on line auction system At any given time there are thousands of auctions in progress Users can log into the system get a list of current auctions and place bids on one or more auctions Each auction lasts for a few days when it ends the highest bidder wins and must pay the amount of his or her bid OK Auctions most pressing security concern is to ensure that users do not learn each others bids while an auction is in progress OK Auctions wants to prevent users from placing bids that are only slightly higher than the existing high bid since that would decrease winning bid values and thus pro ts They are worried that someone might exploit a bug in their software and steal high bids 3 Cite as Robert Morris course materials for 6 824 Distributed Computer Systems Engineering Spring 2006 MIT OpenCourseWare http ocw mit edu Massachusetts Institute of Technology Downloaded on DD Month YYYY OK Auctions current web site consists of a single process running on a UNIX server The process accepts HTTP connections checks usernames and passwords maintains …