Question

In: Computer Science

Discuss how the Lamport’s algorithm achieves clock synchronization, using 4 clocks of different machines. Here, also...

Discuss how the Lamport’s algorithm achieves clock synchronization, using 4 clocks of
different machines. Here, also compute the time taken for synchronizing the clocks
(consider the clock with lowest time and compute the time with respect to this clock). Can
this algorithm be used in a real time system.

Solutions

Expert Solution

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 Si
  • 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 Si
    • When a site Sj receives the request message REQUEST(tsi, i) from site Si, it returns a timestamped REPLY message to site Si and places the request of site Si 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


Related Solutions

1. Sort the given keys using Counting sort algorithm. Also write the algorithm.          4, 1,...
1. Sort the given keys using Counting sort algorithm. Also write the algorithm.          4, 1, 0, 2, 1, 5, 0, 4                                                                     No code or programs, please. Manually solve the problem, please. Thanks
using Java, Implement the following algorithm: - Accept 5 different memory partitions and 4 different processes...
using Java, Implement the following algorithm: - Accept 5 different memory partitions and 4 different processes from user and show how best fit algorithm allocates them.
How can you generate a circle of center C and radius R using Bresenhem’s algorithm? Also,...
How can you generate a circle of center C and radius R using Bresenhem’s algorithm? Also, make flow chart for this algorithm. Write a C/C++ program to implement Bresenhem’s circle algorithm.
write an algorithm and python program using the following information. also can y How much should...
write an algorithm and python program using the following information. also can y How much should I study outside of class?                         Issue: Your fellow students need help. This is their first year in college and they need to determine how many hours they need to study to get good grades. Study Hours Per Week Per Class                    Grade 15                                                           A 12                                                           B 9                                                             C 6                                                             D 0                                                             F Project Specifications: The user enters their full name and the number...
Compare position of molecular ion peaks for (bromobenzene and 4-bromotoluene) how are they different/similar? Also, compare...
Compare position of molecular ion peaks for (bromobenzene and 4-bromotoluene) how are they different/similar? Also, compare the fragments that formed (how are they different and similar?)
how COVID-19 has affected the U.S economy. Also 4-5 charts with different economic measures that graphically...
how COVID-19 has affected the U.S economy. Also 4-5 charts with different economic measures that graphically represent the negative economic implications of the epidemic.
Discussion: How your company Vitamin Shoppe defines itself using support information to discuss this topic. Also,...
Discussion: How your company Vitamin Shoppe defines itself using support information to discuss this topic. Also, discussion on what the “guiding stars” are and how these work together with values/vision/mission. Discussion on how value is created as stated in the mission as well as some of the 9 components that may be included in a good mission was part of this session. Points should be brought forward on the progress gap (present state to future state) pertaining to the mission....
Discussion: How your company Vitamin Shoppe defines itself using support information to discuss this topic. Also,...
Discussion: How your company Vitamin Shoppe defines itself using support information to discuss this topic. Also, discussion on what the “guiding stars” are and how this works together with values/vision/mission. Discussion on how value is created as stated in the mission as well as some of the 9 components that may be included in a good mission was part of this session. Points should be brought forward on the progress gap (present state to future state) pertaining to the mission....
Provide comparison for liquid mixing expriments using different impellers and baffles and discuss how this affect...
Provide comparison for liquid mixing expriments using different impellers and baffles and discuss how this affect the liquid and the power curves and power requirements.
Question 4: How is the medical care market different from other markets? Discuss your answer by...
Question 4: How is the medical care market different from other markets? Discuss your answer by giving 4 likely reasons. Health care marketing: Refers to the use of marketing strategies for the purposes of protecting and improving population health the strategies including:
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT