Time, Clocks and synchronization
In a distributed world, the concept of time is very important for the progress of operations. Time is available on a local processor because it relies on a clock or counter. In the distributed world, there is no shared clock. Yet the shared notion of time is critical. Instead of maintaining a shared central counter for the the time, let us look at how this time is used.
The processors want to know about time because they are looking to order their events. Time is used to place events such that some events "happen before" others. In a distributed system, there are three ways in which a certain event affects another.
1) A and B are on the same processor and A is earlier in computation before B
2) A and B are on different processors and A sends a message to B
3) A can affect a third event C and C can affect B
Let us look at how to represent these events. We know that events occurs on different processors on different time. So we can structure a diagram where all events that occur on a processor P are are arranged in a straight lines and there are parallel lines for different processors. The events are represented by the vertices on these lines and the "happens-before" relation is represented by directed edges between the vertices. Time proceeds to the right so the edges are directed up or down or towards the right. A horizontal axis represents the "true time"
An abstraction of a monotonic counter is used for a clock. The values read from this counter is the timestamp. But there is no central clock. Each processor maintains its own clock.
Timestamps are issued such that the timestamp is greater than all the events that happened before.
There are three cases :
Local event: the clock is merely incremented
Send event: the clock is incremented and the updated value is the timestamp for the event and the message
Receive evnet: : the clock is updated by the maximum of the current clock and the timestamp of the message.
The invariant here is that the clock shows the most recently assigned timestamp. This is the concept of the logical clock.
In a distributed world, the concept of time is very important for the progress of operations. Time is available on a local processor because it relies on a clock or counter. In the distributed world, there is no shared clock. Yet the shared notion of time is critical. Instead of maintaining a shared central counter for the the time, let us look at how this time is used.
The processors want to know about time because they are looking to order their events. Time is used to place events such that some events "happen before" others. In a distributed system, there are three ways in which a certain event affects another.
1) A and B are on the same processor and A is earlier in computation before B
2) A and B are on different processors and A sends a message to B
3) A can affect a third event C and C can affect B
Let us look at how to represent these events. We know that events occurs on different processors on different time. So we can structure a diagram where all events that occur on a processor P are are arranged in a straight lines and there are parallel lines for different processors. The events are represented by the vertices on these lines and the "happens-before" relation is represented by directed edges between the vertices. Time proceeds to the right so the edges are directed up or down or towards the right. A horizontal axis represents the "true time"
An abstraction of a monotonic counter is used for a clock. The values read from this counter is the timestamp. But there is no central clock. Each processor maintains its own clock.
Timestamps are issued such that the timestamp is greater than all the events that happened before.
There are three cases :
Local event: the clock is merely incremented
Send event: the clock is incremented and the updated value is the timestamp for the event and the message
Receive evnet: : the clock is updated by the maximum of the current clock and the timestamp of the message.
The invariant here is that the clock shows the most recently assigned timestamp. This is the concept of the logical clock.
No comments:
Post a Comment