DISTRIBUTED SYSTEMS

Principles and Paradigms

Second Edition
ANDREW S. TANENBAUM
MAARTEN VAN STEEN

Chapter 1
Introduction
* Modified by Prof. Rivalino Matias, Jr.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 History
• From 1945 to approx. 1985, computers were big
and very expensive to buy, maintain and operate.
• Few organizations had computers, which worked
independently.
• In mid of 1980’s, two technology advances
changed this scenario:
o Development of high-capacity microprocessors (8, 16, 32, and 64
bits)
o Invention of computer networks (LAN, MAN, WAN, …)
• As a result, it became possible to connect
multiple computers and build networked systems
(or distributed systems).
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Definition of a Distributed System (1)

A distributed system is:

A collection of independent
computers that appears to its
users as a single coherent
system.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Definition of a Distributed System (1)

A distributed system is:

A collection of independent
computers that appears to its
users as a single coherent
system.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Definition of a Distributed System (2)
This definition has very important aspects:
• A DS is composed of autonomous computers.
• The users (people or programs) don’t know they are
dealing with multiple computer systems.
▪ This means that the autonomous systems must cooperate!
▪ How to establish this cooperation is a key aspect of developing
distributed systems.
• Also, there is no assumption on the computer types of the
autonomous systems (e.g., mainframes to sensor nodes)
• Likewise, there is no assumption on the way the
autonomous computers are interconnected.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Definition of a Distributed System (3)
Important characteristics of DS:
• The differences between the computers and the way
they are interconnected are, mostly, hidden from users.
▪ The same applies to the internal organization of DS.
• Users (people and programs) can interact with the DS in
a consistent and uniform way, regardless where these
interactions occur.
• Increase the whole system scalability must be easy, as a
result of using independent computers.
• Availability is also an expected property, although some
parts may be temporarily offline.
▪ The faulty and replaced parts should not be perceived by users.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Definition of a Distributed System (4)

Figure 1-1. A distributed system organized as middleware. The

middleware layer extends over multiple machines, and offers
each application the same interface.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Goals
• Making resources available.
• Distribution transparency.
• Openness.
• Scalability.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Goals
• Making resources available.
▪ This is the main goal of a distributed systems.
▪ Among the many reasons, economy is the most obvious.
▪ To connect users and resources makes information sharing and
collaboration easier. The Internet is an example.
▪ As connectivity and data/information sharing increase, security becomes
even more important.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Goals
• Making resources available.
• Distribution transparency.
▪ A distributed system that can present itself to users (people
and programs) as a single computer system is called
transparent.
▪ There are many types of transparency in distributed systems
(see next slide).

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Transparency in a Distributed System

Figure 1-2. Different forms of transparency in a

distributed system (ISO, 1995).
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Goals
• Making resources available.
• Distribution transparency.
• Openness.
▪ An open DS is a system that offers its services according to standard
rules (syntax and semantics).
▪ Usually, the services are specified by means of interfaces, which are
commonly described in an IDL (interface description language).
▪ An adequate interface specification is complete and neutral.
▪ Interoperability and portability are also important.
➢ The former indicates the extent to which two systems or components
implementations, from different providers, may coexist and work.
➢ The latter characterizes the extent an application developed for a DS A can
be executed, w/o modification, on a DS B that implements the same
interface implemented by A.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Goals
• Making resources available.
• Distribution transparency.
• Openness.
• Scalability.
• This is a very important property of a DS.
• The scalability can be measured considering three dimensions: size,
geographic, and administrative.
• Sometimes, meeting two or more of these dimensions imply in loss of
performance.
• Growing a system for each one of these dimensions require to solve
different scalability problems (see next slide).

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Scalability Problems

Figure 1-3. Examples of scalability limitations.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Scalability Problems
Characteristics of decentralized algorithms:
• No machine has complete information about the
system state.
• Machines make decisions based only on local
information.
• Failure of one machine does not ruin the
algorithm.
• There is no implicit assumption that a global
clock exists.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Geographic scalability
• Many systems were developed to execute in a
LAN, and thus are based on synchronous
communication.
▪ Building interactive applications to be executed over WANs requires a
different and careful design.
• Communication over WANs is inherited not
reliable, and most of times peer-to-peer.
▪ e.g., broadcast as used in LANs is not an effective option!
• Sharing resources over WANs is most of time
not feasible.
• Different administrative domains create important
challenges (rules, policies, security, …).
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Scaling Techniques (1)
• Mostly, scalability problems appear as
performance issues caused by limited capacity of
servers and networks.
• There are three techniques to scale systems:
▪ Hiding communication latency, distribution, and replication.
• Hiding latency: avoid as much as possible to
wait, synchronously, for remote replies.
▪ Adopting asynchronous communication is an option,
▪ however, it is an issue for interactive applications; which
can be mitigated moving part of the server-side processing
to the client side.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Scaling Techniques (1)

Figure 1-4. The difference between letting (a) a server

or (b) a client check forms as they are being filled.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Scaling Techniques (2)
• Distribution: Divide a component in smaller
parts and distribute them.
▪ This can solve problems of limited processing and storage
capacity.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Scaling Techniques (2)

Figure 1-5. An example of dividing the DNS

name space into zones.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Scaling Techniques (3)
• Replication: distribute multiple instances of the
same component.
▪ Help to increase the availability and to balance the system
load.
▪ For systems distributed over a large geographic area, having
a copy of service/data closer helps to hide latency.
▪ Cache is a special form of replication.
▪ Consistency is an issue in replication of certain
data/components, and keep all replicas synchronized can be
a hard problem with large number of replicas connected
through WANs.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Pitfalls when Developing
Distributed Systems
False assumptions made by first time developer:
• The network is reliable.
• The network is secure.
• The network is homogeneous.
• The topology does not change.
• Latency is zero.
• Bandwidth is infinite.
• Transport cost is zero.
• There is one administrator.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Types of Distributed Systems

Some types of DS are:

• Distributed computing systems.
▪ e.g.: Clusters and Grids
• Distributed information systems.
▪ e.g., Transaction processing systems (TPS), Enterprise
application integration (EAI).
• Distributed pervasive systems.
▪ e.g., Household systems, Health Care Systems, Sensor
networks.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Cluster Computing Systems

Figure 1-6. An example of a cluster computing system.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Grid Computing Systems

Figure 1-7. A layered architecture for grid computing systems.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Transaction Processing Systems (1)

Figure 1-8. Example primitives for transactions.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Transaction Processing Systems (2)

Characteristic properties of transactions:

• Atomic: To the outside world, the transaction
happens indivisibly.
• Consistent: The transaction does not violate
system invariants.
• Isolated: Concurrent transactions do not
interfere with each other.
• Durable: Once a transaction commits, the
changes are permanent.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Transaction Processing Systems (3)

Figure 1-9. A nested transaction.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Transaction Processing Systems (4)

Figure 1-10. The role of a TP monitor in distributed systems.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Enterprise Application Integration

Figure 1-11. Middleware as a communication facilitator in

enterprise application integration.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Distributed Pervasive Systems
Requirements for pervasive systems

• Embrace contextual changes.

• Encourage ad hoc composition.
• Recognize sharing as the default.

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Electronic Health Care Systems (1)
Questions to be addressed for health care systems:
• Where and how should monitored data be
stored?
• How can we prevent loss of crucial data?
• What infrastructure is needed to generate and
propagate alerts?
• How can physicians provide online feedback?
• How can extreme robustness of the monitoring
system be realized?
• What are the security issues and how can the
proper policies be enforced?

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
Electronic Health Care Systems (2)

Figure 1-12. Monitoring a person in a pervasive electronic health

care system, using (a) a local hub or
(b) a continuous wireless connection.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Sensor Networks (1)

Questions concerning sensor networks:

• How do we (dynamically) set up an
efficient tree in a sensor network?
• How does aggregation of results take
place? Can it be controlled?
• What happens when network links fail?

Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Sensor Networks (2)

Figure 1-13. Organizing a sensor network database, while storing

and processing data (a) only at the operator’s site or …
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5
 Sensor Networks (3)

Figure 1-13. Organizing a sensor network database, while storing

and processing data … or (b) only at the sensors.
Tanenbaum & Van Steen, Distributed Systems: Principles and Paradigms, 2e, (c) 2007 Prentice-Hall, Inc. All rights reserved. 0-13-239227-5