What does each node in the distributed
system know? Every node knows its own events,
meaning, what are the computational events that are
happening in its own execution. It also knows
about its communication events with the rest
of the nodes in the distributed system. So,
for instance, if this process Pi sends a
message to process Pj, that's a send event.
Pi knows about that. And similarly Pj when it gets this event, it's a
receive event. It knows about that. So, these are the only two kinds of events
that every node knows about, its own
computational events, and its communication events with its
peers. For instance, process Pj has no
idea about the local computational events of Pi.
Lamport's logical clock builds on this very simple
idea, and the idea is that we want to
associate a timestamp with every one of the
events that are happening in every process in the
entire distributed system. How are we going to
do that? Well, we're going to have a local
clock, Ci over here, And Cj over here. And
this local clock can be anything, can be counter,
it can be a simple counter and what we
are doing is when I want to associate a timestamp
with a particular event that's happening in my process what
I'm going to do is I'm going to look at
this counter and see what the value of the counter is, associate that counter
value as a timestamp for this event A. So for this instance here I've said that
timestamp for a is two. And this counter monotonically increases
as we pile up events in our system. So
once I've associated this timestamp two with this event
a, I cannot associate the same timestamp with other
meaningful events that are happening in my process. And
therefore, I'll increment the timestamp. It's completely up to
your implementation as to whether you want to increase
this counter value by one, or two, by a
thousand, it doesn't really matter. So, in this case
for instance I've incremented the timestamp counter by two,
and so the next even that I'm going to
have in my process B is going to have
a timestamp of 4. So that's the idea behind
having a monotonically increasing counter to associate logical timestamps
with the events that are happening in my process.
Now, what about these communication events? Well, in particular,
let's look at this case here. A is a communication
event on process Pi. And this communication event
is going to have a timestamp of two associated
with it, because that's the time that I
generated this communication event, sent this message over. Comes
over to process Pj. When process Pj receives
this, that's an event. And so let's say we
call it event number d. And we have
to associate now a timestamp with, with event d.
How do I go about assigning a timestamp with
this? Well, we know that this timestamp that I'm going
to associate with this event d, has to be
greater than the timestamp associated with the send of that
message, right? Obviously you cannot receive a message that
has not been sent yet. And therefore, we're going to
say that d should have a timestamp which is
at least greater than a for sure. Now, what else
does d depend on? Well, it depends on other things
that are happening in my own process. For that, I
need to know what the current state of my local
counter is. So for instance, in my execution as I'm showing
you here I haven't done anything meaningful yet and therefore
my local counter is still pointing to zero indicating that
there have been no meaningful events here. So when this
message comes, that's the first time I'm going to do something
meaningful in this process. And I have to associate
a timestamp with d but I cannot associate the timestamp
of zero with it because the timestamp that I associate
with d has got to be greater than the timestamp
that is associated with the send event on process Pi.
And since the send event has this timestamp two, I
have to associate something higher than that. And so I
associate a timestamp three, with the receipt of this message.
That is, this particular event is going to have
a timestamp of, of three. So, the two conditions that
we have talked about. One is that events that are
happening in the same process I'm going to have a monotonically
increasing counter and I'm going to use that to associate
timestamps with the events that are happening in the same
process. That's the first thing. That is if I have
two events a and b in the same process and
I know that a happened before b, because, textually,
in the process because the process is sequential, a
happened before b and therefore the condition is that
the timestamp associated with a has got to be less
than the timestamp associated with b. Pretty straightforward. And
similarly the second condition is that if I have
two events, a and b, and a happens to
be a send event on some process and d happens
to be the receive event on another process then
we know that the receive event has to be
after the send event. And therefore the second condition
is that Ci(a), that is a timestamp associated with
a send event, has got to be less than
the timestamp associated with the receipt of the same
message, Cj(d). So in order to make this condition,
the second condition, valid, we're going to choose the
timestamp to associate with the receipt of a message
d as the max of the timestamp that is
associated with the send event incremented by some quantity.
Ci(a) plus plus. So in this case, it happens
to be two. So increment it and then say three and then you want to know what the
local counter is saying. So, Cj, so what we
pick as a timestamp to associate with d is
the max of the incoming timestamp with the
message and the local counter, whatever it is
pointing to. So that's how I'll pick the
timestamp to associate with a receive event. This brings
up a very interesting question and that is,
what about timestamps of events are happening concurrently in
a distributed system, and before I talk about
that, I want to give you a little quiz.