Distributed computing

LOGICAL CLOCKS

• Clocks are a way of assigning a number to an event. Each process has its own clock.
• For now, clocks will have nothing to do with real time, so they can be implemented by counters with no actual timing mechanism.
• Clock condition: For any events A and B, if A  B, then C(A) < C(B).

IMPLEMENTING LOGICAL CLOCKS

• Each process increments its local clock between any two successive events.
• Each process puts its local time on each message that it sends.
• Each process changes its clock C to C’ when it receives message m having timestamp T. Require that C’> max(C, T).

IMPLEMENTATION OF LOGICAL CLOCKS

• Receiver clock jumps to 14 because of timestamp on message received.

• Receiver clock is unaffected by the timestamp associated with sent message, because receiver’s clock is already 18, so greater than message timestamp.

• 13

• 14

• 8

• 13

• 19

• 18

ORDERING ALL EVENTS

• We want to define a total order .
• Suppose two events occur in the same process, then they are ordered by the first condition.
• Suppose A and B occur in different processes, i and j. Use process ids to break ties.
• LC(A) = A|i, i.e. A concatenated with i.
• LC(B) = B|j.
• The total ordering  is called Lamport clock.

ACHIEVING MUTUAL EXCLUSION USING THIS CLOCK

• Goals:
• Only one process can hold the resource at a time.
• Requests must be granted in the order in which they are made.
• Assumption: Messages arrive in the order they are sent. (Remember, this can be achieved by handshaking.)

ALGORITHM FOR MUTUAL EXCLUSION

• To request the resource, Pi sends the message “request resource” to all other processes along with Pi’s local Lamport timestamp T. It also puts that message on its own request queue.
• When a process receives such a request, it acknowledges the message. (Unless it has already sent a message to Pi timestamped later than T.)
• Releasing the resource is analogous to requesting, but doesn’t require an acknowledgement.

• Pk

• Pi

• Pj

• Ack

• REQUEST

• Ack

• Ack

• REQUEST

• REQUEST

• RELEASE

• RELEASE

• Pi executes

• None needed