Synchronization
Christian’ Algorithm
Berkeley’s Algorithm
Lamport’s Logical(scalar) Clock
Lamport’s Logical Clock
Vector Timestamp Ordering
Vector Timestamp Ordering
Coordinator Selection
Election Algorithms
The Bully Algorithm (1)
The bully election algorithm
• Process 4 holds an election
• Process 5 and 6 respond, telling 4 to stop
• Now 5 and 6 each hold an election
Global State (3)
d) Process 6 tells 5 to stop
e) Process 6 wins and tells everyone
A Ring Algorithm
Election algorithm using a ring.
Requirements of Mutual Exclusion
Algorithms
1. Safety property: At most one process may execute in the critical
region (CR) at a time.
2. Liveness property: A process requesting entry to the CR is
eventually granted it. There should not be deadlock and starvation
3. Fairness: Each process should get a fair chance to execute the
CR.
Performance Metrics
1. Synchronization delay: Time interval between critical region (CR)
exit and new entry by any process.
2. System throughput: Rate at which requests for the CR get executed.
3. Message complexity: Number of messages that are required per CR
execution by a process.
4. Response time: Time interval from a request send to its CR
execution completed.
Classification of Mutual Exclusion
Algorithms
• Centralized mutual exclusion algorithms
• Distributed mutual exclusion algorithms
• Non-token-based algorithm:
• Lamport’s Distributed Mutual Algorithm
• Ricart–Agrawala Algorithm
• Maekawa’s Algorithm
• Token-based algorithm:
• Suzuki–Kasami’s Broadcast Algorithm
• Singhal’s Heuristic Algorithm
• Raymond’s Tree-Based Algorithm
Mutual Exclusion:
A Centralized Algorithm
a) Process 1 asks the coordinator for permission to enter a critical region.
Permission is granted
b) Process 2 then asks permission to enter the same critical region. The
coordinator does not reply.
c) When process 1 exits the critical region, it tells the coordinator, when
then replies to 2
Performance Parameters
1. The algorithm is simple and fair as it handles the request in the
sequential order.
2. It guarantees no starvation.
3. It uses three messages as REQUEST, REPLY and RELEASE.
4. It has a single point of failure.
5. Coordinator selection could increase synchronization delay
especially at times of frequent failures.
Lamport’s Distributed Mutual Algorithm
Performance Parameters
• Lamport’s algorithm has message overhead of total 3(N − 1)
messages: N – 1 REQUEST messages to All process (N minus
itself), N −1 REPLY messages, and N −1 RELEASE messages
per CR invocation.
• The synchronization delay is T. Throughput is 1/(T + E).
• The algorithm has been proven to be fair and correct. It can also
be optimized by reducing the number of RELEASE messages
sent.
Ricart–Agrawala Algorithm
Performance Parameters
The algorithm does not use explicit RELEASE message.
The dequeuing is done on the receipt of REPLY itself.
Thus, total message overhead would be 2(N − 1) messages,
that is, for entering a CR, (N − 1) requests and exiting (N −
1) replies.
2. The failure of any process almost halts the algorithm
(recovery measures are needed) as it requires all replies.
Maekawa’s Algorithm
Properties of a Quorum Set
Performance Parameters
1. An execution of the CR requires N
REQUEST, N REPLY and N RELEASE
messages, thus requiring total 3 N messages per
CR execution.
2. Synchronization delay is 2T.
3. M = K = N works best.
Token-Based Algorithms
Suzuki–Kasami’s Broadcast Algorithm
Performance Parameters
1. It is simple and efficient.
2. The algorithm requires at most N messages to
obtain the token to enter CR.
3. The synchronization delay in this algorithm is 0
or T. Zero synchronization delay, if the process
already holds the token.
Singhal’s Heuristic Algorithm
1. E = Executing and having the token
2. H = Holding the token and not executing
3. R = Requesting the token
4. N = Neutral, none of the above
Data Structures
Arrays Initialization
Performance Parameters
Performance Parameters
1. The number of REQUEST
messages can vary from N/2
(Average value of the identifier) to
N (max value).
Raymond’s Tree-Based Algorithm
Performance Parameters
The algorithm exchanges only O(log N) messages under light load
and four messages under heavy load
to execute the CR, where N is the number of nodes in the network.