Transcript bit8_DC_lec01

Tip
I hear and I forget,
I see and I remember,
I do and I understand.
-Chinese Proverb
Distributed Systems
Fall Semester
Raihan Ur Rasool
Session 01:
Characteristics of Distributed Systems
2
Information
•
•
•
•
•
•
Office #: +51-9280439 (129)
Email: [email protected]
Email: vitalfact @ {gmail, hotmail}.com
Group: http://groups.yahoo.com/group/bit_8
Group Email: [email protected]
TA: Shahid Mehmood
– [email protected]
3
Overview
• This course focuses on the issues fundamental to the
understanding of distributed systems.
• Text and reference books
– Distributed Systems - Concept and Design, G. Coulouris, J,
Dollimore, and T. Kindberg, Addison-Wesley, 4th Edition,
2005.
– Distributed Systems – Principles and Paradigms, A.
Tanenbaum and M. van Steen, Prentice Hall, 2002.
• Course Webpage: http://www.niit.edu.pk/~dr.raihan/BIT8_DC.html
•
Check Regularly
What we’ll learn
•
•
•
•
•
•
•
•
•
Characteristics of Distributed Systems
Distributed System Models
Interprocess Communication
Grid Computing
Distributed Objects and Remote Invocation
Peer to Peer Systems
Web Services
Service Oriented Architecture
Socket Programming, MPI, RMI, MPICHG2
Tentative Grading
•
•
•
•
•
•
Midterm
:
Quizzes
:
Assignment & Lab
:
Concept report/ Project :
Final Exam
:
Open
:
25 %
5%
10 %
10 %
45 %
5%
6
Class Information
• Class groups: 3 students/ group
• For CR: Send me the list by 28th Nov [5:00 PM]
• ** Five minute rule **
• Two 50 mins Lectures (Tue)
• Two Hrs Lab (Thur)
• Paper Discussion Session:
– One 20 mins paper-discussion sessions (Thur)
7
Academic Integrity
• Permitted Collaboration:
–
–
–
–
–
–
–
–
encouraged and allowed at all times
Examples
Discussion of material covered during lecture / handouts
Discussion of the requirements of an assignment
Discussion of the use of tools or development environments
Discussion of general approaches to solving problems
Discussion of general techniques of coding or debugging
Discussion between a student & a TA or instructor
Academic Integrity
• Collaboration Requiring Citation:
– must be able to explain the solution
– properly credit contribution, just like citing a reference in a
paper
• Examples
–
–
–
–
–
Discussing the “key” to a problem
Discussing the design of a programming project
Assistance in debugging code
Sharing advice for testing
Research from alternative sources
Academic Integrity
• Non-permitted Collaboration:
– submissions must represent original, independent work
• Examples
–
–
–
–
–
Copying solutions from others
Using work from past quarters
Studying another student's solution
Debugging code for someone else
Cut & paste of solution/code from Internet
Overview
•
•
Introduction and History
Examples of distributed systems
–
–
–
•
The internet
Interanets
Moble and ubiquitous computing
Resource sharing and the web
–
The world wide web
•
•
•
•
•
•
•
HTML
URL
HTTP
Dynamic Pages
Web Services
Discussion of the web
Our Aim
• explain the characteristics of networked computer
Challenges
–
–
–
–
–
–
–
Heterogeneity
Openness
Security
Scalability
Failure Handling
Concurrency
Transparency
11
Lets start our journey !
12
History
• Uni-processory monolithic computing
– Tightly coupled computers
• RFC 1
– ARPANET (four node network) –1972
• Increase in the network bandwidth in 1980
• Distributed Systems
– Loosely coupled computers
– Network service (FTP, email) , Client Server
– Network Application
• Resource Sharing
13
Definition of Distributed System
• A distributed system is:
– Components located at networked
computers communicate and coordinate
their actions by passing messages
• A distributed system is:
– Collection of independent computers that
appear to the users of the system as a
single computer [Tanenbaum]
14
Forms of computing
• Monolithic Computing
– Single-user monolithic computing (word, excel)
– Multiuser monolithic computing
• Distributed Computing
– WWW, IE and web server interaction
• Parallel Computing
– CPUs can execute deferent portions without
interfering
• Cooperative Computing
– Sharing surplus CPU cycles –SETI@Home
15
Definition of Distributed System
• "a collection of autonomous computers linked by a
computer network with distributed system software"
• "a collection of processors interconnected by a
communication network in which each processor has
its own local memory and other peripherals and the
communication between any two processors of the
system takes place by message passing over the
communication network"
• "one in which hardware or software components
located at networked computers communicate and
coordinate their actions only by passing messages"
16
Definition(s) of a Distributed System
• A distributed system is:
• one in which hardware or software components at networked
computers communicate and coordinate their actions only by
passing messages [CDK]
• collection of independent computers that appears to its users
as a single coherent system. [DS]
• several computers doing something together; multiple
components, interconnections and shared state [Schroeder]
• fundamental properties are fault tolerance and parallelism
[Mullender]
• one that stops you from getting any work done when a machine
you’ve never heard of crashes [Lamport]
• A set of communicating autonomous entities functioning
together to achieve a common goal [Cheriton]
• Collection of computer nodes connected by a network running
software that makes it function as one system.
Definition of Distributed System
• In other words, to the user, a DS looks like a single system
– a virtual uniprocessor
• The user doesn't know (or care)
– - where (on what machine) files are located
– - where a job is executed
• A Distributed System is made of several computers which
– have no shared memory
– have no shared clock
– communicate with each other via messages
– have their own operating systems
18
Advantages
• Why distributed systems
– Resource sharing
– Communication
– Inherent distribution
– Speed
• 10000 CPU running at speed of 50 MIPS
• 500,000 MIPS
– Economy
– Incremental growth
– Reliability
19
Characteristics of DS
• Concurrency
– Distributed systems are concurrent systems
• Every software or hardware component is autonomous
– Process
• Concurrent tasks
– Synchronization and coordination by message passing
• Lack of global clock
– Coordination and time
• Independent failure
– Failures of individual processes may remain undetected
– Each component can individually fail, leaving the others
still running
20
Examples of Distributed Systems
1. The internet
– Heterogeneous network of computers and
applications
– Implemented through Internet protocol
intranet
%
ISP
%
%
%
backbone
satellite link
desktop computer:
server:
network link:
21
Examples of Distributed Systems
2. Distributed multimedia
•Often use the Internet infrastructure
•Characteristics
•Heterogeneous data sources that need to be synchronized
in real time
•Video, Audio, Text
•Often: distribution services
•Examples
•Tele teaching, Video conferencing
22
Examples of Distributed Systems
3. Intranet
•Locally administered network
•Usually proprietary
•Interfaces with the Internet via router
•Firewall
email server
Desktop
computers
print and other servers
Web server
Issues
Local area
network
email server
- File services need to
share data
-Firewall
the rest of
-Legitimate access
the Internet
File server
print
other servers
router/firewall
23
Examples of Distributed Systems (1)
4. Mobile and Ubiquitous computing
•Resource Sharing while on the move –Nomadic computing
•Access home intranet
•Primary concerns:
•resource discovery
•efficient use of limited bandwidth
•security (privacy)
Internet
Host intranet
WAP
gatew ay
Wireles s LAN
Mobile
phone
Laptop
Printer
Camera
Home intranet
Host site
24
Resource sharing and the Web
Resource sharing pattern
•Sharing of the higher level resources
•Shared database or set of WebPages
•Search engine (Google search() )
Service
•Software that manages a collection of resources and presents
them to users and applications via a well-defined interface
•E-payment service
•File service (methods: read, write, delete)
•Server
•Running program (a process that provide one or more
services)
•Remote invocation
•Client’s request to server.
25
Overview
•
•
Introduction and History
Examples of distributed systems
–
–
–
•
The internet
Intranets
Mobile and ubiquitous computing
Resource sharing and the web
– The world wide web
•
•
•
•
•
•
•
HTML
URL
HTTP
Dynamic Pages
Web Services
Discussion of the web
Challenges
–
–
–
–
–
–
–
Heterogeneity
Openness
Security
Scalability
Failure Handling
Concurrency
Transparency
26
Challenges
• A number of challenges arises:
• Heterogeneity
• Openness
• Security
• Scalability
• Failure handling
• Concurrency of components
• Transparency
27
Challenges
• Heterogeneity
–
–
–
–
networks
computer hardware
Operating systems
Programming languages
• Data types representation/ byte order
• Middleware
– To overcome differences in network, OS and
languages
• RMI, CORBA
• Heterogeneity and mobile code
• Applets
28
Definition of Distributed
System
A distributed system organized as middleware.
Note that the middleware layer extends over multiple machines.
29
Challenges
• Openness
– Ensures extensibility and maintainability of the
system
• Standard interfaces & their publication
• Addition of new resources
– RFC specification for internet protocols.
– key interfaces are published
• Benefits of ODS
– uniform communication mechanisms and access
to shared resources
– Construction
• Heterogeneous components
30
Challenges
• Security
–
–
–
–
Confidentiality
integrity
availability
Example
• A doctor might request access to hospital patient
data
• In electronic commerce and banking, users send
their credit card numbers across the internet
• Current security challenges
– Denial of service attack
– Security of mobile code (Email attachment)
31
Challenges
• Scalability
– Controlling the cost of the physical resources
• Does the system remain effective given the
expected growth
– Controlling the performance loss
• www.amzon.com is more than one computer
– Preventing the software resources running out
• IP addressees :32 bits to 128
• Avoiding performance bottleneck
– Decentralization of data/information
32
Challenges
• Failure handling
– Detecting failure
• Checksum can be used to detect corrupted
data
• System crash
– Masking
• Retransmission
• Redundant storage
– Tolerating failure
• Exception handling (timeout when waiting
for web source)
34
Challenges
• Failure handling
– Recovery from failure
• Roll back
– Redundancy
(services can be made tolerate failures)
• Redundant routes in network
• Replication of DNS tables in multiple
domain name servers
• Database replication
– Availability
• Measure of the proportion of the time a
server is available
• User may move to another computer if the
one they were using fails
35
Challenges
• Concurrency
• Data structure for bids is accessed very frequently
near the deadline
– One client request a time –Throughput ?
– Resources can be encapsulated in an object and
that invocations are executed in concurrent threads
– Avoidance of deadlock
• Transparency
– Concealing the heterogeneous and distributed
nature of the system so that it appears to the
user like one system
36
Challenges :Transparency
• Access transparency: enables local and remote
resources to be accessed using identical operations.
• Location transparency: enables resources to be
accessed without knowledge of their location.
• Concurrency transparency: enables several
processes to operate concurrently using shared
resources without interference between them.
• Replication transparency: enables multiple instances
of resources to be used to increase reliability and
performance without knowledge of the replicas by
users or application programmers.
• Failure transparency: enables the concealment of
faults, allowing users and application programs to
complete their tasks despite the failure of hardware
or software components.
37
Challenges :Transparency
• Mobility transparency: allows the movement of
resources and clients within a system without
affecting the operation of users or programs.
• Performance transparency: allows the system to be
reconfigured to improve performance as loads vary.
• Scaling transparency: allows the system and
applications to expand in scale without change to the
system structure or the application algorithms.
38
Reading Assignment
1
Interview of Fred B. Schneider on “Distributed Computing”
'It's all distributed computing to me...
http://www.computerworld.com/hardwaretopics/hardware/gridcomputing/st
ory/0,10801,104937,00.html
2
From the text book answer
1.7
1.8
1.9
39
More yet to Come !
40
Useful Research
Papers
41
Papers
• Eric A. Brewer. Lessons from Giant-Scale Services.
IEEE Internet Computing, 5(4): pp.46-55
• A. D. Birrell and B. J. Nelson. Implementing remote
procedure calls. ACM Transactions on Computer
Systems 2(1):39-59, February 1984
• P.V. Mockapetris and K.J. Dunlap. Development of the
Domain Name System. Proceedings of ACM
SIGCOMM 1988
42
Papers
•
Leslie Lamport. Time, Clocks, and the Ordering of Events in a Distributed
System. Communications of the ACM, 21(7):558-565, July 1978
•
Yasushi Saito, Brian Bershad, and Henry Levy. Manageability, Availability
and Performance in Porcupine: A Highly Scalable Cluster-Based Mail
Service. Proc. of the 17th ACM Symp. on Operating Systems Principles,
December 1999
•
D. B. Terry, et al. Managing Update Conflicts in Bayou, a Weakly
Connected Replicated Storage System. Proceedings of the Fifteenth ACM
Symposium on Operating Systems Principles, 1995
•
John Ousterhout. The Role of Distributed State. CMU Computer Science: A
25th Anniversary Commemorative, ACM Press Anthology Series, R. Rashid
(Ed.), July 1991
43
Papers
•
George Candea et al. Microreboot -- A Technique for Cheap Recovery.
Proc. 6th Symposium on Operating Systems Design and Implementation
(OSDI), San Francisco, CA, December 2004
•
Stuart Staniford, Vern Paxson, and Nicholas Weaver. How to Own the
Internet in Your Spare Time. Proceedings of the 2002 USENIX Security
Symposium, San Francisco, CA, August 2002.
•
Butler W. Lampson. Hints for computer system design. Proceedings of the
Ninth ACM Symposium on Operating Systems Principles (SOSP).
44