DISTRIBUTED SYSTEMS

Course code: BCS 413 Credit Hours: 3

INSTRUCTOR
DENNIS REDEEMER
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 LECTURE 6

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]

Computer Science) -Computer Science, ReCAS
SYNCHRONISATION
AND
COORDINATION

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]

Computer Science) -Computer Science, ReCAS
 SYNCHRONISATION AND COORDINATION 1
• Distributed Algorithms
• Time and Clocks
• Global State
• Concurrency Control

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]

Computer Science) -Computer Science, ReCAS
 DISTRIBUTED ALGORITHMS
Algorithms that are intended to work in a distributed environment
Used to accomplish tasks such as:
• ➜ Communication
• ➜ Accessing resources
• ➜ Allocating resources
• ➜ Consensus
• ➜ etc.
Synchronisation and coordination inextricably linked to distributed
algorithms
• ➜ Achieved using distributed algorithms
• ➜ Required by distributed algorithms
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 SYNCHRONOUS Vs ASYNCHRONOUS
DISTRIBUTED SYSTEMS
Timing model of a distributed system
Affected by:
• ➜ Execution speed/time of processes
• ➜ Communication delay
• ➜ Clocks & clock drift
• ➜ (Partial) failure

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 SYNCHRONOUS Vs ASYNCHRONOUS
DISTRIBUTED SYSTEMS
Synchronous Distributed System:
Time variance is bounded
Execution : bounded execution speed and time
Communication : bounded transmission delay
Clocks : bounded clock drift (and differences in clocks)
Effect:
• ➜ Can rely on timeouts to detect failure
• Easier to design distributed algorithms
• Very restrictive requirements
• Limit concurrent processes per processor
• Limit concurrent use of network
• Require precise clocks and synchronisation
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 SYNCHRONOUS Vs ASYNCHRONOUS
DISTRIBUTED SYSTEMS
Asynchronous Distributed System:
Time variance is not bounded
Execution : different steps can have varying duration
Communication : transmission delays vary widely
Clocks : arbitrary clock drift

Effect:
• ➜Allows no assumption about time intervals
• Cannot rely on timeouts to detect failure
• Most asynch DS problems hard to solve
• Solution for asynch DS is also a solution for synch DS
• ➜ Most real distributed systems are hybrid synch and asynch
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 EVALUATING DISTRIBUTED ALGORITHMS
General Properties:
• ➜ Performance
• number of messages exchanged
• response/wait time
• Delay
• throughput: 1/(delay + executiontime)
• complexity: O()
• ➜ Efficiency
• resource usage: memory, CPU, etc.
• ➜ Scalability
• ➜ Reliability
• number of points of failure (low is good)
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 SYNCRONISATION AND COORDINATION
Important :
Doing the right thing at the right time.
Two fundamental issues:
• ➜ Coordination (the right thing)
• ➜ Synchronisation (the right time)

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 SYNCRONISATION
Ordering of all actions
• ➜ Total ordering of events
• ➜ Total ordering of instructions
• ➜ Total ordering of communication
• ➜ Ordering of access to resources
• ➜ Requires some concept of time

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 COORDINATION
Coordinate actions and agree on values.
Coordinate Actions:
• ➜ What actions will occur
• ➜ Who will perform actions
Agree on Values:
• ➜ Agree on global value
• ➜ Agree on environment
• ➜ Agree on state

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 MAIN ISSUES
• Time and Clocks:
synchronizing clocks and using time in distributed algorithms
• Global State:
how to acquire knowledge of the system’s global state
• Concurrency Control:
coordinating concurrent access to resources

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 TIME AND CLOCKS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]

Computer Science) -Computer Science, ReCAS
 TIME
Global Time:
• ➜ ‘Absolute’ time
• Einstein says no absolute time
• Absolute enough for our purposes
• ➜ Astronomical time
• Based on earth’s rotation
• Not stable
• ➜ International Atomic Time (IAT)
• Based on oscillations of Cesium-133
• ➜ Coordinated Universal Time (UTC)
• Leap seconds
• Signals broadcast over the world
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 TIME
Local Time:
• ➜ Not synchronised to Global source
➜ Relative not ’absolute’

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 PHYSICAL CLOCKS
Synchronisation Using Physical Clocks:
Examples
• ➜ Performing events at an exact time (turn lights on/off,lock/unlock gates)
• ➜ Logging of events (for security, for profiling, for debugging)
• ➜ Tracking (tracking a moving object with separate cameras)
• ➜ Make (edit on one computer build on another)

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 PHYSICAL CLOCKS
Based on actual time
• ➜ Cp(t): current time (at UTC time t) on machine p
• ➜ Ideally Cp(t) = t
Clock differences causes clocks to drift
• ➜ Must regularly synchronise with UTC

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 BERKELEY ALGORITHM

Accuracy: 20-25 milliseconds

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CRISTIAN’S ALGOIRTHM
Time Server:
• ➜ Has UTC receiver
• ➜ Passive
Time Server:
• ➜ Clients periodically request the time
• ➜ Don’t set time backward
• ➜ Take propagation and interrupt handling delay into account
• (T 1 − T 0)/2
• Or take a series of measurements and average the delay
• ➜ Accuracy: 1-10 millisec (RTT in LAN)

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 NETWORK TIME PROTOCOL(NTP)
Hierarchy of Servers:
• ➜ Primary Server: has UTC clock
• ➜ Secondary Server: connected to primary
• ➜ etc

Synchronisation Modes:

Multicast: for LAN, low accuracy

Procedure Call: clients poll, reasonable accuracy
Symmetric: Between peer servers. highest accuracy

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 NETWORK TIME PROTOCOL(NTP)
Synchronisation :
• ➜ Estimate clock offsets and transmission delays between two
nodes
• ➜ Keep estimates for past communication
• ➜ Choose offset estimate for lowest transmission delay
• ➜ Also determine unreliable servers
• ➜ Accuracy 1 - 50 msec

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 LOGICAL CLOCKS
Event ordering is more important than physical time:
• ➜ Events (e.g., state changes) in a single process are ordered
• ➜ Processes need to agree on ordering of causally related events
(e.g., message send and receive)
Local ordering:
• ➜ System consists of N processes pi, i ∈ {1, . . . , N}
• ➜ Local event ordering →i:
If pi observes e before e′, we have e →i e′
Global ordering:
• ➜ Leslie Lamport’s happened before relation →
• ➜ Smallest relation, such that
1. e →i e′ implies e → e′
2. For every message m, send(m) → receive(m)
3. Transitivity: e → e′ and e′ → e′′ implies e → e′′
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 LOGICAL CLOCKS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 LOGICAL CLOCKS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 LOGICAL CLOCKS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 VECTOR CLOCKS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 VECTOR CLOCKS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 VECTOR CLOCKS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 GLOBAL STATE

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]

Computer Science) -Computer Science, ReCAS
 GLOBAL STATE
How do peers keep track of all other peers?
• ➜ Distributed garbage collection:
Do any references exist to a given object?
• ➜ Distributed deadlock detection:
Do processes wait in a cycle for each other?
• ➜ Distributed termination detection:
Did a set of processes cease all activity? (Consider messages in
transit!)

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CONSISTENT CUTS
Determining global properties:
• ➜ We need to combine information from multiple nodes
• ➜ Without global time, how do we know whether collected
local information is consistent?
• ➜ Local state sampled at arbitrary points in time surely is
not consistent
• ➜ We need a criterion for what constitutes a globally
consistent collection of local information

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CONSISTENT CUTS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CONSISTENT CUTS

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CHANDY & LAMPORT’S SNAPSHOTS
• ➜ Determines a consistent global state
• ➜ Takes care of messages that are in transit
• ➜ Useful for evaluating stable global properties
Properties:
• ➜ Reliable communication and failure-free processes
• ➜ Point-to-point message delivery is ordered
• ➜ Process/channel graph must be strongly connected
• ➜ On termination,
• processes hold only their local state components and
• a set of messages that were in transit during the snapshot.
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CHANDY & LAMPORT’S SNAPSHOTS
Outline of the algorithm:
• ➀ One process initiates the algorithm by
• recording its local state and
• sending a marker message over each outgoing channel
• ➁ On receipt of a marker message over incoming channel c,
• if local state not yet saved, save local state and send marker messages, or
• if local state already saved, channel snapshot for c is complete
• ➂ Local contribution complete after markers received on all incoming channels
Result for each process:
• ➜ One local state snapshot
• ➜ For each incoming channel, a set of messages received after performing the
local snapshot and before the marker came down that channel
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CONCURRENCY

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]

Computer Science) -Computer Science, ReCAS
 CONCURRENCY
Concurrency in a Non-Distributed System:
Typical OS and multithreaded programming problems
• ➜ Prevent race conditions
• ➜ Critical sections
• ➜ Mutual exclusion
• Locks
• Semaphores
• Monitors
• ➜ Must apply mechanisms correctly
• Deadlock
• Starvation
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 CONCURRENCY
Concurrency in a Distributed System:
Distributed System introduces more challenges
• ➜ No directly shared resources (e.g., memory)
• ➜ No global state
• ➜ No global clock
• ➜ No centralized algorithms
• ➜ More concurrency

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 DISTRIBUTION MUTUAL EXCLUSION
• ➜ Concurrent access to distributed resources
• ➜ Must prevent race conditions during critical regions
Requirements:
• ➀ Safety: At most one process may execute the critical section at
a time
• ➁ Liveness: Requests to enter and exit the critical section
eventually succeed
• ➂ Ordering: Requests are processed in happened-before ordering

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 EVALUATING DISTRIBUTED ALGORITHMS

Properties:
➜ Multicast leads to increasing overhead (more sophisticated algorithm using
only subsets of peer processes exists)
➜ Susceptible to faults

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
 EVALUATING DISTRIBUTED ALGORITHMS
General Properties:
• ➜ Performance
• number of messages exchanged
• response/wait time
• Delay
• throughput: 1/(delay + executiontime)
• complexity: O()
• ➜ Efficiency
• resource usage: memory, CPU, etc.
• ➜ Scalability
• ➜ Reliability
• number of points of failure (low is good)
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
MUTUAL EXCLUSION:A COMPARISON

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate] Computer Science) -
Computer Science, ReCAS
THANK YOU VERY
MUCH

Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]

Computer Science) -Computer Science, ReCAS
Korda Dennis Redeemer (BSc., MPhil., & PhD [Candidate]
Computer Science) -Computer Science, ReCAS