Distributed Systems
Lecture 1
Professor Louise E. Moser
Spring 2014
Course Administrative Details
n Lectures: T Th 11am-12:15pm Phelps 2524
n Discussion Sections: Th 5-5:50pm Phelps 1444
F 10-10:50am Phelps 1440
n Office Hours:
□ Prof Louise Moser: T Th 2-3:30pm HFH 2164
□ TA Miguel Lastras Montano: M W 3-4pm, Th 4-5pm Phelps 1435
TA Harichandan Pulagam: M W 1-2pm, F 11-12noon Phelps 1435
n Text: Distributed Systems: Principles and Paradigms
A. S. Tanenbaum and M. van Steen, Prentice Hall, Second Edition
n Midterm: Tue, May 6, 11-12:15pm, Final: Wed, June 11, 12-3pm
n Grading: Midterm 15%, Final 35%, Assignments 35%
Class Attendance / Participation 15%
(Lectures and Discussion Sections)
2
Definition of a Distributed System
n A Distributed System is a collection of two or more
independent computers that appears to its users as
a single coherent system
n A distributed system is typically organized as middleware
that extends across multiple computers and that offers
each application the same interface
3
Goals of a Distributed System
n Overall Goal: Connecting resources and users
n Additional Goals:
¨ Transparency
¨ Openness
¨ Scalability
4
Different Forms of Transparency
Transparency Description
Hide differences in data representations and how
Access
a resource is accessed
Location Hide where a resource is located
Hide that a resource may be moved to another
Relocation
location
Hide that a resource may be moved to another
Migration
location while it is being used
Hide that a resource may be available on several
Replication
distinct computers
Hide that a resource may be shared by several
Concurrency
competing users at the same time
Failure Hide the failure and recovery of a resource
5
Degree of Transparency
Complete transparency might not be desirable or possible
n Users might be located in different countries - distribution
is apparent and might not be something you want to hide
n Complete transparency can result in extra performance costs
□ Keeping Web caches exactly up-to-date with the master copy
□ Immediately copying the results of write operations to disk
n Hiding faults in hardware and software might not be
theoretically or practically possible
□ You cannot distinguish a slow computer from one that has failed
□ You cannot be sure that a computer has actually performed
an operation before it crashed
6
Openness
n An open distributed system is one that interacts with
services from other open systems and requires
□ Well-defined interfaces and protocols
□ Portability of applications
□ Interoperability of systems
n An open distributed system is one that is independent
of the heterogeneity of the underlying environment
□ Languages
□ Operating systems
□ Hardware
7
Implementing Openness
n Policies specified by the applications and the users
□ What level of consistency do we require for client-cached data?
□ Which operations do we allow downloaded code to perform?
□ Which QoS requirements do we adjust for different applications?
□ What level of security/privacy do we require for communication?
n Mechanisms implemented by the middleware and
the operating system
□ Allow dynamic setting of caching policies, preferably per cached item
□ Support different levels of trust for downloaded code
□ Provide adjustable QoS parameters per data stream
□ Offer different encryption algorithms
8
Scalability
n Limitations of scalability due to centralization
9
Scalability
n Characteristics of decentralized algorithms
□ No machine has complete information about the state
of the distributed system
□ Machines make decisions based on local information
□ No implicit assumption that a global clock exists
□ Failure of one machine does not affect the operation of
the algorithm
10
Scalability Metrics
n Many developers of distributed systems use the term
“scalable” without making clear how their systems scale
n At least three scalability metrics exist
□ Size scalability – number of users or processes or machines
□ Geographical scalability – maximum distance between nodes
□ Administrative scalability – number of administrative domains
11
Scaling Techniques
n Distribution: Partition the data and computations
across multiple machines
□ Move computations to clients (Java applets)
□ Decentralized naming services (DNS)
□ Decentralized information systems (WWW)
n Caching: Allow client processes to access local copies
□ Web caches (browser or proxy)
□ File caching (client or server)
n Replication: Make copies of the data available on
different machines (mainly for fault tolerance)
□ Replicated file servers
□ Replicated databases
□ Mirrored Web sites
12
Example Scaling Technique
n Domain Name System (DNS) in the Internet is hierarchically
structured into several hundred top-level domains
¨ Domains correspond to organizational boundaries, not physical
boundaries
¨ Domains are partitioned hierarchically in a tree structure into
subdomains, etc.
¨ To create a new domain, need permission from the manager
above in the tree
¨ Domain is named by a path, e.g., [Link]
n Generic DNS names
¨ com (commercial)
¨ edu (educational)
¨ gov (US government)
¨ mil (US military)
¨ int (international organizations)
¨ net (network providers)
¨ org (non-profit organizations)
13
Example Scaling Technique
(a) Server checks the form for each client, or
(b) Client checks the form, which is more scalable
because server can then serve more clients
14
Pitfalls in Developing Distributed Systems
n False assumptions made by a first-time developer of
a distributed system
□ Network is homogeneous
□ Network is secure
□ Network is reliable
□ Topology does not change
□ Latency is zero
□ Bandwidth is infinite
□ Transport cost is zero
□ There is one administrator
15
Types of Distributed Systems
n Distributed Computing Systems
¨ Cluster Computing Systems
¨ Grid Computing Systems
n Distributed Information Systems
¨ Transaction Processing Systems
¨ Enterprise Application Integration (EAI)
n Pervasive Distributed Systems
¨ e-Healthcare Systems
¨ Sensor Networks
16
Cluster Computing Systems
n A cluster is a collection of workstations or PCs
connected by a local-area network (LAN)
n Each node runs the same operating system (OS)
n Example: Master/slave system where the slaves
(compute nodes) operate in parallel
17
Grid Computing Systems
n A grid is a federation of computing systems
¨ Each system might be in a different administrative domain
¨ Each system might use different software, hardware,
network technology
n A layered architecture for a grid computing system
18
Transaction Processing Systems
n A transaction is a group of program statements that
are intended to be executed together (i.e., atomically)
n Standard primitives for transactions
19
Transaction Processing Systems
n Traditionally, transactions operate on a single local database
n Such transactions are expected to satisfy the following
ACID properties:
□ Atomic: To the outside world, the transaction happens indivisibly,
i.e., all of the operations of the transaction are performed, or
none of them is performed
□ Consistent: The transaction does not violate system invariants
□ Isolated: Concurrent transactions do not interfere with each other;
they can be serialized
□ Durable: Once a transaction commits, the changes are made
permanent, by writing them to disk
n Note: It is very difficult to guarantee the ACID properties for
distributed transactions that operate on multiple databases
and that span multiple enterprises 20
Transaction Processing Systems
n Nested transactions with subtransactions
n Subtransactions typically operate in parallel on
different databases
n Durability applies only to the top-level transactions
21
Transaction Processing Systems
n Transaction Processing (TP) monitor allows
an application to access multiple servers/databases,
using the transaction model
22
Enterprise Application Integration
n In Enterprise Application Integration (EAI), a distributed
application is separated into independent components
¨ In particular, processing components are separated from
database components
n These components need to be integrated and to communicate
with one another
¨ Middleware facilitates this integration and communication in EAI
23
Pervasive Distributed Systems
n A pervasive distributed system typically comprises small,
battery-powered, mobile computing devices with
wireless connections
¨ Part of our surroundings, lacks human administrative control
¨ Devices must automatically discover their environment and
other devices within it
n Pervasive distributed systems requirements:
□ Adapt to contextual changes
□ Enable ad hoc composition
□ Recognize sharing as the default
24
Example: e-Healthcare Systems
n Questions to be addressed in an e-healthcare system
□ Where and how should patient data from monitoring
devices be stored?
□ How can we prevent loss of crucial patient data?
□ What infrastructure is needed to generate and
propagate alerts to the patient, caregivers, healthcare
professionals?
□ How can physicians provide online feedback?
□ What are the security and privacy issues and
how can the proper policies be enforced?
□ How can robustness of the e-healthcare system
be realized? 25
e-Healthcare Systems
n Health monitoring of a patient using
(a) A local hub
(b) A continuous wireless connection
26
Example: Sensor Networks
n A sensor network typically comprises hundreds to
thousands of small battery-powered nodes (each with
a sensor) that use wireless communication
□ Typically, used for measurement and surveillance
□ Efficiency is a prime design criterion due to limited processing
and memory resources, communication capabilities, and
power supplies
n Questions concerning data processing within a
sensor network
□ How do we set up an efficient means of communication?
□ How do we aggregate and consolidate results?
□ What happens when a network link fails?
27
Sensor Networks
n A sensor network database with storage and
processing of data
(a) Only at the
operator’s site
(b) Only at the
sensors
28