Homework 11

Due 4/20/2012 [start of section]

Problem 1

• at-most-once semantics
• at-least-once semantics
• two-phase commit
• transactions

Problem 2

1. A network with 200 microsecond overhead, 10 Mbyte/s bandwidth, 20 microsecond latency
2. A network with 20 microsecond overhead, 10 Mbyte/s bandwidth, 200 microsecond latency
3. A network with 20 microsecond overhead, 1 Mbyte/s bandwidth, 2 microsecond latency
4. A network with 2 microsecond overhead, 1 Mbyte/s bandwidth, 20 microsecond latency

Problem 3

Suppose two nodes, A and B, communicate via messages and that the probability of receiving any message that is sent is P (0 < P < 1 ). You need not consider any other types of failures.

1. Is it possible for A and B to agree with certainty to perform some action (but not necessarily perform it at the same time)? If not, explain why not. If so, describe a protocol that provides this guarantee.

2. Is it possible for both nodes to agree to do the same thing at the same time with >99.99999% certainty (e.g. guarantee that there is less than a 0.0000 1% risk that one or both will fail to make the appointment)? If not, explain why not. If so, describe a protocol that provides this guarantee.

3. Suppose that in addition to lost messages, either A or B may crash at any time and, once crashed, recover at some arbitrary time in the future. Is it possible for A and B to agree with certainty to perform some action (but not necessarily perform it at the same time)? If not, explain why not. If so, describe a protocol that provides this guarantee

Problem 4

Suppose a server workload consists of network clients sending 128-byte requests to a server which reads a random 50KB chunks from a server's file system and transmits that 50KB to the client. The server's file system is able to cache all metadata, so that each read consists of a single 50KB sequential read from a random location on disk. The server may have multiple disks and multiple network interfaces.

Each disk rotates at 10000 RPM and takes 5 ms on an average random seek. There are on average 300 sectors per track and each sector is 512 bytes (in actuality, the number of sectors per track will vary, but we'll ignore that. We'll also assume that each request is entirely contained in one track and that each starts at a random sector location on the track.)

To access disk, the CPU overhead is 30 microseconds to set up a disk access. The disk DMAs data directly to memory, so there is no CPU per-byte cost for disk accesses.

Each network interface has a bandwidth of 100 Mbits/s (that's Mbits not MBytes!) and there is a 4 millisecond one-way network latency between a client and the server. The network interface is full-duplex: it can send and receive at the same time at full bandwidth. The CPU has an overhead of 100 microseconds to send or receive a network packet. Additionally, there is a CPU overhead of .01 microseconds per byte sent.

1. How many requests per second can each disk satisfy?

i1 = 0;
while(true){
  overwriteFile("/foo", i1);
  i1++;
}

while(true){
  int i2 = readValueFromFile("/foo");
  overwriteFile("/bar", i2);
}

  int i2 = readValueFromFile("/bar");
  int i1 = readValueFromFile("/foo");