Exercise 9: an algorithm to record global state assuming the communication network is reliable.

[dag7dev]

Exercise 9: Consider a distributed system where every node has its physical clock and all physical clocks are perfectly synchronized. Give an algorithm to record global state assuming the communication network is reliable. (Note that your algorithm should be simpler than the Chandy–Lamport algorithm.)

[susannacifani]

The solution on Drive seems right to me.

A distributed system where every node has its physical clock and all physical clocks are perfectly synchronized implies that we have access to a real-time global clock. Assuming the communication network is reliable (so message delays are bounded), the monitor process starts the protocol by broadcasting a "take snapshot" message at time $t_0$ for time $t \geq t_0 + \delta$. At time $t$, each process sends its snapshot to the monitor, which can reorder them in increasing timestamp order.
The time complexity goes from $O(n^2)$, required by the Chandy-Lamport algorithm, to $O(n)$.

[simonesestito]

Why can't we simplify it?

• every process keeps track of the timestamp (global) of each event
• $p_0$ sends at time $t_0$ the request to obtain all the events with timestamp prior to $t_0$
• other processes just send them as soon as they can
• $p_0$ reorders them

This way we have no assumption on time bounded messages and it can be faster