Distributed

Multimedia
CHAPTER 5
Distributed and
Parallel Computing
 In this chapter, we turn to the
problem of coordinating multiple
computers and processors.

Overview:
 Distributed Computing
• Client/server system
• Peer-to-peer system
 Parallel Computing
 System Model
Distributed
Computing
 Definition

• These are interconnected groups of independent

computers that need to communicate with each other to
get a job done.
• They may need to coordinate to provide a service, share
data, or even store data sets that are too large to fit on a
single machine.
• We will look at different roles computers can play in
distributed systems and learn about the kinds of
information that computers need to exchange in order to
work together.
 Introduction
• A distributed system is a network of autonomous computers
that communicate with each other in order to achieve a goal.
• The computers in a distributed system are independent and do
not physically share memory or processors.
• They communicate with each other using messages, pieces of
information transferred from one computer to another over a
network.
• Messages can communicate many things: computers can tell
other computers to execute a procedures with particular
arguments, they can send and receive packets of data, or send
signals that tell other computers to behave a certain way.
 Distributed Computing

• Computers in a distributed system can have different

roles.
• A computer's role depends on the goal of the system and
the computer's own hardware and software properties.
• There are two predominant ways of organizing computers
in a distributed system.
• The first is the client-server architecture, and the second is
the peer-to-peer architecture.
 Client/Server Systems

• The client-server architecture is a way to dispense a

service from a central source.
• There is a single server that provides a service, and
multiple clients that communicate with the server to
consume its products.
• In this architecture, clients and servers have different jobs.
• The server's job is to respond to service requests from
clients, while a client's job is to use the data provided in
response in order to perform some task.
Client/Server Systems
 Client/Server Systems

• The concepts of client and server are powerful

functional abstractions.
• A server is simply a unit that provides a service,
possibly to multiple clients simultaneously, and a
client is a unit that consumes the service.
• The clients do not need to know the details of how
the service is provided, or how the data they are
receiving is stored or calculated, and the server does
not need to know how the data is going to be used.
 Client/Server Systems
• On the web, we think of clients and servers as being on
different machines, but even systems on a single machine can
have client/server architectures.
• For example, signals from input devices on a computer need to
be generally available to programs running on the computer.
• The programs are clients, consuming mouse and keyboard input
data.
• The operating system's device drivers are the servers, taking in
physical signals and serving them up as usable input.
 Disadvantages of client-server
systems
• The server is a single point of failure. It is the only
component with the ability to dispense the service. There can
be any number of clients, which are interchangeable and can
come and go as necessary. If the server goes down, however,
the system stops working. Thus, the functional abstraction
created by the client-server architecture also makes it vulnerable
to failure.
• Another drawback of client-server systems is that resources
become scarce if there are too many clients. Clients increase
the demand on the system without contributing any computing
resources. Client-server systems cannot shrink and grow with
changing demand.
 Peer-to-peer Systems

• The term peer-to-peer is used to describe distributed systems

in which labor(work) is divided among all the components
of the system.
• All the computers send and receive data, and they all
contribute some processing power and memory.
• As a distributed system increases in size, its capacity of
computational resources increases.
• In a peer-to-peer system, all components of the system
contribute some processing power and memory to a
distributed computation.
 Peer-to-peer Systems
• Division of labor among all participants is the identifying
characteristic of a peer-to-peer system.
• This means that peers need to be able to communicate
with each other reliably.
• In order to make sure that messages reach their intended
destinations, peer-to-peer systems need to have an
organized network structure.
• The components in these systems cooperate to maintain
enough information about the locations of other
components to send messages to intended destinations.
 Peer-to-peer Systems

• The most common applications of peer-to-peer

systems are data transfer and data storage.
• For data transfer, each computer in the system
contributes to send data over the network.
• If the destination computer is in a particular
computer's neighborhood, that computer helps send
data along.
 Peer-to-peer Systems

• For data storage, the data set may be too large to fit
on any single computer, or too valuable to store on
just a single computer.
• Each computer stores a small portion of the data,
and there may be multiple copies of the same data
spread over different computers.
• When a computer fails, the data that was on it can be
restored from other copies and put back when a
replacement arrives.
 Peer-to-peer Systems

• Skype, the voice- and video-chat service, is an example of

a data transfer application with a peer-to-peer architecture.
• When two people on different computers are having a
Skype conversation, their communications are broken up
into packets of 1s and 0s and transmitted through a peer-
to-peer network.
• This network is composed of other people whose
computers are signed into Skype. Each computer knows
the location of a few other computers in its
neighborhood.
 Peer-to-peer Systems

• A computer helps send a packet to its destination by

passing it on a neighbour, which passes it on to some
other neighbour, and so on, until the packet reaches its
intended destination.
• Skype is not a pure peer-to-peer system.
• A scaffolding network of supernodes is responsible for
logging-in and logging-out users, maintaining information
about the locations of their computers, and modifying the
network structure to deal with users entering and leaving.
Parallel Computing
 Definition

• Parallel or Concurrent computation is when a single

program is executed by multiple processors with a
shared memory, all working together in parallel in
order to get work done faster.
 Introduction

• Computers get faster and faster every year. In 1965,

Intel co-founder Gordon Moore made a prediction
about how much faster computers would get with
time.
• Based on only five data points, he extrapolated that
the number of transistors that could inexpensively be
fit onto a chip would double every two years.
• Almost 50 years later, his prediction, now called
Moore's law, remains startlingly accurate.
 Parallel Computation

• Despite this explosion in speed, computers aren't able to

keep up with the scale of data becoming available. By
some estimates, advances in gene sequencing technology
will make gene-sequence data available more quickly than
processors are getting faster.
• In other words, for genetic data, computers are become
less and less able to cope with the scale of processing
problems each year, even though the computers
themselves are getting faster.
 Parallel Computation

• To circumvent physical and mechanical constraints

on individual processor speed, manufacturers are
turning to another solution: multiple processors.
• If two, or three, or more processors are available,
then many programs can be executed more quickly.
While one processor is doing one aspect of some
computation, others can work on another. All of
them can share the same data, but the work will
proceed in parallel.
 Parallel Computation
• In order to be able to work together, multiple processors need
to be able to share information with each other.
• This is accomplished using a shared-memory environment.
• The variables, objects, and data structures in that environment
are accessible to all the processes.
• The role of a processor in computation is to carry out the
evaluation and execution rules of a programming language. In a
shared memory model, different processes may execute
different statements, but any statement can affect the shared
environment.
 System Model

Definition:
Abstract descriptions of systems whose requirements
are being analyzed
 System Model

• System modeling helps the analyst to understand the functionality

of the system and models are used to communicate with
customers
• Different models present the system from different perspectives
 External perspective showing the system’s context or
environment
 Behavioral perspective showing the behavior of the system
 Structural perspective showing the system or data architecture
 Model types

 Data processing model showing how the data is processed

at different stages
 Composition model showing how entities are composed
of other entities
 Architectural model showing principal sub-systems
 Classification model showing how entities have common
characteristics
 Stimulus/response model showing the system’s reaction
to events
 Three types of system models
• Physical models: capture the hardware composition of a system in terms
of computers and other devices and their interconnecting network;
• Architecture models: defines the components of the system, the way they
interact, and the way the are deployed in a network of computers
– client-server models (many variants)
– peer processes (P2P)
– spontaneous networks (mobility)
• Fundamental models: formal description of the properties that are
common to all architecture models
– interaction models
– failure models
– security models
 Context models

• Context models are used to illustrate the

boundaries of a system

• In some cases, the boundary between a system

and its environment is relatively clear.

• Architectural models show the a system and its

relationship with other systems
The context of an ATM system
Security
system
Branch
Account
accounting
database
system
Auto-teller
system
Branch
Usage
counter
database
system
Maintenance
system
 Process models
• Process models show the overall process and the processes
that are supported by the system

• Data flow models may be used to show the processes and

the flow of information from one process to another

• This involves specifying the equipment required, finding

and choosing a supplier, ordering the equipment, taking
delivery, and testing the equipment.(dotted lines for the
system boundary).
 Process (activity) model
Delivery
note

Equipment Checked Delivery

spec. spec. note
Specify Validate Accept Check
Get cost
equipment specification delivery of delivered
estimates
requir ed equipment items
Spec. +
supplier + Installation
estima te Order
Equipment notification instructions
spec. Supplier list
Place
Supplier Find Choose equipment Install
database suppliers supplier equipment
Order order
details +
Blank order Installation
form acceptance

Accept
delivered
Checked and equipment
signed order form

Equipment
details

Equipment
database
 Behavioral models
• Behavioral models are used to describe the overall behavior of
a system

• Two types of behavioral model are shown here:

• Data Flow models (DFD) that show how data is
processed as it moves through the system
• State machine models (STD) that show the systems
response to events

• Both of these models are required for a description of the

system’s behavior
 Data-processing models (DFD)
• Data flow diagrams are used to model the system’s data
processing

• By nature it is part of many analysis methods

• Simple notation that customers can understand

• Show end-to-end processing of data

• Four symbols only for DFD, Source/Sink (Square), Data

flow(arrow), process (oval), and Data store (rectangle)
 Order processing DFD
Checked and
Completed Signed Signed Send to signed order
order form order form order form supplier + order
Order
notification
details + Complete Validate Record
blank order form order order
order form Adjust
Order available
Signed budget
details order form
Order
amount
+ account
details
Orders Budget
file file
 Data flow diagrams
• DFDs model the system from a functional perspective

• Tracking and documenting how the data associated with a process is

helpful to develop an overall understanding of the system

• Data flow diagrams may also be used in showing the data exchange
between a system and other systems in its environment

• DFD do not try to represent conditional processing or loops in it, it is

simply show the flow of data
 Insulin pump DFD

Blood
Blood parameters
Blood sugar Blood sugar Blood sugar
sensor analy sis level

Insulin
requir ement
computa tion
Pump contr ol
Insulin commands Insulin Insulin
Insulin requir ement
deli very
pump contr oller
 Object models
• Object models describe the system in terms of object classes, if they
are developed during requirements analysis, they would simplify the
transition to object oriented design and programming.
• An object class is an abstraction over a set of objects with common
attributes and the services (operations) provided by each object
• Various object models may be produced
• Inheritance models- how object are related to each other
• Aggregation models- how object form other object
• Interaction models- how object interact with each other
 Object models
• Natural ways of reflecting the real-world entities manipulated by
the system, such entities as cars, aircraft, books… etc

• More abstract entities are more difficult to model using this

approach, such library, medical record systems.

• Object class identification is recognized as a difficult process

requiring a deep understanding of the application domain

• Object classes reflecting domain entities are reusable across

systems
 Inheritance models
• Organize the domain object classes into a hierarchy, it is
not an easy task, so analyst has to understand in detail the
domain in which the system is to be installed.

• Classes at the top of the hierarchy reflect the common

features of all classes

• Object classes inherit their attributes and services from one

or more super-classes, these may then be specialized as
necessary
 Object models and the UML
• The UML is a standard representation devised by the developers
of widely used object-oriented analysis and design methods.

• It has become an effective standard for object-oriented modelling.

• Notation
• Object classes are rectangles with the name at the top, attributes in
the middle section and operations in the bottom section;
• Relationships between object classes (known as associations) are
shown as lines linking objects;
• Inheritance is referred to as generalisation and is shown ‘upwards’
rather than ‘downwards’ in a hierarchy.
 The Unified Modelling
Language,UML
• Has nine different notations State
State
Class
Use Case Diagrams
Diagrams
Use
UseCase
Case Diagrams State
State
Use
UseCase
Case Diagrams
Diagrams Object
Sequence Diagrams Diagrams
Diagrams
Diagrams
Diagrams Diagrams
Diagrams

Scenario
Scenario State
State
Collaboration
Diagrams Component
Diagrams
Diagrams
Diagrams Models Diagrams
Diagrams

Scenario
Scenario
Component
Component
Statechart
Diagrams Deployment
Diagrams
Diagrams
Diagrams
Diagrams Activity Diagrams
Diagrams
 Library class hierarchy
Library item
Catalogue number
Acquisition date
Cost
Type
Status
Number of copies
Acquire ()
Catalogue ()
Dispose ()
Issue ()
Return ()

Published item Recorded item

Title Title
Publisher Medium

Book Magazine Film Computer

program
Author Year Director
Edition Issue Date of release Version
Publication date Distributor Platform
ISBN
 User class hierarchy
Libr ary user
Name
Address
Phone
Registration #
Register ()
De-r egister ()

Reader Borrower
Affiliation Items on loan
Max. loans

Staff Student
Department Major subject
Department phone Home address
 Fundamental models
 Properties shared by all architecture models
 communicates by sending messages across a network
 requirements of performance, reliability, and security
 Fundamental models
 abstracts over unnecessary details
 used to address questions like
– what are the most important entities in the system?
– how do they interact?
- what are the characteristics that affect their individual and collective behaviour?
 The purpose of fundamental models
- to make explicit all relevant assumptions about the system we are modeling
-to find out what is generally feasible and not feasible under the given assumptions
 Two variants of the
interaction model
• Synchronous distributed systems
- the time to execute each step of a process has known
lower and upper bounds
- each message transmitted over a channel is received
within a known bounded time
- each process has a local clock whose drift rate from real
has a known bound
 Two variants of the
interaction model
• Asynchronous distributed systems
- the time to execute each step of a process can take
arbitrarily long
- each message transmitted over a channel can be
received after an arbitrarily long time
- each process has a local clock whose drift rate
from real time can be arbitrarily large
 Ordering of events
• distributed coordination protocols have a need for ordering of events in
time (“happened before” relationship)
– events: sending and receiving messages
– example: update of replicated data must generally be done in the
same order in all replica
– difficult to use physical clocks in computers for coordination
(e.g.,. clock values in messages)
- have limited time resolution and ticks with different rates (clock drift)
- basic properties of message exchange limit the accuracy of the
synchronization of clocks in a DS [Lamport 78]
 A failure model
 Is a definition of in which way failures may occur in distributed
systems
 Provides a basis for understanding the effects of failures
 Definition of the failure model of a service enables construction
of a new service that hides the faulty behaviour of the service it
builds upon
- example: TCP on top of IP
• – TCP: reliable byte-stream service
• – IP: unreliable datagram service
 Specification of failure model

• Specification of failure models requires a way to describe

failures
• One approach is to classify failure types:
Omission failures
Arbitrary failures
Timing failures
 Omission failure (1)

• A process or channel fails to perform actions that it is

supposed to do
Failure class Affects Description

Fail-stop Process Process halts and remains halted.

Other processes may detect this
state.
Crash Process Process halts and remains halted.Other
processes may not be able to detect
this state.
Omission Channel A message inserted in an outgoing message
buffer never arrives in the other end’s
incoming buffer.
 System Model

Send m Receive m

communication channel

outgoing message buffer incoming message buffer

 Omission failure (2)

Failure class Affects Description

Send-omission Process A process completes a

send-operation, but
the message is not put
into the outgoing
message buffer.
Receive-omission Process A message is put into a
process’s incoming
message buffer, but the
process does not
receive it.
 Omission failure (3)
• Usual assumption that a server has “fail-stop” failure model
• the server crashes in a “nice” way
- it halts completely
- other servers may detect it has failed
• if the server nevertheless fails in a different way, the software
that uses the server, may fail in unpredictable ways
• It is difficult to detect omission failures for processes in an
asynchronous system
 Arbitrary failures (Byzantine
failures)
• Process or channel may exhibit arbitrary behavior when failing,
 send/receive arbitrary messages at arbitrary intervals
 a process may halt or perform “faulty” steps
 a process may omit to respond now and then
• By adopting a byzantine failure model, we can attempt to make systems
that are “ultra-reliable” (handles HW failures, and provide guaranteed
response times)
 control systems in air planes
 patient monitoring systems
 robot control systems
 control systems for nuclear power plants
 Timing failure

• Applicable in synchronous distributed systems.

 responses that are not available to clients in a specified
time interval
 timing guarantees requires guaranteed access to resources
when they are needed
• Example : control and monitoring systems, multimedia
systems
 Timing failure

Failure class Effects Description

Clock Process Process’s local clock exceeds the

bounds on its rate of drift from real
time
Performance Process Process exceeds the bounds on the
interval between two processing steps

Performance Channel A message’s transmission takes longer

than the stated bounds
End of Chapter 5

Thank You!
 Exercise In Class

• 2 persons in a group:
Discuss:
• A) What is Video-On-Demand (VoD)?
• B) What is Video-on-Reservation (VoR)?
• C) Difference between VoD vs. VoR.