This is a homework, but these questions will give you some idea of the kind of questions to expect on the midterm and final. (The exam questions will respect the very limited amount of time there is to answer them, of course.)

In all questions, TOMCast mean the Lamport clock implementation. (Whether or not ACKs are included is explicit in each question.)

1. Imagine a fully working implementation of TOMCast, including ACKs. By "fully working" I mean it implements the Lamport clock algorithm described in the lecture slides, including any corner cases not covered by the slides, and so gets correct results when no packets are dropped.

   Now imagine in some run of this code that exactly one packet is dropped. Describe the overall effect on the multicast group. To help make clear what I'm looking for, I'll answer the first one.

   • A CLIENT_MCAST packet sent to A isn't received by A.

     Client A fails to print the message that is the payload of the dropped packet, and fails to send ACKs for it. All other clients print the contained message, in a consistent order. There is no other correctness impact on the group as a whole, and no significant performance/behavioral impact so long as client A sends or recieves a packet "soon" after the dropped one.

   • A CLIENT_SERVER_HELLO packet from A to the lobby isn't received by the lobby.

   • A SERVER_CLIENT_HELLO packet from the lobby to A isn't received by A.

   • A CLIENT_CLIENT_GOODBYE sent from A to B isn't received by B.

   • An ACK sent from A to B, prompted by A's having received a packet from C, isn't received by B.

2. Counting only CLIENT_MCAST and ACK packets, what fraction of the packets sent are MCAST packets? (Assume no packet losses.)

3. Suppose that UDP were completely reliable: every packet given to UDP to send always got to the UDP protocol layer at the destination. The chat client would still not be guaranteed a reliable network, because MCast and TOMCast (in homework 2 part A) are not reliable.

   Explain why they're not reliable, and briefly describe a scenario that will cause them to lose packets.

4. Suppose everyone in the class has written a correct TOMCast implementation, with one small exception, and we hook them up using a correct lobby into one big multicast group. (The lobby follows the lobby protocol in the assignment.) Further assume that no packets are lost (by the hardware network or by anyone's software.)

   The one small exception is this: one TOMCast implementation is in all ways correct, except that it forgets to update the clock when a packet is received. That is, its clock updates come about solely by incrementing the clock each time it sends (a CLIENT_MCAST or an ACK).

   A. Will all clients print whatever messages they print in a consistent order?

   B. Will all clients print all messages, assuming all clients eventually terminate generating messages?

   C. Suppose you had a complete log (a printout, say) of all packets your client had sent and received while participating in this multicast group, but no other information about what had happened. Could you prove, using only that printout, that some client had misbehaved (not followed the protocol)? Could you tell which client it was that was misbehaving?

5. Suppose Bob and Charlie are regular members of a chat group that gets together every night from 7:00PM to 8:00PM. Bob has written his own chat, TOMCast, and MCast implementations. Further, Bob has really come to dislike Charlie. To goad Charlie, Bob changes his implementation so that when he receives a CLIENT_MCAST packet from Charlie with timestamp T and containing message M, Bob sends (multicasts) a TOMCast packet with timestamp T-2 and message M. (This is off the idea of this question, but in case it bothers you: Bob first changes "Charlie says..." in M to "Bob says..".)

   A. Will all clients print all messages in a consistent order?

   B. Suppose Charlie claims Bob is doing this, but Bob responds that it's in fact Charlie who's copying Bob. Can Charlie suggest a procedure that each other person in the group can follow (using only the printout of the packets that other person has received) that will show definitively that Bob is copying him? (You can assume that all clients can assume that either everyone is operating according to the rules (in which case Bob is not copying Charlie) or else that the only violation of the rules is the copying described above.)

6. Suppose we have correctly working HW2 Part A chat, TOMCast, and MCast implementations (with or without ACKs), and suppose we use them to engage in a TOMCast chat session in which a few billion messages are exchanged. In this case, it's possible the total ordering property will be violated.

   Why?