Introduction to
Distributed Systems
Brian Nielsen
[email protected]
About me
• Brian Nielsen
• Lecturer in Computer Science
• Distributed
Di ib d and dE
Embedded
b dd d SSystems
• Research
– Distributed programming (Linda w. multiple tuple
spaces)
– Distributed
Di t ib t d M
Multi-media
lti di
– Real-Time Operating Systems
– Automated testing of embedded, real-time, distributed
systems
About You
• Dat-3
Dat 3
• F7S
• SSE 1 / MI1 / DE-1
SSE-1 DE 1
• Guests (SSE-1)
• EVU
• Project Course vs Study Course
• ⇒ Different background and expectations
Teaching Assistant
• Claus Rørbæk Thrane:[email protected]
Thrane:crt@cs aau dk
Study Regulations
“Purpose: That the student obtains knowledge about
concepts in distributed systems
systems, knowledge about their
construction, and an understanding of advantages and
disadvantages of their use.”
Study Regulations
Contents:
•Structure of distributed systems.
•Distributed algorithms.
•Distributed and parallel programming.
•Fault
Fault tolerance.
tolerance
•Examples of one or more distributed systems.
Goals
• Solid understandingg of the characteristics and p
properties
p
of Distributed System
• Solutions
– Programming languages/models
– Middleware
– Distributed algorithms for typical problems: mutex, multicast,
consensus, replication
• Advantages and disadvantages of a distributed solution
– When and which to choose
– Evaluate a system design
• Skill in implementation of distributed systems/algorithms
Course Form
• 3 ECTS (3*30
(3 30 study hours), 15 lectures
• 1 lecture = 6 study hrs
– 2 45 min of lectures
2*45
– 1.5 hrs of exercises with TAs in groups
– 1.5 hrs of reading homework
– 0.5 hrs of exam-preparation
• 1 “big” study assignment subject to examination
• PE: exam part of project-exam
• SE: Oral 20 mins, Binary scale!
Text Book
• Coulouris, Dollimore and
Kindberg
• Distributed Systems:
Concepts and Design
• Edition 4
• www.cdk4.net
Preliminary Course Plan
Lecture Topic
1 Introduction to Distributed Systems
2 Programming Models I - RPC,
RPC RMI
Programming Models II – message passing, events, shared
3
memory
4 Distributed File Systems
5 Peer2peer Systems
6 Clock Synchronization
7 Distributed Mutual Exclusion & Election
8 Multicast communication
9 Consensus and study-exercises
10 Replication
13 Study Exercise
11 Web Services
12 Introduction to Grid Computing (Guest Lecture by Josva Kleist)
14 Study Exercise
15a Conclusions and Exam Information
15b Exam Questioning Hour / Spørgetime
Pre requisites
Pre-requisites
• Programming
– Practical programming in e.g. Java, C, C++
– Basic data-structures and algorithms
– Preferably also concurrent programming
• Networks
N t k
– IP-stack, IP-addressing, IP-routing, message enveloping,
TCP/UDP, Sliding-window, socket-programming, basic
encryption technology
– Else read chapter 3
• Operating Systems
– Processes
Processes, threads
threads, concurrency
concurrency, non-determinism
non determinism, kernel and
user level, synchronization (semaphores, monitors), address
spaces, virtual memory, file-systems
– Else read chapter 6
Examples of Distributed
Systems
A typical portion of the
Internet
intranet
ISP
backbone
satellite link
desktop computer:
server:
network link:
A typical intranet
email server Desktop
computers
print and other servers
Local area
Web server network
email server
print
File server
other servers
the rest of
the Internet
router/firewall
Intranets
• Ap
portion of the Internet that
– is separately administered
– usually proprietary
– provides internal and external services
– can be configured to enforce local security policies
• may
ay use a firewall
e a to p
prevent
e e tuunauthorized
aut o ed messages
essages leaving
ea g
or entering
– may be connected to the internet via a router
• Services:
– File, print services, backup, program-sharing, user-,
system-administration, internet access
Automotive Control
•80+ ECU’s interconnected in controller area networks
•Vehicle dynamics (engine, brake, gear control,…)
•Instrumentation control (lights, indicators, windows,…)
•System Integration
•Information
I f ti andd entertainment
t t i t systems
t
•Drive-by-wire
Distributed Computing
• Speed up huge computations by using multiple
computers
• NOWs (network of workstations) / cluster
computing
• Dedicated computers
• seti@home: project to scan data retrieved by a
radio
di ttelescope
l tto search
h ffor radio
di signals
i l ffrom
another world;
• Grid Computing: www.grid.org
www grid org (Millions CPUs
world-wide – source 2004)
Cluster & Grid Computing
Home made PC cluster
Fyrkat@AAU
Fyrkat is a 672 core cluster with specs:
84 IBM blades
bl d - 2 Xeon
X quadd core 2 cpus 2.33
2 33 Ghz
Gh
16 GB memory per blade
Infiniband interconnect
Sensor-networks
Games
Mission-critical
Mission critical applications
• Embedded systems,
y automotive, avionics
• Control Systems
• Banking, stock markets, stock brokerages
• H lth care, h
Health hospital
it l automation
t ti
• Control of power plants, electric grid
• Telecommunications infrastructure
• Electronic commerce and electronic cash on the Web
(very important emerging area)
• Corporate “information” base: a company’s memory of
decisions, technologies, strategy
• Military command, control, intelligence systems
• …
Shared Memory Multi-Processor
Multi Processor
processor processor processor
cache cache cache
NOT System bus
a
di t ib t d system!
distributed t !
i/o subsystem
Main
memory
Domain Name Service
root
dk com gov mil org net uk fr etc.
aau mit
cs ece owlnet
• Database that maps host names to IP-
homer addresses and vice versa
• homer.cs.aau.dk =130.225.194.13
130.225.194.13
• Client--server interaction on UDP Port 53
DNS: History
• Initially all host-addess mappings were in a file
called hosts.txt (in /etc/hosts)
– Changes were submitted to SRI (Stanford Research
Institute) by email
– New versions of hosts.txt ftp’d periodically from SRI
– An administrator could pick names at their discretion
– Any name is allowed: eugenesdesktopatrice (flat
namespace)
• As the internet grew this system broke down
because:
– SRI couldn’t handled the load
– Hard to enforce uniqueness of names
– Many hosts had inaccurate copies of hosts.txt
• Domain Name System (DNS) was born in ‘83
DNS zone data records
Example Domain dcs.qmul.ac.uk
domain name time to live class type value
www 1D IN CNAME apri cot
p cot
apri 1D IN A 138.37.88.248
dcs 1D IN NS dns0.dcs
dns0.dcs 1D IN A 138.37.88.249
dcs 1D IN NS dns1.dcs
dns1.dcs 1D IN A 138.37.94.248
dcs 1D IN NS cancer.ucs.ed.ac.uk
CNAME = Canonical name for an alias
A = IP Address
NS = Authorative name server
DNS: Root Name Servers
• Contacted by local name
server that can not resolve
name
• Root name server:
– Contacts authoritative
name server if name
mapping not known
– Gets mapping
– Returns mapping to local
name server
• Several root name servers
worldwide
DNS Servers
root name server
Root name server:
• M
May nott know
k
authoritative name
server
• May
ay know
o intermediate
e ed a e
name server: who to
contact to find
authoritative name local name server intermediate name server
server? dns cs aau dk
dns.cs.aau.dk ((com server))
authoritative name server
ns1.google.com
requesting host
homer.cs.aau.dk
www.google.com
Example of Recursive DNS
Query
root name server
Root name server:
• M
May nott know
k
authoritative name 6
2
server 7 3
• May
ay know
o intermediate
e ed a e
name server: who to
contact to find
authoritative name local name server intermediate name server
server? dns cs aau dk
dns.cs.aau.dk ((com server))
Recursive query: 4 5
1 8
• Puts burden of name
resolution on contacted authoritative name server
name server ns1.google.com
• Heavy load? requesting host
homer.cs.aau.dk
www.google.com
Example of Iterated DNS Query
root name server
Iterated query
Contacted server iterated query
2
replies with name
of server to contact 3
4
• “II don
don’tt know this 5
name, but ask this intermediate name server
server” local name server (com server)
((delegation):
g ) dns cs aau dk
dns.cs.aau.dk 7
6
1 8
authoritative name server
This iis h
Thi how ns1.google.com
today’s DNS requesting host
system
y behaves homer.cs.aau.dk
www.google.com
DNS spoofing
DNS-spoofing
Query: (A,
(A netbank
netbank.bank.dk)
bank dk)
local name server Response: (A, netbank.bank.dk 216.239.37.99) remote name server
dns cs aau dk
dns.cs.aau.dk ns1.bank.dk
1 b k dk
Quick Response: (A, netbank.bank.dk,172.133.44.44)
Attacker
172.133.44.44
• Until the TTL expires, 172.133.44.44
serves netbank.dk
Lessons Learned
• Flexibility
• Manual or static configuration or update is too inflexible
• Must work across organizations and administrative domains with different
security and resource usage policies
• Heterogeneous Computer and OS
• Performance
• Avoid Bottlenecks - typically occurs at centralized components
• Localize access
• to increase response time and minimize (long-distance
(long distance communication).
• caching
• Distribute load evenly
• Use parallelism for increased processing power.
• Scaleability
• Dependability
• Replication for increased availability, fault tolerant
• Security is always a problem!
• Correct functionality
Definition
Definition
• A distributed system is the one in which
hardware and software components at
networked computers communicate and
coordinate their activity only by passing
messages.
messages
• Examples: Internet, intranet and mobile
computing systems.
systems
Consequences
• Concurrent execution of processes
– Users work independently & share resources
– non-determinism, race-conditions, synchronization, deadlock,
liveness, …
• No global clock
– Coordination is done by message exchange
– There are limits to the accuracy with which computers in a network
can synchronize their clocks
• No global state
– Generally, there is no single process in the distributed system that
would have a knowledge g of the current gglobal state of the system
y
• Units may fail independently.
– Network faults can result in the isolation of computers that continue
executing
– A system failure or crash might not be immediately known to other
systems
Why a Distributed System?
• Functional distribution
– computers have different functional (eg. File server,
print, ) capabilities yet may need to share resources
• Client / server
• Data gathering / data processing
• Inherent distribution in application domain
• physically or across administrative domains
• cash register and inventory systems for supermarket chains
• computer supported collaborative work
• Economics
– collections of microprocessors offer a better price/
performance ratio than large mainframes
Why a Distributed System?
• Better performance
– Load balancing
– Replication of processing power
• Increased Reliability
– Exploit independent failures
f property and
– Redundancy
Models
Architectural
Fundamental (semantic
assumptions)
Architectural models
• Software layers
• System architecture
OSI model
OSI-model
•Open Systems Interconnection model (ISO standard)
•Session Layer: Dialog
controller
•Establish
Establish
•Maintain
•Synchronize
•Terminate
Presentation layer: handles
syntax and semantics
•Data translation
•Encryption/decryption
•Compression/expansion
Service layers
Applications, services
.net Remoting RMI
MSMQ Middleware MASSIV
jGroups Corba Jini OSGi
Operating system
Platform
Computer
p and network hardware
Middleware
• Software layer (library of functions) that
simplifies programming
– Masks heterogeneity
– Provides a convenient programming model
• Objects/ processes
• Comm nication primiti
Communication primitives
es
• Synchronization
• Group and multicasting
• Naming and Localization services
• Event notification
– Corba,
Corba JavaRMI,
JavaRMI .NET
NET Remoting,
Remoting MPI,
MPI ISIS
ISIS,…
Clients / Server model
Client invocation Server
invocation
result result
Server
Client
Key:
Process: Computer:
Variations:
•thin / thick / smart ((dynamic)
y ) clients
•Server-farms
•multi-tier systems
A distributed application
based on peer processes
Peer 2
Peer 1
Application
Application
Sharable Peer
ee 3
objects
Application
Peer 4
Application
Peers 5 .... N
Client Server vs Peer based
Client-Server Peer
• Most widely used • Symmetrical,
model computers runs same
• Functional algorithms
l ith / same
specialization responsibilities
• Asymmetrical
A ti l • Truly Distributed
• Tends to be • Share / exploit
Centralized resources at a large
g
number of
• Tends to scale poorly participants
Fundamental Models
Design and solutions depend on
fundamental assumptions on
– Process Interaction
– Failures
F il
– Security threats
Interaction Model
Message send / receive
• Process:
– executing program with private state
– sending and receiving messages
• Distributed Algorithms:
– A definition of the steps to be taken by each of the processes of
which the system is composed, especially the messages
transmitted between them
• Communication Performance is a limiting characteristic
– Latency, bandwidth, Jitter
• It is impossible to maintain a single notion of time
– Computer clocks have drift
– GPS: 1 micro Sec
– Message Passing (eg.NTP) 100ms
Communication speed
Compare:
static void Main(string[] args)
{
uint i = 0; long y; int x = 500;
const uint MAX_ITER = 1000000; // 1million
DateTime tmStart; DateTime tmEnd;
tmStart = DateTime.Now;
for (i = 0; i <= MAX_ITER; i++)
y = x * i;
tmEnd = DateTime.Now;
TimeSpan tmDiff = tmEnd - tmStart;
Console.WriteLine(MAX_ITER + "iterations took "+
(tmDiff TotalMilliseconds ) + "ms");
(tmDiff.TotalMilliseconds ms );
}
With: Roundtrip time:
Pingg www.cs
Ping krak.dk
Ping google.com
Ping www.jcu.edu.sg
Interaction model 1:
A
Asynchronous
h systems
No known bounds for:
• The execution speed of a process
• Message
M d
delay
l on th
the network
t k
• Clock drift
Interaction model 2:
(P l ) Synchronous
(Partly) S h systems
• Known upper and lower bound for each
process step
• Known upper bound for the time it task for
a message to be received
• Known
K upper bound
b d ffor clock
l kd drift
ift
Failure Model
• The system might need to tolerate failures
– processes
• might stop / crash
• degrade gracefully
• exhibit Byzantine
y failures
– may also be failures of
• communication mechanisms
Omission and arbitrary
failures
Class of failure Affects Description
p
Fail-stop Process Process halts and remains halted. Other processes
may detect this state.
Crash Process Process halts and remains halted. Other processes
may nott be
b able
bl tto d
detect
t t this
thi state.
t t
Omission Channel A message inserted in an outgoing message buffer
never arrives at the other end’s incoming message
buffer.
Send-omission Process A process completes a send but the message is
not put in its outgoing message buffer.
Receive- Process A message is put in a process’s incoming message
omission buffer but that process does not receive itit.
buffer,
Arbitrary Process Process/channel exhibits arbitrary behaviour: it may
(Byzantine) or send/transmit arbitrary messages at arbitrary times,
channel commit omissions; a process may stop or take an
incorrect step.
Timing failures
Class of Failure Affects Description
Clock Process Process’s local clock exceeds the bounds
on its
it rate
t off drift
d ift from
f reall time.
ti
Performance Process Process exceeds the bounds on the interval
between two steps.
Performance Channel g
A message’s transmission takes longer
g than
the stated bound.
Security model
• Protection of objects, ressources
• Securing processes and their interaction
– Goals
• Secrecy, integrity, authentication, authorization,..
– Attacks
• man-in-the-middle, eaves-dropping, play-back, …
Copy of m
The enemy
m´
Process q m Process q
Communication channel
END
