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.

Let p1 be the transmitter and v be the value it wishes to broadcast reliably. This value is from the domain V. There are two other values, neither in V: ∅, which a process p sends to q to indicate that p failed to receive an expected message from q in the previous round, and ⊥, which a process p sends to q to indicate that p received a message from q sent in the previous round.

Each process p executes the following protocol.

d = none;

round 0:
  if (p == p1) {
    d = v;
    send(v) to all;
    }
  else send(⊥) to all;

round i: 1 ≤ i ≤ t:
  if (receive(∅) from any process) crash;
  if (receive(val ∈ V) from any process && d == none) {
    d = val;
    send(d) to all;
    }
  else for each process (q) {
    if (received message from q) send(⊥) to q;
    else send(∅) to q;
    }

round t+1:
  if (receive(∅) from any process && d == none) crash;
  if (receive(val ∈ V) from any process) d = val;
  if (d == none) decide(0);
  else decide(d);

It is easy to show that this protocol ensures that if a correct process sets d to val in round i < t + 1 then all processes that are not crashed by the end of round i set d to val in round i + 1. And, if a process sets d to val in round t + 1 then a correct process set d to val in some round i < t + 1. So, all we need to show is that if a send-faulty process sets d to val in some round i < t + 1 and later decides, then all processes that decide have set d to val by round t + 1.

A process x that is send-faulty will crash itself if it learns it has committed a send omission. Thus, if a send-faulty process decides, then it sent all expected messages to all correct processes in each round. Thus, if x sets d to val in some round i < t + 1, then each correct process receives val by round i + 1. And, similar to above, if x sets d to val in round t + 1, then a correct process set d to val in some round i < t + 1.

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.

Let p1 be the transmitter and v be the value it wishes to broadcast reliably. This value is from the domain V.

This problem requires n > 2t. An informal proof is: assume it is solvable with n ≤ 2t. Divide the processes into two sets A and B, each containing t or fewer processes. Let p1 be in A and let v ≠ 0 (where 0 is the default decision value). Consider three runs:

1. In the first run, let all the processes in A crash in the first step. All the processes in B eventually decide 0.
2. In the second run, let all processes in B crash in the first step. All the processes in A eventually decide v.
3. In the third run, let all processes in B be receive-faulty only with processes in A. This run is indistinguishable to the first run by the processes in B, and is indistinguishable to the second run by the processes in A. Hence, eventually the processes in A decide v and the processes in B decide 0; this violates uniformity

   Each process p executes the following protocol. The value ⊥ ∉ V is a heartbeat.

   d = ⊥
   silent[1..n] = [false, ..., false];
   round 0:
     if (p == p1) {
       d = v;
       send(v) to all;
       }
     else send(⊥) to all;
   
   round i: 1 ≤ i ≤ t+1:
     for each process q:
       if (did not receive message from q) silent[q] = true;
     if (more than t elements of silent are true) crash;
     if (receive(val ∈ V) from any process && d == none) {
       d = val;
       send(d) to all;
       }
     else send(⊥) to all;
   
   round t+2:
     for each process q:
       if (did not receive message from q) silent[q] = true;
     if (more than t elements of silent are true) crash;
     if (receive(val ∈ V) from any process) d = val;
     if (d == none) decide(0);
     else decide(d);
   

   As with the previous protocol, it is easy to show that this protocol ensures that if any process sets d to val in round i < t + 1 and does not crash in this round, then all correct processes set d to val in round i + 1. And, if a process sets d to val in round t + 1 then some process set d to val in some round i < t + 1 and did not crash in that round. So, we need to show that if a process sets d to val in some round i < t + 1 and does not crash, then a receive-faulty process either sets d to val by round t + 2 or crashes itself before deciding.

   Since this protocol runs for t+2 rounds, and all correct processes receive v by round t+1, each correct process will have broadcast v by round v+2. If a receive-faulty process receives none of these messages, then it will detect this fact and crash itself before deciding.

   ---

4. 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.

      
      Here's s simple example. It is trivially FIFO and causal, and is not total. Repeating this pattern of messages is also FIFO, causal and not total.
      
      
      

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

      Assume i executed bc-send(m1) causally before j executed bc-send(m2). This means that j executed bc-recv(m1) before executing bc-send(m2). By definition, j executed bc-send(m2) before executing bc-recv(m2), and so j executed bc-receive(m1) before executing bc-recv(m2). Since the broadcast is total, i executed bc-recv(m1) before executing bc-recv(m2). Thus, the broadcast primitive is causal.

30 January 2009 by kam