Transcript (A) 2002, MT Harandi, J. Hou, and I. Gupta

ECE 428
Distributed Systems
Yih-Chun Hu
August 25, 2005
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-1
The “Constitution” of Distributed
Systems
(and the First Amendment)
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-2
Our First Aim Today
To Define the Term Distributed System
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-3
Can you name some examples of Operating
Systems?
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-4
Can you name some examples of Operating
Systems?
…
Linux WinXP Unix FreeBSD Mac
2K Aegis Scout Hydra Mach SPIN
OS/2 Express Flux Hope Spring
AntaresOS EOS LOS SQOS LittleOS TINOS
PalmOS WinCE TinyOS
…
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-5
What is an Operating System?
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-6
What is an Operating System?
•
•
•
•
•
User interface to hardware (device driver)
Provides abstractions (processes, file system)
Resource manager (scheduler)
Means of communication (networking)
…
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-7
FOLDOC definition
•
•
•
•
The low-level software which handles the interface to peripheral hardware,
schedules tasks, allocates storage, and presents a default interface to the
user when no application program is running.
The OS may be split into a kernel which is always present and various
system programs which use facilities provided by the kernel to perform
higher-level house-keeping tasks, often acting as servers in a client-server
relationship.
Some would include a graphical user interface and window system as part
of the OS, others would not. The operating system loader, BIOS, or other
firmware required at boot time or when installing the operating system
would generally not be considered part of the operating system, though
this distinction is unclear in the case of a roamable operating system such
as RISC OS.
The facilities an operating system provides and its general design
philosophy exert an extremely strong influence on programming style and
on the technical cultures that grow up around the machines on which it
runs.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-8
Can you name some
examples of
Distributed Systems?
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-9
Can you name some examples of
Distributed Systems?
•
•
•
•
•
•
•
•
•
•
Client-server (e.g., NFS)
The Internet
The Web
An ad-hoc network
A sensor network
DNS
Kazaa (peer to peer overlays)
Titan Lander-Orbiter-Earth Station
(Society?)
(Food Chain?)
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-10
What is a Distributed System?
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-11
FOLDOC definition
A collection of (probably heterogeneous) automata whose distribution is
transparent to the user so that the system appears as one local machine.
This is in contrast to a network, where the user is aware that there are
several machines, and their location, storage replication, load balancing
and functionality is not transparent. Distributed systems usually use some
kind of client-server organization.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-12
Textbook definitions
• A distributed system is a collection of
independent computers that appear to the users
of the system as a single computer
[Andrew Tanenbaum]
• A distributed system is several computers doing
something together. Thus, a distributed system
has three primary characteristics: multiple
computers, interconnections, and shared state
[Michael Schroeder]
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-13
Unsatisfactory
• Why are these definitions short?
• Why do these definitions look inadequate to us?
• Because we are interested in the insides of a
distributed system
–
–
–
–
design and implementation
maintenance
study
algorithmics
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-14
“I shall not today attempt further to define the kinds of
material I understand to be embraced within that shorthand
description; and perhaps I could never succeed in
intelligibly doing so. But I know it when I see it, and the
motion picture involved in this case is not that.”
[Potter Stewart, Associate Justice, US Supreme Court
(talking about his interpretation of a technical term laid
down in the law, case Jacobellis versus Ohio 1964) ]
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-15
Which is a Distributed System – (A) or (B)?
(A)
(A) Plants and Animals interacting in the Food Chain
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-16
(B)
(B) The Internet (Internet Mapping Project, color coded by ISPs)
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-17
A working definition for us
A distributed system is a collection of entities, each
of which is autonomous, programmable,
asynchronous and failure-prone, and
communicating through an unreliable
communication medium.
• Our interest in distributed systems involves
– design and implementation, maintenance, study, algorithmics
• Entity=a process on a device (PC, PDA)
• Communication Medium=Wired or wireless network
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-18
A range of interesting problems for
Distributed System designers
•
•
•
•
•
•
•
•
•
•
•
•
Basic Concepts [Asynchrony,Consensus,…]
Routing [IP,BGP]
Large-scale Systems [The Grid,Gnutella,Kazaa]
Distributed File Systems [NFS,AFS]
Protocols, e.g., multicast [IP multicast, SRM, RMTP]
Coordination[SETI@Home,Multiplayer online games]
Storage and Databases
Security
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-19
Distributed Systems Design Goals
• Common Goals:
– Heterogeneity – can the system handle different types of
PCs and devices?
– Robustness – is the system resilient to crashes and
failures?
– Availability – are data, services always there?
– Transparency – can the system hide its internal
workings from the users?
– Concurrency – can the server handle multiple clients
simultaneously?
– Efficiency – is it fast enough?
– Scalability – can it handle 100 million nodes?
– Security – can the system withstand hacker attacks?
– Openness – is the system extensible?
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-20
Distributed System Example -- the Internet
intranet
%
ISP
%
%
%
backbone
satellite link
desktop:
server:
network link:
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-21
The Internet
• A vast interconnected collection of computer
networks of many types.
• Intranets – subnetworks operated by companies
and organizations.
• ISPs – companies that provide modem links and
other types of connections to users.
• Intranets are linked by backbones – network links
of large bandwidth, such as satellite connections,
fiber optic cables, and other high-bandwidth
circuits.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-22
A Typical Intranet
email s erv er
Desktop
computers
print and other servers
Web server
Local area
netw ork
email s erv er
File s erv er
print
other servers
the rest of
the Internet
router/firew all
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-23
Intranets
• Composed of several local area networks (LANs)
linked by backbone connections.
• Connected to the Internet via a router/multiple
routers.
• A firewall is used to protect an intranet by
preventing unauthorized message
leaving/entering, and is implemented by filtering
incoming and outgoing messages.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-24
Internet Apps: Their Protocols and
Transport Protocols
Application
e-mail
remote terminal access
Web
file transfer
streaming multimedia
remote file server
Internet telephony
Application
layer protocol
Underlying
transport protocol
smtp [RFC 821]
telnet [RFC 854]
http [RFC 2068]
ftp [RFC 959]
rtsp [RFC 2326],
proprietary
NFS
H.323, SIP [RFC
2543], …
TCP
TCP
TCP
TCP
TCP or UDP
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
TCP or UDP
typically UDP
Lecture 1-25
WWW: the HTTP Protocol
HTTP: hypertext transfer
protocol
•
•
WWW’s application layer
protocol
client/server model
PC running
Explorer
– client: browser that requests,
receives, and “displays”
WWW objects
– server: WWW server sends
objects in response to
requests
•
•
http1.0: RFC 1945
http1.1: RFC 2068
Server
Running
cnn.com
Web
server
Mac running
Navigator
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-26
The HTTP Protocol: More
http: TCP transport
service:
• client initiates a TCP
connection (creates socket)
to server, port 80
• server accepts the TCP
connection from client
• http messages (applicationlayer protocol messages)
exchanged between
browser (http client) and
WWW server (http server)
• TCP connection closed
http is “stateless”
• server maintains no
information about
past client requests
aside
Protocols that maintain “state”
are complex!
• past history (state) must be
maintained
• if server/client crashes, their
views of “state” may be
inconsistent, and hence must
be reconciled.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-27
HTTP Example
Suppose user enters URL www.cs.uiuc.edu/
(contains text,
references to 10
jpeg images)
1a. http client initiates a TCP
connection to http server
(process) at www.cs.uiuc.edu.
Port 80 is default for http server.
1b. http server at host
www.cs.uiuc.edu waiting for a
TCP connection at port 80.
“accepts” connection, notifying
client
2. http client sends a http request
message (containing URL) into
TCP connection socket
3. http server receives request
messages, forms a response
message containing requested
object (index.html), sends
message into socket
time
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-28
HTTP Example (cont.)
4. http server closes the TCP
connection.
5. http client receives a response
message containing html file,
displays html, Parses html
file, finds 10 referenced jpeg
objects
6. Steps 1-5 repeated for each of 10
time
jpeg objects
• non-persistent connection: one object in each TCP
connection
– some browsers create multiple TCP connections
simultaneously - one per object
• persistent connection: multiple objects transferred within
one TCP connection
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-29
Trying Out HTTP (Client Side) for Yourself
1. Telnet to your favorite WWW server:
telnet www.eurecom.fr 80 Opens TCP connection to port 80
(default http server port) at www.eurecom.fr.
Anything typed in sent
to port 80 at www.eurecom.fr
2. Type in a GET http request:
GET /~ross/index.html HTTP/1.0
By typing this in (hit carriage
return twice), you send
this minimal (but complete)
GET request to http server
3. Look at response message sent by http server!
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-30
Does our Working Definition work for the http W
A distributed system is a collection of entities, each
of which is autonomous, programmable,
asynchronous and failure-prone, and
communicating through an unreliable
communication medium.
• Our interest in distributed systems involves
– design and implementation, maintenance, study, algorithmics
• Entity=a process on a device (PC, PDA)
• Communication Medium=Wired or wireless network
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-31
“Important” Distributed Systems Issues
• No global clock; no single global notion of
the correct time (asynchrony)
• Unpredictable failures of components: lack
of response may be due to either failure of
a network component, network path or a
computer crash (failure-prone, unreliable)
• Highly variable bandwidth
• Possibly large and variable latency
• Large numbers of hosts
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-32
“Important” Issues
• If you’re already complaining that the list of topics
we’ve discussed so far has been perplexing…
– You’re right!
– It was meant to be (perplexing)
• The Goal for the Rest of the Course: see enough
examples and learn enough concepts so these
topics and issues will make sense
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-33
“Concepts”?
•
Which of the following inventions do you think is
the most important?
1. The PDA
2. The PC
3. The transistor
•
Which of the following inventions do you think is
the most important?
1. Email
2. The Web
3. TCP/IP
“What lies beneath?” Concepts!
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-34
How will you Learn?
Take a look at handout “Course Information and Schedule”
• Text: Coulouris, Dollimore, and Kindberg
• Lectures
• Homeworks
– Approx. one every two weeks
– Need to be typed, figures can be hand-drawn
• Programming assignments
– Incremental, in 5-6 stages
– We will probably build a peer to peer system!
• Exams/quizzes
– Midterm, and final
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-35
What assistance is available to you?
• Lectures
– lecture slides will be placed online at course website
» “Tentative” version before lecture
» “Final” version after lecture
• Homeworks – office hours to help you (without
giving you the solution)
• Programming Assignments – program templates
will be given to you. C (or C++) programming.
– The last assignment will be open-ended, and can turn into a
research project.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-36
If you’re still thinking, “Everything you’ve
said so far is so ho-hum...”…
CS425 is about enjoying distributed systems,
learning a few new things, and designing some
cool new systems that you can boast about to
your friends (and job interviewers).
We’re here to help you achieve all these things.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-37
For Next Class
• Read sections 10.1-10.4
• Fill out and return Student InfoSheet
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-38
The “Constitution” of Distributed
Systems
(and the First Amendment)
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-39
Additional Slides
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-40
Design Challenges: Heterogeneity
• Variety and differences among:
–
–
–
–
Networks
Hardware and Operating Systems
Programming Languages
Implementations
• Middleware – a software layer that provides a programming
abstraction as well as
– (i) masking the heterogeneity of the underlying networks, hardware,
operating systems and programming languages.
– (ii) providing uniform computational models, e.g., remote object
invocation, remote event notification.
• Virtual machine
– The compiler for a particular language generates code for a virtual
machine, instead of a particular hardware code to assist execution of
mobile code.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-41
Design Challenges: Openness
• Degree to which new resource-sharing
services can be added & used.
• Requires publication of interfaces for
access to shared resources
• Requires uniform communication
mechanism
• Conformance of each component to the
published standard must be tested and
verified
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-42
Design Challenges: Security
• Security has three components:
– Confidentiality (protection against disclosure to
unauthorized individuals).
– Integrity (protection against alternation or corruption).
– Availability (protection against interference with the
means to access the resources).
• Two security challenges:
– Denial of service attacks: bombarding the service with a
large number of pointless requests.
– Mobile code security: mobile codes may be accessing
local resources.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-43
Design Challenges: Scalability
• A system is said to be scalable if it will remain
effective when there is a significant increase in
the number of resources and users:
– Controlling the cost of resources
– Controlling the performance loss
– Preventing software resources running out
(e.g., IP addresses)
– Avoiding performance bottlenecks
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-44
Design Challenges: Failure Handling
• Failure in DS is partial – some component fails
while the rest is functional;
– Detecting failures (remote site crash or delay in
message transmission?)
– Masking failures (message retransmission, file
replication)
– Tolerance for failure (clients give up after a predetermined number of attempts and take other actions)
– Failure recovery (checkpoint and rollback recovery)
– Redundancy (multipath routing, replicated database,
replicated DNS)
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-45
Design Challenges: Concurrency
• Is a problem when two or more users access to
the same resource by two at the same time
– Each resource is encapsulated as an object and
invocations are executed in concurrent threads
– Concurrency can be maintained by use of semaphores
and other mutual exclusion mechanisms.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-46
Design Challenges: Transparency
• Concealment of the separation of components from users:
–
–
–
–
–
–
–
Access transparency: local and remote resources can be
accessed using identical operations.
Location transparency: resources can be accessed without
knowing their whereabouts.
Concurrency transparency: processes can operate
concurrently using shared resources without interferences.
Failure transparency: faults can be concealed from
users/applications.
Mobility transparency: resources/users can move within a
system without affecting their operations.
Performance transparency: system can be reconfigured to
improve the performance.
Scaling transparency: system can be expanded in scale
without change to the applications.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-47
Design Challenges: Transparency
• Distributed file system allows access
transparency and location transparency.
• URLs are location transparent, but are not
mobility-transparent (someone’s personal web
page cannot move to a new place and still be
accessed using the same URL).
• Message retransmission governed by TCP is a
mechanism for providing failure transparency.
• Mobile phone is an example of mobility
transparency.
 2002, M. T. Harandi, J. Hou, and I. Gupta (modified Y. Hu)
Lecture 1-48