1. In class, we gave a round-based protocol for consensus in synchronous systems for crash failures. Give a round-based protocol for consensus in synchronous systems for send omission failures. A send omission is a failure in which a process attempts to send a message but the message is instead dropped. Hint: in each round, have processes send messages in a way that each process can determine whether or not it has suffered a send omission. If a process i determines this, then have it crash itself. Assume that no more than t processes can be faulty, where a faulty process can have send omission failures, can crash, or can do both.

   ---

2. Like the previous problem, come up with a round-based protocol for receive omission failures. A receive omission is a failure in which a process attempts to receive a message that has been sent to it, but the message is instead dropped. Assume that no more than t processes can be faulty, where a faulty process can have receive omission failures, can crash, or can do both.

   ---

3. Consider a broadcast service with the following interface:

   • bc-send(m): A process i presents a message m to be broadcast to all processes in the group (including i).

   • bc-recv(m): A process i receives a message m that was broadcast to all processes in the group.

   Neither of these operations block: the first one does not wait for the message to be received by all processes, and the second one works in an interrupt-like fashion.

   We define three different ordering requirements:

   1. FIFO: if a process i executes bc-send(m1) before executing bc-send(m2), then no process executes bc-recv(m2) before executing bc-recv(m1).

   2. Causal: if process i executing bc-send(m1) happens before process jexecuting bc-send(m2), then no process executes bc-recv(m2) before executing bc-recv(m1). In this case, we define "happens before" in terms of local events and bc-send(m), bc-recv(m) events.

   3. Total: For all messages m1 and m2 and all processes i and j, if i executes bc-recv(m1) before executing bc-recv(m2), then process j does not execute bc-recv(m2) before executing bc-recv(m1).

   Answer the following two questions about this kind of service.

   1. Give a space-time diagram of that illustrate an execution of a broadcast service that is FIFO and causal but not total.

   2. Prove that if a broadcast service is both FIFO and total, then it is also causal.

30 January 2009 by kam