Distributed Systems

A. F. M. Minhazur Rahman
Lecturer
Deparment of CSE
Rajshahi University of Engineering & Technology

5/31/24 Distributed Systems 1

 Introduction
• Definition: Collection of autonomous computing elements that
appears to its users as a single coherent system

• Characteristic features

• Autonomous computing elements, also referred to as nodes, be they

hardware devices or software processes.

• Single coherent system: users or applications perceive a single system

⇒ nodes need to collaborate.

5/31/24 Distributed Systems 2

 Collection of autonomous nodes
• Independent Behaviour:
• Each node is autonomous and will thus have its own notion of time
• There is no global clock ⇒ Leads to fundamental synchronization and
coordination problems.

• Collection of nodes
• Managing group membership can be exceedingly difficult
• How to know that you are indeed communicating with an authorized
(non)member?

5/31/24 Distributed Systems 3

 Organization
• Overlay network
• Each node in the collection communicates only with other nodes in the
system, its neighbors.
• The set of neighbors may be dynamic, or may even be known only
implicitly (i.e., requires a lookup).
• Overlay types
• Structured: each node has a well-defined set of neighbours with whom
it can communicate (tree, ring).
• Unstructured: each node has references to randomly selected other
nodes from the system.

5/31/24 Distributed Systems 4

 Coherent system
• Coherence: The collection of nodes as a whole operates the
same, no matter where, when, and how interaction between a
user and the system takes place.
• Examples
• An end user cannot tell where a computation is taking place
• Where data is exactly stored should be irrelevant to an application
• If or not data has been replicated is completely hidden
• Coherence is not always possible
• At any time only a part of the distributed system may fail
• Hiding partial failures and their recovery is often very difficult and in
general impossible to hide.

5/31/24 Distributed Systems 5

 Middleware

• Middleware:
• A separate layer of software
• Logically placed on top of the respective operating systems of the
computers that are part of the system

5/31/24 Distributed Systems 6

 Advantages
• Economics
• Grosch's Law: Computing power of a CPU∝(Price of a CPU)2
• No longer effective
• Cost effective solution: Equip large number of cheap CPU's together
• Achieve better price/performance ratio using microprocessors than
mainframes
• Speed
• More total computing power than a mainframe
• Inherently Distributed Applications
• Supermarket chain with local stores, inventories, sales, decisions
• Reliability and Fault Tolerance
• Single chip/machine failure will not crash the whole system
• Ability to continue work in the presence of failures
• Continuously available
5/31/24 Distributed Systems 7
 Advantages (cont’d)
• Incremental Growth
• Adding more processors to the system to increase the system’s
performance
• Scalability
• Scalable distributed systems can gracefully handle more users, data, or
requests by adding additional resources (like servers or storage)
• Horizontal scaling (scale-out): Adding more machines to the system to
distribute the workload
• Vertical scaling (scale-up): Increasing the power of individual
machines (more CPU, RAM, etc.)
• Resource Sharing
• Users access a common database and share expensive peripherals

5/31/24 Distributed Systems 8

 Disadvantages (cont’d)
• Complexity
• Difficulty in building robust software

• Networking
• Message loss, overloading, saturation, failure

• Security
• Ease of sharing might lead to data leakage

5/31/24 Distributed Systems 9

 Design Goals
• Support sharing of resources

• Distribution transparency

• Openness

• Scalability

5/31/24 Distributed Systems 10

 Supporting Resource Sharing
• Cheaper to have a single high-end reliable storage facility be
shared than having to buy and maintain storage for each user
separately

• Connecting users and resources also makes it easier to

collaborate and exchange information

• Success of file-sharing peer-to-peer networks like BitTorrent

5/31/24 Distributed Systems 11

 Distribution Transparency
• Distribution Transparency: hide the fact that its processes and
resources are physically distributed across multiple computers
possibly separated by large distances

5/31/24 Distributed Systems 12

 Types of Distribution Transparency
Transparency Description
Hide differences in data representation and how an
Access
object is accessed
Location Hide where an object is located
Hide that an object may be moved to another
Relocation
location while in use

Migration Hide that an object may move to another location

Replication Hide that an object is replicated

Hide that an object may be shared by several
Concurrency
independent users
Failure Hide the failure and recovery of an object

5/31/24 Distributed Systems 13

Types of Distribution Transparency (cont’d)
• Access Transparency
• Hiding differences in data representation and the way that objects can
be accessed
• Hide differences in machine architecture
• Reach agreement on how data is to be represented by different
machines and operating systems
• Example: Hide the fact that different machine can have different
operating systems, each having their own file-naming conventions.
Differences in naming conventions, differences in file operations, or
differences in how low-level communication with other processes is to
take place, are examples of access issues that should preferably be
hidden from users and applications.

5/31/24 Distributed Systems 14

Types of Distribution Transparency (cont’d)
• Location Transparency
• Users cannot tell where an object is physically located in the system
• Naming plays an important role in achieving location transparency
• Example: Assigning only logical names.
• An example of a such a name is the uniform resource locator (URL)
[Link]
• Gives no clue about the actual location of Prentice Hall’s main Web server
• Relocation Transparency
• Hide that an object may be moved to another location while in use
• The entire site of Prentice Hall may have been moved from one data center to
another, yet users should not notice
• Migration Transparency
• Offered by a distributed system when it supports the mobility of processes
and resources initiated by users
• Example
• Mobile phones: regardless whether two people are actually moving, mobile phones will
allow them to continue their conversation

5/31/24 Distributed Systems 15

Types of Distribution Transparency (cont’d)
• Replication Transparency
• Hiding the fact that several copies of a resource exist or
• Several processes are operating in some form of lockstep mode so that one can
take over when another fails
• Concurrency Transparency
• Hide that an object may be shared by several independent users
• Example: Two independent users may each have stored their files on the
same file server or may be accessing the same tables in a shared database. In
such cases, it is important that each user does not notice that the other is
making use of the same resource.
• Important issue: Concurrent access to a shared resource should leave a
resource in a consistent state.
• Consistency can be achieved through locking mechanisms, transaction etc.
• Failure Transparency
• A user or application does not notice that some piece of the system fails to
work properly
• User should not notice system recovery from failure

5/31/24 Distributed Systems 16

 Degree of Distribution Transparency
Aiming at full distribution transparency may be too much
• There are communication latencies that cannot be hidden
• Completely hiding failures of networks and nodes is
(theoretically and practically) impossible
• You cannot distinguish a slow computer from a failing one
• You can never be sure that a server actually performed an operation
before a crash
• Full transparency will cost performance, exposing distribution of
the system
• Keeping replicas exactly up-to-date with the master takes time
• Immediately flushing write operations to disk for fault tolerance

5/31/24 Distributed Systems 17

 Openness of Distributed Systems
• Openness: Be able to interact with services from other open systems,
irrespective of the underlying environment

• Systems should conform to well-defined interfaces

• Components should adhere to standard rules that describe the syntax and semantics
of what those components have to offer
• Systems should easily interoperate
• Two implementations of systems or components from different manufacturers can co-
exist and co-operate together relying on each other’s services as specified by a
common standard
• Systems should support portability of applications
• Application developed for a distributed system A can be executed, without
modification, on a different distributed system B that implements the same interfaces
as A
• Systems should be easily extensible
• Easy to add new components or replace existing ones without affecting those
components that stay in place

5/31/24 Distributed Systems 18

 Scalability of Distributed Systems
• Scalability of a system can be measured along at least three
different dimensions
• Size scalability
• Geographical scalability
• Administrative scalability

5/31/24 Distributed Systems 19

 Size Scalability
• Size scalability: Add more users and resources to the system
without any noticeable loss of performance.
• Problems that need to be solved:
• Many services are centralized (single server running on a specific
machine in the distributed system)
• Centralized services become a bottleneck when they need to process an
increasing number of requests.
• Three root cause of bottleneck
• The computational capacity, limited by the CPUs
• The storage capacity, including the I/O transfer rate
• The network between the user and the centralized service

5/31/24 Distributed Systems 20

 Size Scalability (cont’d)
• Things to avoid:
• Centralized services
• A single server for all users
• Centralized data
• Example: A single on-line telephone book
• Having a single database might saturate all the communication lines into and out
of it
• Centralized algorithm
• Collecting and transporting all the input and output information is a bad idea
• Messages would overload part of the network
• Need to adopt Decentralized algorithms

5/31/24 Distributed Systems 21

 Size Scalability (cont’d)
• Decentralized Algorithm

• 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

5/31/24 Distributed Systems 22

 Geographical Scalability
• Geographical scalability: Users and resources may lie far apart,
but the fact that communication delays may be significant is
hardly noticed.
• Problems that need to be solved:
• Distributed system was mainly designed for LAN communication
• LAN communication is mostly synchronous (blocking)
• Synchronous communication works fine on LAN because communication latency
is at worst a few hundred microseconds
• Hundreds of milliseconds in case WAN
• WAN communication is inherently less reliable than LAN
• WAN have very limited facility for multipoint communication
• LANs often support efficient broadcasting mechanisms
• Extremely useful for discovering components and services

5/31/24 Distributed Systems 23

 Administrative Scalability
• Administrative scalability: System is easily managed even if it
spans many independent administrative organizations
• Problems that need to be solved:
• Conflicting policies with respect to
• Resource usage (and payment),
• Management
• Security

5/31/24 Distributed Systems 24

Scaling Techniques: Hiding Communication Latency
• Hide communication latencies

• Make use of asynchronous communication

• Have separate handler for incoming response

• Problem: not every application fits this model

5/31/24 Distributed Systems 25

Scaling Techniques: Hiding Communication Latency
• Hide communication latencies: Moving computations to client

5/31/24 Distributed Systems 26

Scaling Techniques: Partitioning and Distribution
• Paritioning and Distribution

• Taking a component, splitting it into smaller parts

• Spreading those parts across the system.

• Example:
• Internet Domain Name System (DNS) : Name resolution via recursive resolver
• World Wide Web (WWW): Web is physically partitioned and distributed across
a few hundred million servers, each handling a number of Web documents

5/31/24 Distributed Systems 27

Scaling Techniques: Partitioning and Distribution

5/31/24 Distributed Systems 28

Scaling Techniques: Partitioning and Distribution

5/31/24 Distributed Systems 29

Scaling Techniques: Replication and Caching
• Replication
• Generally a good idea to actually replicate components across a
distributed system
• Replication increases availability, balances the load between
components leading to better performance.
• In geographically widely dispersed systems, having a copy nearby can
hide much of the communication latency problems mentioned before.

• Caching
• Caching is a special form of replication
• Decision is made by owner of resource

5/31/24 Distributed Systems 30

Scaling Techniques: Replication and Caching
• Applying replication is easy, except for one thing

• Having multiple copies (cached or replicated), leads to inconsistencies:

modifying one copy makes that copy different from the rest.

• Always keeping copies consistent and in a general way requires global

synchronization on each modification.

• Global synchronization precludes large-scale solutions.

• Observation: If we can tolerate inconsistencies, we may reduce the

need for global synchronization, but tolerating inconsistencies is
application dependent.

5/31/24 Distributed Systems 31

 Pitfalls of Distributed System
False assumptions that everyone makes when developing a
distributed application for the first time:

• 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

5/31/24 Distributed Systems 32

High Performance Distributed Computing
• Definition: High Performance Distributed Computing system
combines multiple, often dispersed, computing resources to
handle complex tasks efficiently

• Key Features: Uses parallel processing, distributed memory,

and networked communication for high speed and capacity

• Applications: Essential in scientific research, data analysis,

machine learning, and large-scale simulations

5/31/24 Distributed Systems 33

 Parallel Computing
• Observation: High-performance distributed computing started
with parallel computing

Multiprocessor system Multicomputer system

5/31/24 Distributed Systems 34

 Distributed Shared Memory Systems
• Observation: Multiprocessors are relatively easy to program in comparison
to multicomputers, yet have problems when increasing the number of
processors (or cores)

• Solution: Try to implement a shared-memory model on top of a

multicomputer

• Example: Through virtual-memory techniques Map all main-memory

pages (from different processors) into one single virtual address space. If
process at processor A addresses a page P located at processor B, the OS
at A traps and fetches P from B, just as it would if P had been located on
local disk.

• Problem: Performance of distributed shared memory could never compete

with that of multiprocessors, and failed to meet the expectations of
programmers. It has been widely abandoned by now.

5/31/24 Distributed Systems 35

 Cluster Computing
• Essentially a group of high-end systems connected through a
LAN
• Homogeneous: same OS, near-identical hardware
• Single managing node
• Used for parallel programming in which a single (compute intensive)
program is run in parallel on multiple machines

5/31/24 Distributed Systems 36

 Grid Computing
• Grid Computing: A form of distributed computing that involves
a large number of geographically dispersed, loosely coupled
computers working together to solve large-scale problems
• Heterogeneous
• Dispersed across several organizations
• Can easily span a wide-area network

• Note: To allow for collaborations, grids generally use virtual

organizations. In essence, this is a grouping of users (or better:
their IDs) that will allow for authorization on resource
allocation.

5/31/24 Distributed Systems 37

 Cloud Computing
• Cloud Computing: A technology that provides on-demand access
to a shared pool of computing resources, including servers,
storage, databases, networking, software, and applications, over
the internet.

The organization of clouds

5/31/24 Distributed Systems 38
 Cloud Computing
Four layers of cloud computing:
• Hardware: Processors, routers, power and cooling systems.
Customers normally never get to see these.
• Infrastructure: Deploys virtualization techniques. Evolves
around allocating and managing virtual storage devices and
virtual servers.
• Platform: Provides higher-level abstractions for storage and
such. Example: Amazon S3 storage system offers an API for
(locally created) files to be organized and stored in so-called
buckets.
• Application: Actual applications, such as office suites (text
processors, spreadsheet applications, presentation applications).
Comparable to the suite of apps shipped with OSes.
5/31/24 Distributed Systems 39
 References
[1] A. S. Tanenbaum, Distributed Operating Systems, 1st edition.
Pearson, 1994.
[2] M. van Steen and A. S. Tanenbaum, Distributed Systems, 3rd
edition. CreateSpace Independent Publishing Platform, 2017.
[3] Slides for Distributed Systems, 3rd edition.

5/31/24 Distributed Systems 40

 Thank You

5/31/24 Distributed Systems 41