Distributed Synchronization and Mutual Exclusion Summary

Key Concepts in Distributed Synchronization and Mutual Exclusion

What is Time?

  • Global time is not available in distributed systems.
  • Synchronization can be based on physical time or logical time.

Physical Clock

  • Quartz crystal: Oscillates at a frequency, generates clock ticks.
  • Clock skew: Difference in time values across systems, can lead to issues.

Clocks in Distributed Systems

  • No shared memory or global clock; synchronization must be carefully managed.

Synchronization Methods

  • Physical Clock Synchronization:
    • TAI: International Atomic Time.
    • UTC: Universal Coordinated Time, can be received via several methods.
  • Centralized Algorithm: Cristian’s algorithm for clock synchronization.
  • Distributed Algorithm: Berkeley algorithm for multiple machines.

Cristian's Algorithm

  1. A machine requests time from a time server.
  2. Time server responds with current UTC.
  3. Machine adjusts its clock based on round-trip delay.
  4. Adjustments made based on whether the local clock is faster or slower.

Berkeley Algorithm

  • Time daemon collects clock values from all machines.
  • Daemon computes a mean time and instructs machines to adjust their clocks.

Logical Clocks

  • Introduced by Lamport, tracks the ordering of events in distributed systems.
  • Relation "happens before" denoted by ( a \rightarrow b ).
  • Key conditions:
    1. If in the same process, if event a occurs before b, then ( a \rightarrow b ).
    2. If a sends msg to b, then ( a \rightarrow b ).
    3. Transitivity: If ( a \rightarrow b ) and ( b \rightarrow c ), then ( a \rightarrow c ).

Conditions of Logical Clocks

  • Events must be recorded and incremented to maintain a logical order.
  • Sending and receiving messages must adhere to the logical time increment rules.

Total Ordering Relation

  • Events can be totally ordered using logical clock values.
  • Provides a framework to order events despite distributed nature.

Distributed Mutual Exclusion (ME)

  • Necessary for synchronized access to shared resources across distributed processes.
  • Unique challenges: No shared memory and no common clock.
    • Requirements of ME: Mutual Exclusion, Freedom from Deadlock/Starvation, Fairness, Fault Tolerance.
  • Centralized Solution: Queue requests; prone to bottlenecks and single points of failure.