Introduction
Dr. Joe Yuen
Department of Electrical and Electronic Engineering
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Outlines
• About this course
• What is a distributed system? • Characteristics – Transparency • User Requirements
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Coursework
• Continuous Assessment (20%) • Quiz (10%)
• Group project (10%)
• Written Examination (80%)
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Motivation
• Bring additional computing power to a system seamlessly
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Distributed System
A distributed system is defined as a collection of autonomous computers linked by a network with software designed to produce an integrated computing facility.
Coulouris et al. 1994
Tanenbaum 1995
A distributed system is a collection of independent computers that appear to the system as a single computer.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Distributed System
= Computers/Hosts + Communication Network + Transparencies
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Advantages of Distributed Systems
• Price/performance
• A cost-effective way to build larger system is to use a larger number of
cheap CPUs.
• Nature of some applications
• Some applications are inherently distributed (e.g. banking and supermarket chain).
• Reliability
• If one machine crashes, the system as a whole can still survive.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Advantages of Distributed Systems
• Incremental growth
• Computing power can be added in small increments.
• Data sharing
• It allows many users access to a common database;
• Device sharing
• It allows many users to share expensive peripherals;
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Advantages of Distributed Systems
• Communication
• It provides communication facilities;
• Flexibility
• It spreads the workload over the available machines in the most cost- effective way.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Characteristics
• Resource Sharing • Openness
• Concurrency
• Scalability
• Fault Tolerance • Transparency
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Resource Sharing
• What to share?
• Hardware devices • Data
• How to share?
• Resources are stored in workstations and can be accessed via
communications by a resource manager • Resource Manager
• A program that offers a communication interface enabling the resource to be accessed, manipulated and updated reliably and consistently.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Resource Manager
Provide resource name
Identify resource location
Coordinate concurrent access to ensure consistency
Map resource name to communication address
Resource
Locating
Mapping
Coordinating
Naming
Manager
Access
Concurrent
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Openness
• Characteristic that determines whether the system can be extended in various ways
• Hardware: Additional peripherals, memory or communication interfaces;
• Software: Additional operating system features, communication protocols and resource-sharing services.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Concurrency
• In a distributed system with M computers (cores) , up to M processes can be executed in parallel.
• Parallel executions occur for two reasons:
• More than one users simultaneously invoke commands or interact with
application programs
• Many server processes run concurrently, each responding to different requests from client processes.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Scalability
• DS can be existed in different scale:
• The smallest: 2 workstations + 1 file server
• Local area network (LAN): • hundreds workstations
• Several file servers
• Print servers
• Internetwork:
• Several LANS interconnected
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Fault Tolerance
• The design of fault-tolerant computer systems is based on:
• Hardware redundancy: the use of redundant components
• Software recovery: the design of programs to tolerate (process group) or recover from faults
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Transparency
• Hidden from the user (application) programmer of separation of components;
• Achieve a single system image to make everyone into thinking that the collection of machines is simply an old-fashioned time-sharing system.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Transparency
• Access transparency
• Enable local and remote information to be accessed using identical
operations.
• Location transparency
• Enable the information objects to be accessed without knowledge of their location (users need not tell where resources are located).
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Transparency
• Concurrency transparency
• Enable several processes to operate concurrently using shared information objects without interference (multiple users can share resources automatically).
• Replication transparency
• Enable multiple replicas to be used to increase reliability and performance without user knowledge of how many replicas exist.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Transparency
• Failure transparency
• Enable concealment of faults, allowing users to complete their tasks despite
the failure of hardware or software components. • Migration transparency
• Allow information objects move within a system without changing their name or affecting users.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Transparency
• Performance transparency
• Allow the system to be configured to improve performance as loads vary.
• Scaling transparency
• Allow the system and applications to expand in scale without change to the system structure or the application algorithms.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Transparency
• Parallelism transparency
• Allow the program to be executed in parallel without users knowledge.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
User Requirements
• Functionality
• Re-configurability • Quality of Service
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Functionality
A distributed system should bring an improvement over the services provided by any single computer through enhancements of:
• Sharing across a network can bring access to a richer variety of resources.
• Parallel and Fault-tolerant applications.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Functionality
How to migrate a multi-user centralized computing to distributed computing?
• Adapt existing operating systems
• Continue to use existing operating system software that has been adapted for
networking.
• e.g. add servers to UNIX or Sun Network File System.
• Move to an entirely new operating system designed specifically for distributed system.
• Existing software becomes unusable.
• Emulation
• Move to a new OS designed for DS which can emulate one or more existing OS. • Existing and new distribution software can run side-by-side.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Re-configurability
• Short-term
• A failed process, computer or network component is replaced by another,
working counterpart.
• Overload is shifted from over-loaded to less-loaded machines to increase the total throughput of the DS.
• To reduce network communications, data are moved from a machines to the others to make the data accessible.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Re-configurability
• Medium/long term evolution
• To accommodate heterogeneous components and assign new task or to upgrade the existing machines.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Quality of Service
• Performance
• Speed up the response of software components in a distributed system;
• Reliability and availability • Fault-tolerance;
• Security
• Apply a reasonable degree of security applied to the data stored and transmitted with a distributed system.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Basic Design Issues
• Naming
• Name resources or objects in order to access them.
• Communication
• Optimize the communication implementations in distributed systems while
retaining a high level programming model for its use.
• Software structure
• Define interface and good abstraction of data and services.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Basic Design Issues
• Workload allocation
• Deploy computers and communications to achieve optimum performance
and use of resources.
• Consistency maintenance
• How to balance consistency & performance?
• Security
• How to secure message transfer in a distributed system?
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Summary
• Distributed System = Collection of computers + Communication Network + Transparency
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Course Outline (tentative)
Week
Topics
1
Introduction
2
Message Passing (Inter Process Communication)
3
Time Synchronization
4
Distributed Coordination
5
Replication and Concurrency Control I
6
Replication and Concurrency Control II
7
Reading weeks
8
Quiz
9
Distributed File System
10
Distributed Programming
11
Project Presentation
12
Review
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Summary
Distributed System =
• Collection of computers + Communication Network + Transparencies
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
2. Inter-process Communication
Dr. Joe Yuen
Department of Electrical and Electronic Engineering
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Introduction
• Why we need Inter-process Communication (IPC)?
• The components of a distributed system are both logically and physically
separated
• They must communicate in order to interact.
P5
P1
P4
P3
P2
Host 1
Host 2
Host 3
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Communication Patterns
• Client-server communication
• request and reply messages provide the basis for communication between
clients and servers.
• Group communication
• some messages are sent to several processes in a group.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client Server Communication
• The idea of the model is to structure the distributed systems as a group of cooperating processes, i.e. the servers, that offer services to the users, namely, the clients.
Request message
Network
Reply message Client
Server
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Data Passing
• For any two computers to exchange data value, we need to map data structures and data items to messages.
• Data structure must be flattened before transmission and rebuilt on arrival. (I.e., flattening of structured data into a sequence of basic data)
• On receiving data stream, the data structure must be rebuilt.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Example: MMOG
Treasure_Hunter
Level: 3 HP: 5000 Item:
• Basic Sword x 2
• HealPack x 3
• PowerBooster x4
Deadline_Fighter
Level: 4
HP: 7500
Item:
• Basic Sword x 1 • DoorKeyx2
• Magic Power x 5
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Data Passing
• Marshalling
• the process of taking a collection of data items and assembling them into a
form suitable for transmission in a message; • Unmarshalling
• the process of disassembling them on arrival to produce an equivalent collection of data items at the destination;
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Example
• Convert the following array into a plan string Course Taken:
ELEC6006
ELEC6008
ELEC6069
ELEC7021
ELEC6603
ELEC7021
ELEC7079
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Data Passing
• Usually a language preprocessor (interface compiler) can be used to generate marshalling / unmarshalling operations automatically.
• When an IPC primitive is encountered involving data item of the above type, the preprocessor generates code to do the marshalling (for a send) or unmarshalling (for a receive) based on the type description.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
JSON (JavaScript Object Notation)
Variable in Swift
var id:Int = 12345678
var name:String = “John Peter”
var gpa:Float = 3.8
var taken = [3644,1330,1320,1851]
JSON
{
“id” : 12345678,
“name” : “Peter John”,
“gpa” : 3.7999999523162842,
“taken” : [
3644,
1330,
1320,
1851
] }
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronization
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronization
• A central issue in the communication structure;
• 2 types of operations
• Blocking: the invocation blocks the execution of its invoker.
• Non-blocking: the invocation does not block the execution of its invoker.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Blocking
• Blocking Send
• Issuing process blocks (i.e., control is not passed back) until the message
has been sent and received. • Blocking receive
• Issuing process blocks until a message has arrived and passed to the process.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronization: Blocking
Sender
Network
Receiver
Application
Kernel
Kernel
Application
Send Data
Receive
Data
Data
Blocking
Data
Msg Ready
Ack.
Send Ack.
Ack.
Next Instruction
Ack.
Ack. Received Ack.
Next Instruction
Blocking
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Time
Synchronization: Non-blocking
• Non-blocking send
• Issuing process continues (i.e. control is passed back) execution after the
message has been copied out of the process’s environment. • Non-blocking receive,
• Issuing process continues if there is no message waiting to be received. Receiver process will have to be notified later on message arrival, either by polling or interrupt mechanism.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronization: Non-blocking
Sender
Network
Receiver
Application
Kernel
Kernel
Application
Send Data
Receive
Next Instruction
Data
Next Instruction
Data
Notify
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Time
Synchronous vs. Asynchronous Communication
• Drawback: Can lead to inefficiency due to waiting • high overhead and less efficiency.
• Solution: time-out
• Receive (A, msg, TO);
• If a message is not arrived in TO seconds, the process will be unblocked (and the receive operation aborted).
• Send (B, msg, TO)
• Sender blocks and if the message is not received in TO seconds, the process will be unblocked.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronous vs. Asynchronous Communication
• Synchronous communication
• Blocking send and blocking receive;
• Sender and receiver synchronize at point of message transfer.
• Advantage:
• Can make definite assumptions on message send and receipt • Easy design and control of the distributed processes
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronous vs. Asynchronous Communication
• Asynchronous communication
• Sender and receiver do not synchronize at message transfer.
• Non-blocking send + non-blocking receive;
• Non-blocking send + blocking receive (usual combination);
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronous vs. Asynchronous Communication
• More flexible and potentially more parallelism;
• Less assumption can be said about sending and receiving – more
difficult to verify program properties.
• Non-blocking send requires buffering of messages.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Implementation
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Process Location
• A port is a location independent identifier which can be mapped into low-level address in order to deliver message.
• In TCP/IP, message destination addresses are Port number (used by the process) and Internet address of the computer (the process resides on),
• Send (portB, msg);
• Receive(portB, msg);
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
IP Address: 163.14.5.1
Send (portB, msg); Receive(portB, msg);
portB = IP:163.14.5.1, port number:80
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Unreliable vs. Reliable Messages
• Unreliable message is used to refer to a single message transmitted from sender to receiver, without acknowledgement or retries.
• e.g. UDP only makes its “best effort” to deliver a message.
• Reliable message delivery may be constructed from an unreliable one by using acknowledgement.
• Positive ack: receivers send ack message whenever a message is received.
• Negative ack: Receivers do not send ack message until something wrong (timeout
or receiving any incorrect message).
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
• Client-server model uses request-reply communication.
• Request-reply is normally synchronous because a client will wait for the
reply.
• Request-reply can be asynchronous in case that the client can afford to retrieve replies later.
• Question: how many system calls (Send and Receive) are required for two kinds of communications?
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
DoOperation .
.
.
. (wait)
.
.
.
. continuation
Request message
Reply message
GetRequest .
. Execute request
.
. SendReply
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
• Request-reply protocols
• PROCEDURE DoOperation (serverPort: PortId; request: Message
VAR reply: Message)
• send a request message, request to server at port serverPort and receives the reply message.
• PROCEDURE GetRequest (serverPort: PortId; reply: Message) • get a client request, request via server port serverPort.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
• PROCEDURE SendReply (clientPort: PortId; reply: Message) • send a reply message, reply to client at its port clientPort.
• Request-reply message structure
• Generated by DoOperation in the client
• Used to check against the reply message
• Server procedure identity
• Map to request operation
Fields
Type
Message Type
Request, Reply
RequestID
Cardinal
ProcedureID
Cardinal
Arguments
Flattened List
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
• Communication failures
• Loss of request message: communication link fails / network switch fails /
receiver’s node is down.
• Loss of reply message: communication link fails / network switch fails / sender’s node is down.
• Unsuccessful execution of the request: server crashes while executing the request.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
• In the presence of communication failures three protocols are used for implementing various type of client-server communication.
• The request (R) protocol
• Client issues a Send (server-id, request) and continues. It is suitable for cases in which there is no reply required from the server and that the client requires no confirmation that the request has been carried out.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
R
Client
Server
Request
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
• The request-reply (RR) protocol
• Most commonly used;
• The reply message from the server also acts as acknowledgment to the original request message.
• A subsequent request from the client may be regarded as an acknowledgment of the server’s message.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
Client
Server
Request
RR
Blocking state
Reply
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
• The request-reply-acknowledge reply (RRA) protocol
• An acknowledgement will be sent back to the server after received the
reply
• The ack includes the request-Id and acknowledges all request messages up to that request-Id.
• Although the exchange involves an additional message, it need not block the client as the acknowledgement may be transmitted after the reply has been given to the client, but it does use processing and network resources.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Client-Server Communication Protocol
Client
Server
RRA
Blocking state
Request
Reply Ack
Blocking state
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Other Issues
• Time-out
• occur when a request message is lost or the network becomes partitioned,
or the server is overloaded (and hence slow); or the reply message is lost.
• DoOperation repeats sending the request message N times (time-outs) before reporting failure.
• It is impossible to distinguish between a process failure and a communication failure. When process does not reply after some agreed number, N of attempts to communicate with it, it is assumed to be unavailable.
• The choice of N is difficult (?).
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Other Issues
• Duplicated request messages
• Occur when request message is retransmitted (on time-outs).
• Duplicates can be detected using Request-Id (like a sequence number) and discarded.
• Lost reply messages
• If the server has already sent the reply message, it may need to execute the request again to obtain the result. Re-executing is only possible for idempotent operation.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Other Issues
• An idempotent operation is an operation that can be performed repeatedly with the same effect as if it had been performed exactly once.
• If server operation is not idempotent a record of past results (called history) can be kept. History can be kept from growing too large by using the RAA protocol, or discarding results which have passed a certain time limit.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Other Issues
• Multipacket messages
• Datagram with limited length (often as 8 kbytes).
• Not enough if a request or reply is too large.
• Solution multipacket: a message made up of a sequence of datagrams.
• Drawbacks: complicated in design and control (receive in sequence), low efficiency in retransmission.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Summary
• Data Passing :
• Data structure must be flattened before transmission
• Data format must be well-defined before communication • Marshalling, Unmarshalling
• Communication
• Blocking vs. Non-blocking
• Synchronous vs. Asynchronous Communication
• Process Location
• Unreliable vs. Reliable message • R, RR, RRA Protocol
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
3. Time in Distributed Systems
Dr. Joe Yuen
Department of Electrical and Electronic Engineering
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Introduction
• Time is an important and interesting issue in distributed systems because
• Internal (computer-to-computer) and external (computer-to-external) synchronization;
• Many algorithms depend upon clock synchronization, e.g. transaction.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• Physical clocks
• Electronic devices that count oscillations occurring in a crystal at a
definite frequency.
• It is useful for keeping accurate time and time-stamping events, e.g., time in accounting records of connection.
• Event is an action that appears to occur indivisibly.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• Sources of accurate timing signals: coordinated universal time (UTC) • Radio broadcast accuracy: 0.1 – 10 ms
• Satellite (Geostationary Operational Environment Satellite GOES) accuracy: 1 ms
• Satellite (Global Positional System GPS) accuracy: 0.1 ms
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• Difficulties in distributed systems
• Not all sites have direct access to accurate time sources such as GPS
receivers.
• Sites have to synchronize their local clocks with those have more accurate time.
• Synchronization needs to be done periodically due to clock drift: they count time at different rates, and so diverge.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• Cristian’s method
• A central time server process S supplies the time according to its clock upon
request.
Request
Mr
Process P
Time Server S
Mt
Time
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
Clock=t+Ttrans
Request
Time Server S
Process P
WAN
Request
Mt
Time t
Ttrans
min
Time t
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• If a process P requests the time in a message mr, and receives the time value t in a message mt, then it could set its clock to the time t + Ttrans, where Ttrans is the time taken to transmit mt from the server S to P.
• Ttrans can be variant. We may say, Ttrans = min + x, where x = 0 and min is the time of message transmission if no other processes and no other messages.
• min can be measured or conservatively estimated but x is still unknown!
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
Min
Min
Request
Tround/2 Tround
Mt
t
Tround
Time t
Clock=t+Tround/2
Min
x
Min
y
Request
Mt
t
Time t
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
Tround
Min
x
Min
Mt
Time t
Min
Min
y
Time t
Clockmin
Request
t
Clockmax
Request
Mt
t
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• Let Tround be the total round trip time to send the request mr and receive the reply mt, then P should estimate its clock as t + Tround / 2 (Tround can be measured or conservatively estimated ).
• Let the time between sending and receipt for mr and mt be min + x and min + y respectively, then t lies in the range [t + min, t + Tround – min].
• The accuracy is ±(Tround / 2 – min).
• Problem: single-server failure.
• Solution: group synchronization time server.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
P1
t1
Time=?
t2 t3
t4t5
t6
Time Server
Time=x
Time=y
Time=?
Time=?
Time=z
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• The Berkeley algorithm
• An algorithm for internal synchronization in BSD UNIX.
• (Unlike Cristian’s) In a group sites, one is chosen as coordinator (master). It periodically polls the other sites (slaves) to synchronize their clocks.
• Master estimates the slaves’ clock times by observing round trip time (like Cristian’s). It averages the time obtained (including its own).
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• The average (with probabilities) can cancel out individual clock’s run fast or slow.
• Accuracy depends on round-trip time between master and slaves.
• Master sends time rate adjust value (+ or -) to slaves, requesting
them to adjust their time rates.
• Master takes fault-tolerant average.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
Time server
3. +/-
2. Time =z
1. Time?
3. +/-
2. Time =x
1. Time?
3. +/-
1. Time?
P1
2. Time =y
P2
P3
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• Network Time Protocol (NTP)
• A standard for clock synchronization throughout the Internet
• Design aims and features
• To provide a service enabling clients across the Internet to be synchronized accurately
to UTC;
• Employs statistical techniques for the filtering of timing data and it discriminates between the quality of timing data from different servers
• To provide a reliable service to losses of connectivity; • Redundant servers and paths
• To enable clients to resynchronize sufficiently frequently; • Scale to large numbers of client and servers
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
Radio clock
1
22
accurate
Stratum 1
Stratum 2
Less accurate
333
Stratum 3
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• NTP server synchronize – UDP
• Multicast mode • high speed LAN
• Multicast periodically • Procedure call mode
• Similar to the operation of Cristian’s algorithm • More accurate than multicast mode
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• NTP server synchronize – UDP
• Symmetric mode
• For servers that supply time information in LANs
• Synchronize with higher level NTP server
• A pair of servers exchange messages bearing timing information and the timing data are retained as part of an association between servers to improve the accuracy
• Each message bears timestamps of recent message events
• Local times when the previous NTP message between the pair was sent
• Local times when the previous NTP message between the pair was received
• Local time when the current message was transmitted
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
– Ti-2 = Ti-3 + t + o
– Ti = Ti-1 + t’ – o
– di = t + t’
– o = oi + ( t’ – t )/2 // oi=(Ti-1 – Ti + Ti-2-Ti-3)/2
oi:Actual offset between 2 clocks
di:total transmission time for the two messages o:true offset of the clock at B related to A
t, t’ : transmission times for M and M’
Ti-2
Ti-1
Server A
Server B
M
M’
Ti
Ti-3
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Synchronizing Physical Clocks
• No guarantee (bounded) on the difference between two clocks. • This is a “best-effort” service.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Casual Ordering (Happens-before)
• Causal ordering •x
Non-initator
receive
send
Non-initator
receive
send
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Ring Algorithm
• Initiator:
• Begin
• send
• Receive
• End
• Non-initiators
• Begin
• Receive
• Send
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Tree Algorithm
• All leaves of the tree initiate the algorithm
• Each process sends exactly one message in the algorithm
• If a process has received a message via each of its incident channels except one, the process sends a message via the remaining channel
• If a process has received a message via all of its incident channels it decides
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Tree Algorithm
12
34
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Echo Algorithm
• Initiator sends messages to all its neighbors
• Upon receipt of the first message a non-initiator forwards messages to all its neighbors except the one from which the message was received
• When a non-initiator has received messages from all its neighbors an echo is sent to the father
• When the initiator has received a message from all its neighbors it decides.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Echo Algorithm
e f
a, father=b
e. father = b
f. father = e
a
b
b
dd cgcg
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Echo Algorithm
a, father=b e. f. a, father=b e. f. father=b father=e father=b father=e
bb
dd cgcg
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Polling Algorithm
• A process can decide if it has received a message from each neighbor
var recp:integer init 0;
Initiator:
begin forall qÎNeighp do send
decide
end
For non-initiators:
begin receive
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Phase Algorithm
• For directed networks, channel can carry messages in one direction only • In-neighbors: processes that can send message to the node
• Out-neighbors: processes to which the node can send message • Diameter of the network must be known
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Phase Algorithm
cons D :integer
var recp[q] :0..D sentp :0..D
//network diameter
//init 0, for each q Î Inp
//init 0, no. of messages sent to
begin if p is initiator then
begin forall rÎOutp do send
sentp:=sendtp+1 end;
while minqRecp[q]
if minqRecp[q] ≥Sentp and Sentp
sentp:=sendtp+1
end;
end;
decide
end
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Traversal Algorithms
•
The traversal algorithms has the following properties:
1. In each computation there is one initiator which starts the algorithm by sending out exactly one message
2. A process, upon receipt of a message, either sends out one message or decides
3. The algorithm terminates in the initiator and when this happens, each process has sent a message at least once
The first two properties imply that in each finite computation exactly one process decides. The algorithm is said to terminate in the single process that decides
•
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Traversing Cliques: Sequential Polling Algorithm
var recp :integer //init 0
For the initiator
(*write neighp={q1,q2,…,qn-1}*) begin while recp<#neighp do
begin sent
receive
decide
end;
For non-initiators:
begin receive
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Traversing Tori
var recp :integer //init 0
For the initiator
send
For each process upon receipt of token
end
else if n|k then send
else send
Grid Torus
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Traversing Connected Network: Tarry’s Algorithm
• R1. A process never forwards the token twice through the same channel
• R2. A non-initiator forwards the token to its father (the neighbor from which it first received the token) only if there is no other channel possible according to rule R1
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Tarry’s Algorithm
2
1
1
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Tarry’s Algorithm
2
2
3
3
1
1
4
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Tarry’s Algorithm
2
2
3
3
1
1
4
5
4
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Summary
• Wave Algorithms • Ring Algorithm
• Tree Algorithm
• Echo Algorithm
• Polling Algorithm • Phase Algorithm
• Traversal Algorithms
• Sequential Polling Algorithm • Tarry Algorithm
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
5. Distributed Mutual Exclusion and Election
Dr. Joe Yuen
Department of Electrical and Electronic Engineering
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Distributed Coordination
• Why do we need distributed coordination?
• To prevent interference and ensure consistency before accessing resources, e.g. NFS file
system to share a common text file. • Distributed Mutual Exclusion (DME)
• A single process being given a privilege – the right to access shared resources – temporarily before another process is granted it.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Distributed Mutual Exclusion
• Basic requirements for DME concerning some resources:
• ME1: (safety) At most one process may execute in the critical section (CS) at
a time.
• ME2: (liveness and deadlock-free) A process requesting entry to the CS is eventually granted it (so long as any process executing in the CS eventually leaves it.)
• ME3: (ordering) Entry to the CS should be granted in happened-before order.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Distributed Mutual Exclusion
• The central server algorithm: server manages a mutual exclusion token for a set of processes
P4
Server
P3
2. Release Token
1. Request Token 3. Grant Token
P1
P4
P2
P3
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Distributed Mutual Exclusion
• To employ a server that grants permission to enter a CS.
• Assume only one CS is managed. The protocol is as follows:
enter( ) …
exit( )
(* enter critical section – block if necessary *)
(* access shared resources in critical section *)
(* leave CS allow other processes may now enter *)
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
Distributed Mutual Exclusion
• Satisfy ME1, ME2 and ME3.
• Problem 1: the server could be performance bottleneck. • Problem 2: single point of failure.
ELEC7078 Advanced Topics in Electrical and Electronic Engineering
Distributed Systems
ELEC7078 Advanced Topics in Electrical and Electronic Engineering (Distributed Systems)
Tutorial 1
1. Consider an inter-process communication that using standard Request-Reply- Acknowledgement protocol as follow:
Client
Blocking state (1)
Request
Reply
Ack
Server
Blocking state (2)
a. Briefly state what will happen if the acknowledgement is lost due to transmission error.
Server should keep the reply in its buffer before time-out.
Client believes the communication is finished after sending the acknowledgement.
b. Suggest how the protocol can be recovered from the transmission error.
Server should resend the reply after time-out.
c. Will the server stop serving other clients during the blocking state (2)?
Server normally uses multithreads / separate process to handle each client request. Therefore, the blocking state (2) will only affected the corresponding client only.
2. Discuss whether the following operations are idempotent:
a. pressing a left (elevator) request button
b. writing data to a file
c. appending data to a file
Is it a necessary condition for idempotence that the operation should not be associated with any state?
a. Yes, b. Yes, c. No
3. Consider a host using Cristian’s method to synchronize its clock with a time server T and got the following records. Assume the total delay of transmitting a message from the host to the time server or vice versa is 10ms.
1
Round-trip (millisecond)
Time (hour:minute:second.millisecond)
27
14:21:32.156
24
14:22:10.564
28
14:22:10.712
a. Which of these times should be used to set its clock? To what time should it set? Estimate the accuracy of the setting.
24 (14:22:10.564)
Time=14:22:10.564+12ms=14:22:10.576
Accuracy: 12-min=+/- 2ms
b. What will the answer of part (a) change if the total delay is 9ms?
Time=No change Accuracy: +/-3ms
c. If it is required to synchronize the host’s to within 1 ms. Discuss how to achieve it. Assume 9ms total delay is used
Keep synchronize until the round-trip is 20ms
4. A group of servers using Berkeley algorithm to synchronize their physical clocks. The coordinator received the following replies:
a. What is the clock difference between the coordinator and members? Give the answer with respect to the coordinator.
b. Draft the messages to be sent to each member and what should the member do after receiving the message?
Average the difference = (0 + 0 – 0.004 + 0.03)/4=0.0065
Time received
Round-trip (ms)
Member
Member’s clock
15:25:30.150
20
A
15:25:30.140
15:25:30.156
28
B
15:25:30.138
15:25:30.160
40
C
15.25:30.170
Time received
Round- trip (ms)
Member
Member’s Clock
Member clock at the time received
Time Different
15:25:30.150
20
A
15:25:30.140
15:25:30.150
0
15:25:30.156
28
B
15:25:30.138
15:25:30.152
-0.004
15:25:30.160
40
C
15.25:30.170
15:25:30.190
+0.030
Receiver
Adjustment
Action
A
0.0065
Adjust the clock 0.0065 sec. faster
2
B
0.0065+0.004=0.0105
Adjust the clock 0.0105 sec. faster
C
0.0065-0.03=-0.0235
Adjust the clock 0.0235 sec. slower
c. What if the clock of member C is running faster than the coordinator by 100ms? What is the potential problem of setting the clock value immediately based on the new adjustment?
Average the difference = (0 + 0 – 0.004 + 0.1)/4=0.096/4=0.024
Receiver
Adjustment
Action
A
0.024
Adjust the clock 0.024 sec. faster
B
0.024+0.004=0.028
Adjust the clock 0.028 sec. faster
C
0.024-0.1=-0.076
Adjust the clock 0.076 sec. slower
5. Consider the i. ii. iii.
iv. v. vi. vii. viii. ix. x.
following events
Process A loaded a file(F1) from local storage (E1)
Process B wrote data to a log file (E2)
Process C sent a message(M1) to process A (E3) and then sent another message(M2) to process B (E4)
Process A received the message(M1) from process C (E5) after E1 Process B received the message(M2) from process C (E6) after E2 Process A wrote the message(M1) to file F1. (E7)
Process B replied process C with another message(M2) (E8) Process C received the reply (M2) from process B (E9)
Process C forwarded the reply (M2) to process A (E10)
Process A received the forwarded message (M2), (E11)
a. Assume the initial logical clocks of all process is zero, what are the logical clock values of E1, E4, E5, E8, E9 and E11?
E1:1, E4:2, E5:2, E8:4, E9:5, E11:7
b. What are the casual orders of E5 and E8, E6 and E9, and E2 and E11?
E5 || E8, E6 -> E9, E2->E11
3
c. Can we work out the casual order of E2 and E11 by their logical clocks?
No, although the clock value of E11 (11) is greater than E2 (1), there is no guarantee that E2 is happen before E11 (even E2 is actually happened before E11). Consider E2 and E4, the clock value of E4 is greater than E2 but E2 and E4 are not casually related.
d. What are the vector clocks of E2 and E11? Can we work out the casual order of E2 and E11 by based on the vector clocks?
E2: [0,1,0], E11:[4,3,4]
E2 < E11 (at least one index i fulfill the requirement E2[i] < E11[i])
4