# Synchronization

## Clock Synchronization

### Physical Clock Synchronization

• Christian's Algorithm: delay=(end-start)/2
• Berkeley Algorithm: repeat polling time for every machine and tell everyone the average

### Logical Clock Synchronization

• Lamport's Algorithm
• message carries a timestamp, new time = max(local time, timestamp)+1

## Global State and Election

• Global state = local state of each process + message in transit

### Distributed Snapshot Algorithm

• Organization of a process and channels for a distributed snapshot
• Process Q receives a marker for the first time and records its local state
• Q records all incoming message
• Q receives a marker for its incoming channel and finishes recording the state of the incoming channel

### Chandy-Lamport Snapshot Recording Algorithm

• Marker sending rule for process P
• P records its state.
• For each outgoing channel C on which a marker has not been sent, P sends a marker along C before P sends further message along C
• Marker receiving rule for P
• On receiving a marker along channel C.
• If P has not recorded its state then record the state of C as the empty set and execute the marker sending rule
• otherwise, record the state of C as the set of messages received along C after P's state was recorded and before P received the marker along C

### Election

Assumption

• Each process has a unique number
• One process per machine for simplicity
• Every process knows the process number of every other process
• Processes do not know which process are currently up or down

General Approach

• Locate the process with the highest process number and designate it as coordinator
• Election algorithms differ in the way they do the location

### The Bully Algorithm

• When a process P notices that the coordinator is not responding, it initiates a election
• sends a ELECTION message to all process with higher numbers
• If no one responds, P is the coordinator
• If one of the higher number answers, it takes over
• When a process get an ELECTION message
• receiver send OK message back to indicate that he is alive and will take over
• receiver holds an new election unless it is already holding one
• eventually, one will become the new coordinator, it sends a message to all others
• If a process comes back, it holds a new election

### Ring Algorithm

• Use a ring structure
• When a process notices that coordinator is not functioning, send an ELECTION message to its first alive successor.
• At each step, the sender add its own number to the list in the message
• When the message gets back to the starting process, set the coordinator to the highest number, and loop the message again.

## Sharing in Distributed Systems

### Centralized Algorithm

• Ask coordinator for permission to enter critical section
• Advantages
• guarantees mutual exclusion
• It is fair, no starvation
• easy to implement
• Disadvantages
• coordinator: single point failure, performance bottleneck

### Distributed Algorithm

• Based on total ordering of events
• When a process want to enter a critical section, it builds a message (section, process number, time), and sends to all other processes
• When a process receives a request message:
• If receiver is not in the section and does not want to enter it, sends OK
• If the receiver is in the section, it does not reply, and queues the request
• If it is not in the section but wants to enter, compare the timestamp
• Problems
• n points failure: if any process crashes, it will block all process to enter.
• slower, more complicated, more expensive, less robust

### Token Ring Algorithm

Token holder may enter critical section or pass the Token

• Advantages:
• guarantees mutual exclusion
• No starvation
• Disadvantages:
• hard to detect if the token is lost
• May circulate for hours but no one wants to enter critical section

## Transaction

Transaction is a collection of actions that make consistent transformations of system states while preserving system consistency

### ACID

• Atomicity
• All or nothing, multiple operations combined as an atomic transaction
• Consistency
• No violation of integrity constraints
• Transactions are correct programs
• Isolation
• Concurrent changes invisible (serializable)
• Durability
• Committed updates persist
• Database recovery

### Serializability

If several transactions are executed concurrently, the results must be the same as if they were executed serially in some order

### Distributed Transaction Serializability

• Each local history is serializable
• Two conflicting operation should be in the same relative order in all local histories

## Concurrent Control

### Locking-based algorithms

• Transaction request lock from lock manager
• read lock conflicts with write lock

### Two-phase Locking

• A transaction lock an object before using it
• When a transaction release a lock, it may not request another lock

### Strict Two-phase Locking

Hold all locks until the end

• Centralized 2PL: There is only one lock manager.
• Distributed 2PL: lock managers are at each, the lock manager is responsible for objects at that site

### Deadlock

• Wait-for Graph: U waist for V to release lock, U->V in WTG (local and global)
• Cycle in local WTG, local deadlock. Then check cycle involving external edges for global deadlock

• Prevention: guaranteeing that deadlocks can never occur (predeclare all)
• Avoidance: detecting potential deadlock in advance (order objects)
• Detection and recovery

### Timestamp Ordering

• each objet is assigned a write timestamp and read timestamp
• for read(x): if ts(T) < wts(x) then reject else accepts and rts(x) = ts(T)
• for write(x): if ts(T) < min(rts(x), wts(x)) then reject else accepts and wts(s) = ts(T)