Distributed Operating Systems (Unit 3)

Synchronize 2 Clocks

Physical Time Services

• Broadcast Based - Server time is the main. It is broadcast and other systems follow this time.
• Simple Approach
  
  
  
  
• Berkeley Algorithm

  

  
  
• Request Driven
  

Clock Synchronization Algorithms

• Mean-time - The clocks are set to the mean-time of the initial representation of the clocks.
  
  
  
• Centralized Algorithms
• Cristian's
  
  
  
• Berkeley
  
  
  
• Decentralized Algorithms
• Averaging - Network Time Protocol
• Lamport Timestamps
  

  

  
  
• Multiple External Time Sources

Mutual Exclusion Algorithms

• Centralized
  
  
  
• Distributed
  
  
  
• Token Ring
  

Election Algorithm

• Bully Algorithm
1. Recogniser of no coordinator starts election.
2. A message is sent to all higher numbers.
3. No response makes them the coordinator.
   
   
   
• Ring Algorithm
1. The process which recognizes failure starts a stack of numbers and tells the next.
2. The next process which encounters this acknowledges by adding its number and passing.
   

Properties of Transactions

• Atomic - Indivisible
• Consistent - No violation of basic standards.
• Isolated - Do not interfere with each other.
• Durable - Changes are permanent.

Concurrency Control Algorithm

1. Locking
2. Two-Phase Locking
   
   
   
3. Optimistic Concurrency Control
4. Time Stamps
   

ATM