Distributed Computing

Non-fifo Snapshot, the key idea (hw 1):

In the FIFO network, when node u receives a signal from its neighbor that it took a snapshot, it knows that all the future messages it receives from its neighbor are “after” the snapshot and hence are not part of it. Hence, node u starts recording messages received from its neighbor v at the time u takes a snapshot of its own state until it receives such a signal from v. If the signal from v caused u to take its snapshot then no messages are in transit from v to u in this snapshot. Thus the termination of the recording of all messages in transit from v to u is easily detectable. All messages which were received by node u over link (v,u) at or after Tu (the snapshot time at node u) but before the signal(taking_snapshot) of v arrives on this link, are obviously in transit in this snapshot.

In the non-FIFO discipline, we add acknowledgements (ACK) to messages. By the time node u has received an ACK for each of its messages from before it took a snapshot, all the messages in transit in the snapshot, that node u had generated, have been already arrived to their destination. Now there are two options, either node u records all the messages in transit at the snapshot on links from u to any of its neighbors, or the receiving end records all these messages. In the former case, a node that sends an ACK to a messages, flags the ACK whether it already took a snapshot. Node u then records all messages whose ACK is flagged. In the latter case, node v, a neighbor of u, records all un-flagged messages it receives from u after it took a snapshot until node u sends it a special message saying that all the messages in transit have already arrived.