Now, low let's put Lamport's clock to work
for implementing a distributed mutual exclusion lock algorithm, and
it is going to be very similar to
the car-sharing example that I showed you before. And
also, you will notice that we've talked about
locks in a shared memory multiprocessor where we have
shared memory to implement the lock. But now,
in a distributed system, we don't have shared memory.
And we have to implement a mutual exclusion
lock using Lamport's Logical Clock. So, essentially what is
going to happen is that any Process that
needs to acquire this lock is going to send
the message to all the Processes. And of
course the intent to get a lock may, may
emanate simultaneously from several processes. That's perfectly feasible.
So the algorithm is as follows. Every process has
a data structure, a queue data structure. And those
are the queue's that are associated with process P1. This
is the queue that is associated with process P2. And
this is the queue that is asssociated with process Pn.
Every process has its own private queue. And the private
queue is ordered by the happened-before relationship that we have
discussed so far. So requests for a lock are going
to be time stamped and the protocol is as follows.
To request a lock, what a process is going to
do is send a message to all the other
Processes that I want this lock and my time
stamp is such and so. So it's going to associate the
local timestamp that it has from its counter, which
is its logical timestamp. It's going to associate that timestamp
as the request time for the lock and send
the message to all its peers. And all the peers,
what are they going to do? Well, two things.
One is they're going to stick that request into the
local queue. When a request comes from process Pn,
P1 puts it into its queue, appropriate place in
the queue, because it is ordered by the
timestamp. The smallest time stamp being the highest priority
request pending. So it puts it in its queue.
And the second thing it does is every process,
when it gets a request, puts it in its
queue and then acknowledges the request to its peers. So
let's look at the process P2 here and P2 generated
it's request at timestamp 10. What it did was first
put its request in its local queue and then it
sends a message to its peers. And these guys, when
they get the request, they look at their own local
queue and say well you know there is a request
pending In my queue, which has a time stamp
of 5, and this request that I just got from
P2 has a time stamp of 10, so I'm going to
order that behind the previous request. I put it over
here. I put it over here and once I
do that I'm going to acknowledge this request by sending a
message back to P2. And similarly this guy sends an
acknowledgement back to P2. So that's how the protocol works.
Every request is sent to all the other processors
and every process when it receives a request, it
puts it ordered by Lamport's clock in its own
local queue. And then acknowledges the request with an
act message. Now, what happens when there is a
tie? Well, when we have a tie, we break
the tie by giving priority to the process that
has a lower process ID so that's how this
algorithm works, so that every process can unambiguously make
a decision as to where to place an incoming
request in the queue. So an example of the
state of the queue is as shown. The thing that
should jump out at you immediately is that the
state of the queue is not the same in
all the processes. For instance Process 1's queue contains
its request that it generated at time 2, but I
don't see it yet in the other queues. Is this
possible that the queue can be inconsistent with one another?
Of course it is possible. The reason it is possible
is because a Process, when it generates a request, puts it
in it's queue and then sends a message out. This
message is going to take some time to reach the other
nodes in the distributed system. So, it sent the message
and after it sent the message it got requests from other
Processes and it has put it in its queue.
And it is possible that this message, all the messages
may not take the same amount of time to
traverse a network. We have no idea what's going on
in the network and therefore it so happens that P1's message is
still in transit. Whereas the request messages from P2 and Pn
have already made it everywhere, and it is in the queues of all the Processes,
but P1's message unfortunately, it's taking a
slow route throught the network and it is
still in transit. And in fact, P1 has
subsequently received P2's and PN's message and put
them into its its local queue. It is
just that P1's message hasn't reached its peers
yet and that's how you get this situation.
So the whole purpose of this exercise is
to unambiguously get the mutual exclusion lock for some
process that is competing for it simultaneously. Now how does
a process know that it has the lock? So I
have to make the decision that I have the lock.
How do I make that decision? Two things have
to be true for me to think that I have
gotten the lock. So the first thing is that my
request has to be at the top of the queue.
So now you see the messages that I talked about, that is P1's message to P2
and Pn not having reached the destination, eventually
they reach the destination. And they have acknowledged
it. And, as a result of that the queues are consistent now. P1's request is at
the top and it also has received acknowledgements
from everybody else. So the way you can
make a decision that you have the lock,
unambiguously, in the entire distributed system. Two conditions. First
thing, my request is at the top of the
queue. The second thing is I've received acknowledgments from
all the other nodes in the system. In this
case, all the other nodes were not requesting this
lock so they've sent me acknowledgments. And I've received
all the acknowledgements and there is no other request
that is ahead of me. I've also received lock requests
from P2 and Pn and they are later than mine and
that's how they've been ordered in the queue. So the two
conditions I'm going to look for to make a decision locally
that I have the lock is my request is at the
top of the queue and I've either received acknowledgements from all
the other nodes in the system, if nobody else is competing
for the lock at the same time, or all the requests
that I've gotten so far are later than
my own lock request. Let's say that I haven't
received the acknowledgement for my request from Q, Q2,
and Qn. Can I go ahead and assume I
have the lock? Yes, I can. Why? Because Even
though these guys have not sent me the acknowledgment
yet, it's coming, slowly coming. But I've received lock
requests from them, with timestamps 5 and 10 respectively.
Therefore I can make an unambiguous decision that my lock request precedes all
the other lock requests at this point of time. And I can go ahead and get the
lock. I'm sure you've figured it our
already but since we are following Lamport's cCock
in implementing this mutual execution lock algorithm,
the ACK message for a particular lock request
is going to have a later timestamp than the time stamp associated with the
request itself. So you can see that
Lamport's Logical Clock, with the addition of
a way of deriving a total order from the partial orders given by the Lamport's
clock, allows us to unambiguously make a decision locally based on the state
of local queue as to whether I have the lock or not.
Now let's talk about how I go about releasing the lock. So if
I have the lock. I have used it for a while and
now I am ready to say, well I am done with a lock,
I can release it. What do I do? Well I am going to
send an unlock message to all the other guys. The first thing that
I do, of course, is get rid of the entry that I have
in my queue because I am done with the lock. I can remove
it from my queue. Once I remove it from
my queue I am going to send an unlock message
to everybody else. So the state of the queue
indicates that the unlocked message hasn't reached yet. It is
in transit. It is going to eventually reach these
guys. And when the peers receive the unlocked message they're
going to basically remove the entry, the corresponding entry, from
the respective queues. So P1's turn with using the lock
is complete now. It has done its lock and has done its unlock and
now other Processes in the system, if they're competing for the same lock, can
use the same decision making process to figure out whether they are the winners
for getting the lock next and using
it and entering the respective critical sections.