DISTRIBUTED COMPUTING

UNIT – 3
1. Explain about Lamport Algorithm
Lamport’s Distributed Mutual Exclusion Algorithm is a permission based algorithm proposed by
Lamport as an illustration of his synchronization scheme for distributed systems. In permission based
timestamp is used to order critical section requests and to resolve any conflict between requests. In
Lamport’s Algorithm critical section requests are executed in the increasing order of timestamps i.e a
request with smaller timestamp will be given permission to execute critical section first than a request
with larger timestamp. In this algorithm:
 Three type of messages ( REQUEST, REPLY and RELEASE) are used and communication channels are
assumed to follow FIFO order.
 A site send a REQUEST message to all other site to get their permission to enter critical section.
 A site send a REPLY message to requesting site to give its permission to enter the critical section.
 A site send a RELEASE message to all other site upon exiting the critical section.
 Every site Si, keeps a queue to store critical section requests ordered by their
timestamps. request_queuei denotes the queue of site S i
 A timestamp is given to each critical section request using Lamport’s logical clock.
 Timestamp is used to determine priority of critical section requests. Smaller timestamp gets high
priority over larger timestamp. The execution of critical section request is always in the order of their
timestamp.
Algorithm:
 To enter Critical section:
 When a site Si wants to enter the critical section, it sends a request message Request(tsi,
i) to all other sites and places the request on request_queuei. Here, Tsi denotes the
timestamp of Site S i
 When a site Sj receives the request message REQUEST(tsi, i) from site Si, it returns a
timestamped REPLY message to site S i and places the request of site S i on request_queuej
 To execute the critical section:
 A site Si can enter the critical section if it has received the message with timestamp larger
than (tsi, i) from all other sites and its own request is at the top of request_queuei
 To release the critical section:
 When a site Si exits the critical section, it removes its own request from the top of its
request queue and sends a timestamped RELEASE message to all other sites
 When a site Sj receives the timestamped RELEASE message from site Si, it removes the
request of Si from its request queue
Message Complexity: Lamport’s Algorithm requires invocation of 3(N – 1) messages per critical section
execution. These 3(N – 1) messages involves
 (N – 1) request messages
 (N – 1) reply messages
 (N – 1) release messages
Drawbacks of Lamport’s Algorithm:
 Unreliable approach: failure of any one of the processes will halt the progress of entire system.
 High message complexity: Algorithm requires 3(N-1) messages per critical section invocation.
Performance:
 Synchronization delay is equal to maximum message transmission time
 It requires 3(N – 1) messages per CS execution.
 Algorithm can be optimized to 2(N – 1) messages by omitting the REPLY message in some situations.
Advantages of Lamport’s Algorithm for Mutual Exclusion in Distributed System:
1. Simplicity: Lamport’s algorithm is relatively easy to understand and implement compared to other
algorithms for mutual exclusion in distributed systems.
2. Fairness: The algorithm guarantees fairness by providing a total order of events that is used to
determine the next process that can enter the critical section.
3. Scalability: Lamport’s algorithm is scalable because it only requires each process to communicate with
its neighbors, rather than all other processes in the system.
4. Compatibility: The algorithm is compatible with a wide range of distributed systems and can be
adapted to different network topologies and communication protocols.
 DISTRIBUTED COMPUTING
UNIT – 3
Disadvantages of Lamport’s Algorithm for Mutual Exclusion in Distributed System:
1. Message Overhead: The algorithm requires a lot of message passing between processes to maintain
the total order of events, which can lead to increased network traffic and latency.
2. Delayed Execution: The algorithm can lead to delays in the execution of critical sections because a
process may have to wait for messages to arrive from other processes before entering the critical
section.
3. Limited Performance: The algorithm may not perform well in systems with a high number of
processes because of the increased message overhead and delayed execution.
4. No Fault Tolerance: The algorithm does not provide any fault tolerance mechanism, which means that
if a process fails or crashes, it may cause the entire system to fail or become unstable.

2 Mark FAQs:
How does Lamport’s algorithm ensure mutual exclusion in a distributed system?
Lamport’s algorithm uses a permission-based approach and timestamps to order critical section requests
and resolve any conflicts between them. Each process sends a request message to all other processes to
enter the critical section, and the request is placed in the request queue of each process in the order of its
timestamp. A process can enter the critical section if it has received a reply message from all other
processes with a timestamp greater than its own, and its own request is at the top of its request queue.
What is the message complexity of Lamport’s algorithm?
Lamport’s algorithm requires 3(N-1) messages per critical section execution, where N is the number of
processes in the system. These messages involve (N-1) request messages, (N-1) reply messages, and (N-1)
release messages.
Is Lamport’s algorithm fault-tolerant?
No, Lamport’s algorithm does not provide any fault tolerance mechanism. If a process fails or crashes, it
may cause the entire system to fail or become unstable.

1.Explain about Ricart Agarwala algorithm?

Ricart–Agrawala algorithm is an algorithm for mutual exclusion in a distributed system proposed by
Glenn Ricart and Ashok Agrawala. This algorithm is an extension and optimization of Lamport’s Distributed
Mutual Exclusion Algorithm. Like Lamport’s Algorithm, it also follows permission-based approach to
ensure mutual exclusion. In this algorithm:
 Two type of messages ( REQUEST and REPLY) are used and communication channels are assumed to
follow FIFO order.
 A site send a REQUEST message to all other site to get their permission to enter the critical section.
 A site send a REPLY message to another site to give its permission to enter the critical section.
 A timestamp is given to each critical section request using Lamport’s logical clock.
 Timestamp is used to determine priority of critical section requests. Smaller timestamp gets high
priority over larger timestamp. The execution of critical section request is always in the order of their
timestamp.
Algorithm:
 To enter Critical section:
 When a site Si wants to enter the critical section, it send a timestamped REQUEST message
to all other sites.
 When a site Sj receives a REQUEST message from site S i, It sends a REPLY message to site
Si if and only if
 Site Sj is neither requesting nor currently executing the critical section.
 In case Site Sj is requesting, the timestamp of Site S i‘s request is smaller than
its own request.
 To execute the critical section:
 Site Si enters the critical section if it has received the REPLY message from all other sites.
 To release the critical section:
 Upon exiting site Si sends REPLY message to all the deferred requests.
Message Complexity: Ricart–Agrawala algorithm requires invocation of 2(N – 1) messages per critical
section execution. These 2(N – 1) messages involves
 DISTRIBUTED COMPUTING
UNIT – 3
 (N – 1) request messages
 (N – 1) reply messages
Advantages of the Ricart-Agrawala Algorithm:
 Low message complexity: The algorithm has a low message complexity as it requires only (N-1)
messages to enter the critical section, where N is the total number of nodes in the system.
 Scalability: The algorithm is scalable and can be used in systems with a large number of nodes.
 Non-blocking: The algorithm is non-blocking, which means that a node can continue executing its
normal operations while waiting to enter the critical section.
Drawbacks of Ricart–Agrawala algorithm:
 Unreliable approach: failure of any one of node in the system can halt the progress of the system. In
this situation, the process will starve forever. The problem of failure of node can be solved by detecting
failure after some timeout.
Performance:
 Synchronization delay is equal to maximum message transmission time
 It requires 2(N – 1) messages per Critical section execution

2. Explain Distributed mutual exclusion algorithms.

Mutual exclusion is a concurrency control property which is introduced to prevent race conditions. It is
the requirement that a process can not enter its critical section while another concurrent process is
currently present or executing in its critical section i.e only one process is allowed to execute the critical
section at any given instance of time.
Mutual exclusion in single computer system Vs. distributed system: In single computer system,
memory and other resources are shared between different processes. The status of shared resources and
the status of users is easily available in the shared memory so with the help of shared variable (For
example: Semaphores) mutual exclusion problem can be easily solved. In Distributed systems, we neither
have shared memory nor a common physical clock and there for we cannot solve mutual exclusion problem
using shared variables. To eliminate the mutual exclusion problem in distributed system approach based
on message passing is used. A site in distributed system does not have complete information of state of the
system due to lack of shared memory and a common physical clock.
Requirements of Mutual exclusion Algorithm:
 No Deadlock: Two or more site should not endlessly wait for any message that will never arrive.
 No Starvation: Every site who wants to execute critical section should get an opportunity to execute it
in finite time. Any site should not wait indefinitely to execute critical section while other site are
repeatedly executing critical section
 Fairness: Each site should get a fair chance to execute critical section. Any request to execute critical
section must be executed in the order they are made i.e Critical section execution requests should be
executed in the order of their arrival in the system.
 Fault Tolerance: In case of failure, it should be able to recognize it by itself in order to continue
functioning without any disruption.
Solution to distributed mutual exclusion: As we know shared variables or a local kernel can not be used
to implement mutual exclusion in distributed systems. Message passing is a way to implement mutual
exclusion. Below are the three approaches based on message passing to implement mutual exclusion in
distributed systems:
1. Token Based Algorithm:
 A unique token is shared among all the sites.
 If a site possesses the unique token, it is allowed to enter its critical section
 This approach uses sequence number to order requests for the critical section.
 Each requests for critical section contains a sequence number. This sequence number is used to
distinguish old and current requests.
 This approach insures Mutual exclusion as the token is unique
Example : Suzuki–Kasami Algorithm
2. Non-token based approach:
 A site communicates with other sites in order to determine which sites should execute critical section
next. This requires exchange of two or more successive round of messages among sites.
 DISTRIBUTED COMPUTING
UNIT – 3
 This approach use timestamps instead of sequence number to order requests for the critica l section.
 When ever a site make request for critical section, it gets a timestamp. Timestamp is also used to
resolve any conflict between critical section requests.
 All algorithm which follows non-token based approach maintains a logical clock. Logical clocks get
updated according to Lamport’s scheme
Example : Ricart–Agrawala Algorithm
3. Quorum based approach:
 Instead of requesting permission to execute the critical section from all other sites, Each site requests
only a subset of sites which is called a quorum.
 Any two subsets of sites or Quorum contains a common site.
 This common site is responsible to ensure mutual exclusion
Example : Maekawa’s Algorithm