Note: The table slide has a typo. Should be "The algorithm does not explicitly keep these vectors..."

Note: Consider only the values of the Lamport clocks at each node, and the timestamps they've seen on messages they've received, assuming that the events listed in the left column are correct. That is, don't worry about whether or not the events actually follow the algorithm. (We'll come back to that in question 4.)

Does this work, in the sense of providing an RTOM implementation (as defined on slide 4), under the same assumptions as before (that the underlying network provides reliable, pairwise-ordered communication, there are no node failures, and no nodes try to join or leave the multicast set)?

If so, briefly explain why. If not, describe a counter-example (a situation in which it fails).

Note: Local clocks on different machines are not synchronized.

Note: Remember that two different machines sending messages with the same timestamp is a problem we can handle by resolving the tie using the node id's of the senders (which are unique, and so can't tie). That is, two distinct nodes assigning the same timestamp to two different messages isn't a problem.

Note: On the other hand, a single node assigning the same timestamp to two different message may (or may not) be a problem. To eliminate the possibility it is, assume that the realtime clocks are such high precision (tick so fast) that no two messages sent by the same machine can have the same timestamp.

Note: For the purposes of this question we don't care if some machine gets to display all its messages first, because its clock is way behind all the others. We're only interested in whether or not RTOM is guaranteed.

Here it is a bit more precisely. The constants POST and MSG are ways for the server to distinguish a message it sends to itself for delivery into the queue from those it is re-sending for display:

All nodes:
   On m-send(m):
       net-send(N0,POST,m);

   When (MSG, m) is received:
       deliver(m);

The server (node N0) does this additionally:
   When (POST,m) is received:
       put m at the tail of a queue;

   When the queue is not empty:
       remove the message, m, at the head;
       foreach client c {
          net-send(c, MSG, m);
       }

The server completes sending each MSG m to all clients before it is willing to dequeue another
one.


(N0 is a regular client node, as well as acting as the server, so does all of the above.)

(A) Briefly explain why this works (implements RTOM).
(B) Compare it qualitatively to the RTOM implementation given in the notes. Ignoring the simplicity or complexity of the algorithms as a factor, identify a significant advantage of this implementation over the one in the notes. Identify a significant disadvantage.

Did that break the algorithm, or does it still work with this modification? Briefly explain.

Scheme A: XOR each consecutive 16-bits of the data with each other, and send the result as the ECC bits.

Scheme B: Take each consecutive 16-bits, consider it an unsigned integer, and compute their sum, using infinite precision arithmetic. Send the significant bits of the result as the ECC bits.

Scheme A is identical to the constant-sized portion of what a 2-d parity scheme computes. Scheme B is the Internet checksum algorithm, but having simplified away the things that make it confusing to understand in detail. (One downside is that the number of ECC bits for scheme B depends on the amount of data, which it didn't with Internet checksum. Doesn't matter for the purposes of this question, though.)

(A) Describe a transmission error that scheme A will detect but scheme B will not.
(B) Describe a transmission error that scheme B will detect but scheme A will not.