Synchronization in Distributed Systems

Tom Kelliher, CS43

Apr. 9, 1996

Questions on the homework?

Clock Synchronization

Why bother?

• Timestamps on files.
• Basis for mutual exclusion algorithms.

The differences between non-distributed systems:

• Multiple crystals, individual drifts.
• Processes on different systems: different senses of time.

What is ``clock skew?''

Why not have a central time server?

• Single point of failure.
• Network congestion.
• Network latency. (Fixed with ``logical clocks.'')

Logical Clocks

Lamport.

Internally consistent set of clocks, no relationship to real time.

1. Total order vs. partial order.
2. Time doesn't matter --- order of events does.
3. Non-interacting processes don't need to synch.

Happens-before ( -->)

• if a and b are events in the same process and a occurs before b, then a --> b is true.
• if a is the event of a message being sent by one process and b is the event of the message being received by another process, then a --> b is true.

Physical Clocks

Externally consistent clock.

• International Atomic Time (TAI).
• Universal Coordinated Time (UTC) and leap seconds.
• See xntpd(8) and referenced RFCs.

Physical Clock Synchronization Algorithms

A centralized algorithm:

1. Query time server.
2. Set clock, adjusting for message delay.

A decentralized algorithm:

1. Once an epoch, broadcast your current time
2. Collect times from other broadcasts.
3. Discard outliers, set time to average.

Clock Based Cache Consistency

Read, write caching in a distributed file system.

Leases.

Mutual Exclusion

Centralized Approach

Mutual exclusion coordinator process.

Network saturation, fault tolerance.

Number of messages required in entering critical region.

Distributed Approach

• Send out a broadcast/multicast message containing:
  1. Critical region name.
  2. Process number.
  3. Current time.
  Every message should be acknowledged. (At this layer!!)
• On message receipt:
  1. If no intention of entering critical region, send back ``OK.''
  2. If in critical region, don't reply; queue request and send ``OK'' on exit.
  3. Otherwise, use timestamp to determine priority and act accordingly.

• Numerous processes attempting to enter a critical region?
• Importance of time synchronization?

Fault tolerance.

Number of messages required in entering critical region.

Election Algorithms

Coordinator should be ``highest numbered'' process.

No knowledge of who's crashed, who's working.

Bully Algorithm

When a process notices a coordinator is down:

1. Send election message to higher numbered processes.
2. If no response, you're the coordinator.
3. If a ``higher up'' responds, you're finished.

On receipt of an election message:

1. If sender is lower numbered, send OK and start an election.

Whoever wins sends a coordinator message to all lower numbered processes.

Number of messages?

Ring Algorithm

Processes connected in a logical ring.

When a process notices a coordinator is down:

1. Send election message an ``up'' list to next live process.
2. Each process adds its number to list and passes list.
3. Originator, upon receipt, converts list to coordinator message.

Number of messages?

How are processes added, removed from ring?

Atomic Transactions

Higher-level abstraction.

May consist of several events, either:

• All occur.
• None occur.

Examples:

• Transferring money.
• Booking airline tickets.

Stable Storage

Mirrored disks.

Algorithm:

1. Update master disk.
2. Update slave disk.

Block mismatch after a crash?

Bad Block?

Fault tolerance?

Transaction Primitives

• BeginTransaction.
• EndTransaction.
• AbortTransaction.
• Read --- Example of a transaction event.
• Write --- Ditto.

Properties:

• Atomic.
• Consistent --- No invariants violated.
• Isolated --- Synchronization.
• Durable --- Permanent.

Nested transactions --- May have to back out of child if parent aborts. How?

Implementation

Private Workspace

How are files handled?

Writeahead Log

Log event, before performing it.

Rollback for aborts.

Use log to recover from crashes.

Two-Phase Commit Protocol

Extremely useful for distributed transactions.

1. Coordinator writes, sends prepare message.
2. Subordinates write, send ready message.
3. Coordinator collects replies, decides what to do.
4. Coordinator writes, sends commit/abort message.
5. Subordinates write, perform commit/abort, send finished message.

Two-Phase Locking

1. Growing phase --- Acquire.
2. Shrinking phase --- Release.

Strict two-phase locking: shrinking only occurs after commit/abort. Prevents cascaded transaction aborts.

Deadlocks

Not much work done here. Opportunities to become famous!!