Chapter 4:
Distributed Sorting Algorithms
DR . N OUF A LT MAM I
A S S ISTANT P ROF ESSOR AT COM P U T E R S CI E NCE DE PA RTMENT
COL L EG E OF COM P U T I NG A N D I N FOR M ATION T ECHN OLOGY
csc 505- Parallel and Distributed Computing 1
Introduction
A distributed system is a collection of processes that are separated in space and which
can communicate with each other only by exchanging messages this could be processed
on separate computers or it could even be multiple processes within the same
computer.
A defining characteristic is that the delay of transmitting a message is not negligible
compared to the time between events in a single process.
2
Introduction (cont.)
There is a fundamental limitation when it comes to ordering events in a distributed
system and that is sometimes it is simply not possible to tell if one event occurred
before another one if you take the complete set of events within a distributed system.
In a distributed system we cannot count on physical clocks even if the computers
themselves have physical clocks, because two clocks on two different systems can never
be perfectly synchronized they will always, in reality, be some drift between any two
physical clocks.
3
Computer clocks and timing events
Each computer in a DS has its own internal clock used by local processes to obtain the
value of the current time
– processes on different computers can timestamp their events
– but clocks on different computers may give different times
– computer clocks drift from perfect time and their drift rates differ from one
another.
– clock drift rate: the relative amount that a computer clock differs from a perfect
clock
Even if clocks on all computers in a DS are set to the same time, their clocks will
eventually vary quite significantly unless corrections are applied
4
Clocks, events and process states
How to order the events that occur at a single processor?
A distributed system is defined as a collection P of N processes pi, i = 1,2,… N
Each process pi has a state si consisting of its variables (which it transforms as it executes)
Processes communicate only by messages (via a network)
Actions of processes:
Send, Receive, change own state (changing the value of some variable i.e. data)
5
Clocks, events and process states (cont.)
Event: the occurrence of a single action that a process carries out as it executes e.g. Send,
Receive, change state
Events at a single process pi, can be placed in a total ordering denoted by the relation →i
between the events. i.e. e →i e’ if and only if the event e occurs before e’ at pi
A history of process pi : is a series of events ordered by →i
history(pi)= hi =< ei0, ei1, ei2>
6
Clocks
How to timestamp the events that occur at a single processor?
How to assign to them a date and time of day
To timestamp events, use the computer’s clock
Successive events will correspond to different timestamps only
if the clock resolution < time interval between successive events
Clock resolution: the period between updates of the clock value
7
Skew between computer clocks in a distributed
system
Computer clocks are not generally in perfect agreement
Skew: the difference between the times on two clocks (at any instant)
Computer clocks are subject to clock drift (they count time at different rates)
Clock drift rate: the difference per unit of time from some ideal reference clock
8
Universal Time Coordination (UTC)
International Atomic Time is based on very accurate physical clocks (drift rate 10-13)
UTC is an international standard for time keeping
It is broadcast from radio stations on land and satellite (e.g. GPS)
Computers with receivers can synchronize their clocks with these timing signals
Signals from land-based stations are accurate to about 0.1-10 millisecond
Signals from GPS are accurate to about 1 microsecond
9
Synchronization in Distributed Systems
In the distributed system, the hardware and software components communicate and
coordinate their actions by message passing.
Each node in distributed systems can share its resources with other nodes.
So, there is a need for proper allocation of resources to preserve the state of resources and
help coordinate between the several processes.
To resolve such conflicts, synchronization is used.
10
Synchronization in Distributed Systems (cont.)
Synchronization in distributed systems is achieved via clocks.
The physical clocks are used to adjust the time of nodes.
Each node in the system can share its local time with other nodes in the system.
The time is set based on UTC (Universal Time Coordination).
UTC is used as a reference time clock for the nodes in the system.
11
Synchronization in Distributed Systems (cont.)
Clock synchronization can be achieved by 2 ways: External and Internal Clock Synchronization.
External clock synchronization:
is the one in which an external reference clock is present. It is used as a reference and the nodes
in the system can set and adjust their time accordingly.
Internal clock synchronization:
is the one in which each node shares its time with other nodes and all the nodes set and adjust
their times accordingly.
12
Synchronization in Distributed Systems (cont.)
There are 2 types of clock synchronization algorithms: Centralized and Distributed.
1- Centralized is the one in which a time server is used as a reference. The single time-server
propagates it’s time to the nodes, and all the nodes adjust the time accordingly. It is dependent
on a single time-server, so if that node fails, the whole system will lose synchronization.
Centralized clock synchronization algorithms suffer from two major drawbacks:
•They are subject to a single-point failure. If the time-server node fails, the clock synchronization
operation cannot be performed.
•From a scalability point of view, it is generally not acceptable to get all the time requests serviced by a
single-time server.
13
Synchronization in Distributed Systems (cont.)
2- Distributed is the one in which there is no centralized time-server present. Instead, the nodes
adjust their time by using their local time and then, taking the average of the differences in time
with other nodes. Distributed algorithms overcome the issue of centralized algorithms like
scalability and single point failure.
14
Logical Clock in Distributed System
Logical Clocks refer to implementing a protocol on all machines within your distributed
system, so that the machines are able to maintain consistent ordering of events within
some virtual timespan.
A logical clock is a mechanism for capturing chronological and causal relationships in a
distributed system.
15
Logical Clock in Distributed System (cont.)
Example: Suppose, we have more than 10 PCs in a distributed system and every PC is
doing it’s own work but then how we make them work together. There comes a
solution to this i.e. LOGICAL CLOCK.
Method-1:
To order events across process, try to sync clocks in one approach. This means that if one
PC has a time 2:00 pm then every PC should have the same time which is quite not
possible. Not every clock can sync at one time. Then we can’t follow this method.
16
Logical Clock in Distributed System (cont.)
Method-2:
Another approach is to assign Timestamps to events. If we give each PC their individual
number than it will be organized in a way that 1st PC will complete its process first and
then second and so on.
BUT, Timestamps will only work as long as they obey causality.
17
What is causality ?
Causality is fully based on HAPPEN BEFORE RELATIONSHIP.
Taking single PC only: if 2 events A and B are occurring one by one then TS(A) < TS(B). If A has
timestamp of 1, then B should have timestamp more than 1, then only happen before
relationship occurs.
Taking 2 PCs and event A in P1 (PC.1) and event B in P2 (PC.2) then also the condition will be
TS(A) < TS(B).
Taking example- suppose you are sending message to someone at 2:00:00 pm, and the other
person is receiving it at 2:00:02 pm. Then it’s obvious that TS(sender) < TS(receiver).
18
Properties Derived from Happen Before Relationship
(causality)
Transitive Relation
If, TS(A) <TS(B) and TS(B) <TS(C), then TS(A) < TS(C)
Causally Ordered Relation
a->b, this means that a is occurring before b and if there is any changes in a it will surely reflect
on b.
Concurrent Event
This means that not every process occurs one by one, some processes are made to happen
simultaneously i.e., A || B.
19
Global States in a Distributed System
Initial Problem Example:
• Garbage Collector
Free’s up memory which is no longer in use
Check’s if a reference to memory still exists
• What about in a distributed system?
20
Initial Problem Example (cont.)
Each process can only determine its own “state”
Problem: How do we determine when to garbage collect in a distributed system?
How do we check whether a reference to memory still exists?
System Model
A distributed system consists of multiple processes
Each process is located on a different computer
Each process consists of “events”
An event is either sending a message, receiving a message, or changing the value of
some variable
Each process has a communication channel in and out
Garbage Collection Problem
In order to test whether a certain property of our system is true, we cannot just look at
each process individually
A “snapshot” of the entire system must be taken to test whether a certain property of
the system is true
This “snapshot” is called a Global State
The global state of a distributed system is the set of local states of each individual
processes involved in the system plus the state of the communication channels.
Computation
Deterministic Computation
At any point in computation there is at most one event that can happen next.
Non-Deterministic Computation
At any point in computation there can be more than one event that can
happen next.
Determinism
Deterministic computation
A local event would reveal everything about the global state!
The process will know other process’ state
Non-Deterministic computation
Because of branching, a local event cannot reveal what the next step will be
Simple Algorithm
Create a new process that collects the states of every other process
Every process will save their state at an arbitrary time and send it to this new process
Advantages:
Very simple
Easy to implement
Thank you
27