Distributed and Parallel Computer Systems

CSC 423
Fall 2021-2022

Lecture 4
Fundamental Models

Instructor
Dr / Ayman Soliman
➢ Contents

1) Fundamental Models – Formal Description

o Interaction model

o Failure model

o Security model

2) Summary

8/11/2021 Dr/ Ayman Soliman 2

 ❑ Fundamental Models
➢ Fundamental Models are concerned with the main entities in the
system,

➢ and how they interact,

➢ and the characteristics that affect their individual and collective

behavior.

➢ All Architectural Models composed of processes that communicate

with each other by sending messages over a computer networks.

8/11/2021 Dr/ Ayman Soliman 3

 ❑ Fundamental Models
➢ Models addressing time synchronization, message delays, failures,
security issues are addressed as:

1) Interaction Model – deals with performance and the difficulty of

setting of time limits in a distributed system.

2) Failure Model – specification of the faults that can be exhibited

by processes

3) Secure Model – discusses possible threats to processes and

communication channels.
8/11/2021 Dr/ Ayman Soliman 4
 ❑ 1- Interaction Model
➢ Distributed systems composed of many processes interact like:

o Multiple server processes may cooperate with one another to

provide service like domain name service.

o A set of peer processes may cooperate with one another to

achieve a common goal, for example voice\video conferencing
system.

8/11/2021 Dr/ Ayman Soliman 5

 ❑ 1- Interaction Model
➢ The processes interact by passing messages, resulting in:
o Communication (information flow)
o Coordination (synchronization and ordering of activities) between
processes.

➢ Two significant factors :

o Communication performance.
o It is impossible to maintain a single global notion of time.

8/11/2021 Dr/ Ayman Soliman 6

 ❑ 1- Interaction Model: Performance of Communication Channel

➢ The communication channel realized in a variety of ways:

o Streams

o Simple message passing over a network.

8/11/2021 Dr/ Ayman Soliman 7

 ❑ 1- Interaction Model: Performance of Communication Channel
➢ Communication over a computer network has performance
characteristics:
o Latency:
▪ A delay between the start of a message’s transmission from
one process to the beginning of receipt by another.
o Bandwidth:
▪ The total amount of information that can be transmitted over
in a given time.
o Jitter:
▪ The variation in the time taken to deliver a series of messages.
It is very relevant to multimedia data.
8/11/2021 Dr/ Ayman Soliman 8
 ❑ 1- Interaction Model: Computer clocks and timing events
➢ Each computer in a DS has its own internal clock, which can be used
by local processes to obtain the value of the current time.

➢ However, even if two processes read their clock at the same time,
their local clocks may supply different time.

o This is because computer clock drift from perfect time and their
drift rates differ from one another.

8/11/2021 Dr/ Ayman Soliman 9

 ❑ 1- Interaction Model: Computer clocks and timing events
➢ Even if the clocks on all the computers in a DS are set to the same
time initially, their clocks would eventually vary quite significantly
unless corrections are applied.

o There are several techniques to correct time on computer clocks.

o For example, computers may use radio receivers to get readings

from GPS (Global Positioning System).

8/11/2021 Dr/ Ayman Soliman 10

 ❑ 1- Interaction Model: Two variants of the interaction model
➢ Synchronous DS – hard to achieve:
o The time take to execute a step of a process has know lower and upper
bounds.
o Each message transmitted over a channel is received within a known
bounded time.
o Each process has a local clock whose drift rate from real time has known
bound.
o Use time out to detect the failure of a process

➢ Asynchronous DS: There is NO bounds on:

o Process execution speeds
o Message transmission delays
o Clock drift rates.
8/11/2021 Dr/ Ayman Soliman 11
 ❑ 1- Interaction Model: Event Ordering
➢ The execution of a system can be described in terms of events and
their ordering

➢ In many DS applications we are interested in knowing whether an

event occurred before, after, or concurrently with another event at
another processes.

➢ Consider a mailing list with users X, Y, Z, and A.

8/11/2021 Dr/ Ayman Soliman 12

 ❑ Real-time ordering of events
send receive receive
X
1 m1 4
m2
send
2 3 receive Physical
Y
receive time

send
Z
receive receive

m3 m1 m2
A
receive receive receive
t1 t2 t3

8/11/2021 Dr/ Ayman Soliman 13

 ❑ Inbox of User A looks like:
From Subject
Z Re: Meeting
X Meeting
Y Re: Meeting

➢ Due to independent delivery in message delivery, message may be delivered in

different order.
➢ If messages m1, m2, m3 carry their time t1, t2, t3, then they can be displayed to
users accordingly to their time ordering.
➢ BUT clocks cannot be synchronized perfectly across a distributed system (e.g:
logical ordering)
8/11/2021 Dr/ Ayman Soliman 14
 ❑ 2- Failure Model
➢ In a DS, both processes and communication channels may fail .

➢ Types of failures:

1) Omission Failure

2) Arbitrary Failure

3) Timing Failure

8/11/2021 Dr/ Ayman Soliman 15

 ❑ Processes and channels
process p process q

send m receive

Communication channel
Outgoing message buffer Incoming message buffer

➢ Communication channel produces an omission failure if it does not

transport a message from outgoing message buffer to incoming
message buffer.

known as “dropping messages”

8/11/2021 Dr/ Ayman Soliman 16
 ❑ Processes and channels
process p process q

send m receive

Communication channel
Outgoing message buffer Incoming message buffer

➢ “dropping messages” and is generally caused by lack of buffer space

at the receiver or a network transmission error.

8/11/2021 Dr/ Ayman Soliman 17

 ❑ 1) and 2) Omission and arbitrary failures
Class of failure 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 at the
other end’s incoming message buffer.
Send-omission Process A process completes a send but the message is not put in its outgoing
message buffer.
Receive-omission Process A message is put in a process’s incoming message buffer, but that process
does not receive it.
Arbitrary Process Process/channel exhibits arbitrary behaviour: it may send/transmit
(Byzantine) or channel arbitrary messages at arbitrary times, a process may stop or take an
incorrect step.

8/11/2021 Dr/ Ayman Soliman 18

 ❑ 3) Timing failures
➢ It is applicable in synchronous distributed system where time limit is
set on process execution time.

Class of Failure Affects 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 steps.

Performance Channel A message’s transmission takes longer than the stated bound.

8/11/2021 Dr/ Ayman Soliman 19

 ❑ Masking Failures
➢ It is possible to construct reliable services from components that
exhibit failures.
o For example, multiple servers that hold replicas of data can
continue to provide a service when one of them crashes.

➢ can mask the failure of the components on which it depends:

o Checksums are used to mask corrupted messages.

8/11/2021 Dr/ Ayman Soliman 20

 ❑ 3- Security Model
➢ The security of a DS can be achieved by:

o Securing the processes and the channels used in their interactions

o Protecting the objects that they encapsulate against unauthorized

access.

8/11/2021 Dr/ Ayman Soliman 21

 ❑ Protecting Objects: Objects and principals
Access rights Object
invocation

Client
result Server

Principal (user) Network Principal (server)

➢ Use “access rights” that define who is allowed to perform operation

on an object.
➢ The sever should verify the identity of the (user) and checking that
they have sufficient access rights to perform the requested operation
on the particular object, rejecting those who do not.
8/11/2021 Dr/ Ayman Soliman 22
 ❑ The enemy
Copy of m

The enemy
m’
Process p m Process q
Communication channel

➢ An enemy can send any process or reading/copying message

between a pair of processes

➢ Threats form a potential enemy: threats to processes, threats to

communication channels, and denial of service.
8/11/2021 Dr/ Ayman Soliman 23
 ❑ Defeating security threats: Secure channels

Principal A Principal B

Process p Secure channel Process q

➢ Encryption and authentication are used to build secure channels.

➢ Each of the processes knows the identity of the principal on whose

behalf the other process is executing and can check their access
rights before performing an operation.
8/11/2021 Dr/ Ayman Soliman 24
 ❑ Summary
➢ Most DSs are arranged accordingly to one of a variety of
architectural models:
o Client-Server
▪ Clients and a Single Sever, Multiple Servers, Proxy Servers
with Cache, Peer Model
o Alternative Client-Sever models driven by:
▪ Mobile code, mobile agents, network computers, thin clients,
mobile devices and spontaneous networking
➢ Fundamental Models – formal description
o Interaction, failure, and Security models.
8/11/2021 Dr/ Ayman Soliman 25
8/11/2021 Dr/ Ayman Soliman 26