CHAPTER 6 : COORDINATION
Subtopic
6.1 Clock Synchronization
6.2 Logical clock
6.3 Mutual Exclusion
6.4 Elections Algorithms
6.5 Location systems
6.1 Clock Synchronization
Two types of Clock Synchronization :
• In a centralized system: all processes reside on
the same system utilize the same clock.
• In a distributed system: like synchronize
everyone’s watch in the classroom.
Global Time
• Global Time is utilized to provide timestamps
for processes and data.
• ü Physical clock: concerned with “People”
time
• ü Logical clock: concerned with relative
time and maintain logical consistency
Physical Clocks
• There are two aspects:
Obtaining an accurate value for physical time
Synchronizing the concept of physical time throughout the
distributed system
These can be implemented using centralized algorithms or
distributed algorithms
• AObtaining
physical timean Accurate
server is neededPhysical
to access Time
the
current time from a universal time coordinator (UTC).
• Two sources for UTC:
WWV shortwave radio station in Ft. Collins, Colorado
Geostationary Operational Environmental Satellites
(GEOS)
Synchronizing Physical Time
• The difference in time between two clocks due
to drifting is defined as clock skew. As long as
any and every two clocks differ by a value less
than the maximum skew value, the time
service is considered to be maintaining
synchronization.
•How to synchronize
The information two
necessary to clocks
read thein A and
value mustB?
be
communicated across the network to location B.
• B’s clock value must be read.
• B’s clock value is communicated back to location A.
• B’s clock value is adjusted to reflect the time
necessary to travel across the network.
• B’s clock value is compared to A’s clock value.
Centralized Physical Time Services
• Broadcast Based
• Request Driven
Broadcast
• The centralized timeBased
server’s–action:
first approach
The physical time service broadcasts periodically the current time to members
of the distributed systems.
• The participants’ action:
If a given participant’s clock is ahead of the time server’s clock, the participant
slows down its clock so that it will continually move closer to the accurate time.
If a participant’s clock is behind the time server’s clock, the participant moves
its clock forward. Alternatives do include gradually speeding up the clock.
For example
Location A Time server
Current time Current time=740
= 720 Broadcast based
Delay of 10
Location A
Current time=720
Adjusted current time=750
New current time=750
Request Driven
Location A Timer Server
Current time=730
Request for Current time=740
current time
Current time=740
Adjusted time=750 Delay=10
New current time=750
• Each Distributed Physical Time Service
location broadcasts its current time at predefined set
intervals. Once a location has broadcast its time, it starts a
timer. It then collects time messages that it receives. Each
time message that arrives is stamped with the local current
time. This process continues until the timer expires. Upon the
expiration of the timer, each message is adjusted to reflect
the network delay time estimated for the message source. At
this stage, the participant calculates the average time
according to one of the following approaches:
6.2
•
Logical Clocks
Why Logical Clocks?
It is difficult to utilize physical clocks to order
events uniquely in distributed systems.
• The essence of logical clocks is based on the
happened-before relationship presented by
Lamport.
(Leslie B. Lamport (born February 7, 1941 in Brooklyn) is an American computer scientist and
mathematician)
Happen-Before
• If two events, Relationship
a and b, occurred at the same process,
they occurred in the order of which they were observed.
That is, a > b.
• If a sends a message to b, then a > b. That is, you cannot
receive something before it is sent. This relationship
holds regardless of where events a and b occur.
• The happen-before relationship is transitive. If a happens before b and b
happens before c, then a happens before c. That is, if a > b and b > c, then a > c.
• Logical Ordering
If T(a) is the timestamp for event a, the following relationships must hold in a
distributed system utilizing logical ordering.
• If two events, a and b, occurred at the same process,
they occurred in the order of which they were
observed. That is T(a) > T(b).
• If a sends a message to b, then T(a) > T(b).
• If a happens before b and b happens before c, T(a) >
T(b), T(b) > T(c), and T(a) > T(c).
6.3 Mutual Exclusion
• In single-processor systems, critical regions
are protected using semaphores, monitors,
and similar constructs.
• In distributed systems, since there is no shared
memory, these methods cannot be used.
A Centralized Algorithm
coordinator
process Request
Grant
Enter crical Release
section
Exit
• Advantages: It is fair, easy to implement, and requires only three messages
per use of a critical region (request, grant, release).
• Disadvantages: single point of failure.
Distributed Algorithm
OK OK
REQ REQ
REQ REQ
Token Ring Algorithm
In this algorithm it is assumed that all the processes in the system
are organized in a logical ring. The figure blow describes the
structure.
When a process sends a request message to current coordinator and does
not receive a reply within a fixed timeout, it assumes the coordinator has
crashed. It then initializes the ring and process P1 is given a token.
A Comparison of the Three Algorithms
Algorithm Messages per Delay before Problems
entry/exit entry
Centralized 3 2 Coordinator crash
Distributed 2(n-1) 2(n-1) Crash of any process
Token ring 1 to ∞ 0 to n-1 Lost token, process crash
6.4 Election Algorithm
• The bully algorithm
• When a process notices that the coordinator is no longer
responding to requests, it initiates an election. A process, P,
holds an election as follows:
P sends an ELECTION message to all processes with higher
numbers.
If no one responds, P wins the election and becomes
coordinator.
If one of the higher-ups answers, it takes over. P’s job is done.
For example
1 1 1
7 2 7 2 7 2
6 6 6 Election 3
Election 3 3
5 4 5 4 5 4
Ok
7 1 7 1
2 2
6 Ok 3 6 Coordinator
3
5 4 5 4
• A Ring Algorithm
234561
1 2 6
2
7
3 23
23456 6
5 4
2345 234
6.5onLocation
• Absolute position geoid
System
• Location relative to fixed beacons
• Location relative to a starting point
• Most applications:
– location relative to other people or objects, whether moving or
stationary, or the location within a building or an area
09/13/2025 CS691 25
Location Sensor Technologies
• Electromagnetic Trackers:
– High accuracy and resolution, expensive
• Optical Trackers:
– Robust, high accuracy and resolution, expensive and mechanical complex
• Radio Position Systems (Such as GPS):
– Successful in the wide area, but ineffective in buildings, only offer modest location
accuracy
• Video Image (Such as the MIT Smart Rooms project):
– Location information can be derived from analysis of video images, cheap hardware
but large computer processing
Some new technologies are developing
09/13/2025 CS691 26
• History
GPS
When: 1973 start, 1978-1994 test
Who & Why:
• U.S. Department of Defense wanted the military to have a super
precise form of worldwide positioning
• Missiles can hit enemy missile silos… but you need to know where you
are launching from
• US subs needed to know quickly where they were
• After $12B, the result was the GPS system!
09/13/2025 CS691 27
GPS
• Approach
– “man-made stars" as reference points to calculate
positions accurate to a matter of meters
– with advanced forms of GPS you can make
measurements to better than a centimeter
– it's like giving every square meter on the planet a
unique address!
09/13/2025 CS691 28
GPS System Architecture
09/13/2025 CS691 29
GPS System Architecture
• Constellation of 24 NAVSTAR
satellites made by Rockwell
– Altitude: 10,900 nautical
miles
– Weight: 1900 lbs (in orbit)
– Size:17 ft with solar panels
extended
– Orbital Period: 12 hours
– Orbital Plane: 55 degrees to
equitorial plane
09/13/2025 CS691 30
09/13/2025 CS691 31
GPS aka
• Ground Stations, System
“ControlArchitecture
Segment”
– The USAF monitor the GPS satellites, checking both their
operational health and their exact position in space
– the master ground station transmits corrections for the
satellite's ephemeris constants and clock offsets back to the
satellites themselves
• the satellites can then incorporate these updates in the signals they send
to GPS receivers.
– Five monitor stations
• Hawaii, Ascension Island, Diego Garcia, Kwajalein, and Colorado Springs.
09/13/2025 CS691 32
09/13/2025 CS691 33
GPS Signals in Detail
• Carriers
• Pseudo-random Codes
– two types of pseudo-random code
• the C/A (Coarse Acquisition) code
– it modulates the L1 carrier
– each satellite has a unique pseudo-random code
– the C/A code is the basis for civilian GPS use
CS691 34
GPS
• the Signalscode
P (Precise) in Detail (contd.)
– It repeats on a seven day cycle and modulates
both the L1 and L2 carriers at a 10MHz rate
– this code is intended for military users and can
be encrypted and called "Y"
• Navigation message
– a low frequency signal added to the L1 codes that gives
information about the satellite's orbits, their clock
corrections and other system status
35
09/13/2025 CS691 36
How GPS Works
1. The basis of GPS is “trilateration" from satellites. (popularly but
wrongly called “triangulation”)
2. To “trilaterate," a GPS receiver measures distance using the travel
time of radio signals.
3. To measure travel time, GPS needs very accurate timing which it
achieves with some tricks.
4. Along with distance, you need to know exactly where the satellites
are in space. High orbits and careful monitoring are the secret.
5. Finally you must correct for any delays the signal experiences as it
travels through the atmosphere.
09/13/2025 CS691 37
Earth-Centered Earth-Fixed X, Y, Z Coordinates
CS691 38
