Distributed Systems

System Models

1
Purpose of Models
Models help us
 understand
 predict
 control / construct / explore

Distributed Systems ccsejc, November 2003 2

Good Models
A model consists of attributes and
rules
 rules can be expressed as
mathematical and logical formulas
A model yields insight
 helps recognize unsolvable problems
 helps avoid slow or expensive
solutions

Distributed Systems ccsejc, November 2003 3

Distributed System Models
Architectural Models
 placement of parts
 relationship of parts
Fundamental Models
 formal description of system
properties common in all architectural
models

Distributed Systems ccsejc, November 2003 4

Architectural Model
Service Layers
 Platform
 operating system, hardware
 supplies system programming interface
 Middleware
 masks heterogeneity
 supplies application programming
interface
 provides services (e.g., naming, security,
transactions, event notification, etc.)

Distributed Systems ccsejc, November 2003 5

Service Layers

Applications, services

Middleware

Operating system

Platform

Computer and network hardware

Distributed Systems ccsejc, November 2003 6

Architectural Model
System Architectures
 Client/Server Model
 Multiple Servers
 Proxy Servers and Caches
 Peer Processes

Distributed Systems ccsejc, November 2003 7

Client/Server Model

Client invocation invocation Server

result result
Server

Client
Key:
Process: Computer:

Distributed Systems ccsejc, November 2003 8

Client/Server Model
Remains the most widely used
Services may be provided by
multiple servers
Partitioned or replicated service-
related objects

Distributed Systems ccsejc, November 2003 9

Client/Server Model
Partition provides
 increased performance
 increased availability
 increased fault-tolerance
But requires replica coordination /
consistency preservation

Distributed Systems ccsejc, November 2003 10

Multiple Servers
Service

Server
Client

Server

Client
Server

Distributed Systems ccsejc, November 2003 11

Proxy Servers and Caches
Cache
 a close store of recently used data
 considerably increase performance in
many applications
 but requires cache coherence protocols
Proxy Server
 a shared cache of resources
 most commonly used for web access

Distributed Systems ccsejc, November 2003 12

Proxy Server

Client Web
server
Proxy
server

Client Web
server

Distributed Systems ccsejc, November 2003 13

Peer Processes
Peer Processes
 processes that play similar roles
 no absolute distinction between
client/server
 may still assume client/server roles
from time to time
 Whiteboard Architecture
 Group Communication / Multicast

Distributed Systems ccsejc, November 2003 14

Peer Processes

Application Application

Coordination Coordination
code code

Application

Coordination
code

Distributed Systems ccsejc, November 2003 15

Client-Server Model
Variations
Mobile Code
Mobile Agents
Network Computers
Thin Clients
Mobile Devices and Spontaneous
Networking

Distributed Systems ccsejc, November 2003 16

Mobile Codes
Code will be executed on the client
machine instead of the server
machine
Applets are well-known and widely
used example of mobile code

Distributed Systems ccsejc, November 2003 17

Web Applets
a) client request results in the downloading of applet code

Client Web
Applet code server

b) client interacts with the applet

Web
Client Applet server

Distributed Systems ccsejc, November 2003 18

Server Push Model
Server initiates dialogue
“pushes” information to the client
Client needs application that
listens for server pushes

Distributed Systems ccsejc, November 2003 19

Mobile Agents
A running program that travels
between computers in a network
Carries out tasks on someone’s
behalf
Advantages
 local access everywhere
 reduction in communication cost
Potential security threat
Distributed Systems ccsejc, November 2003 20
Network Computers
All files are stored remotely in file
servers
Minimum software installed locally;
most are downloaded from servers
Any local disk used mainly as
cache

Distributed Systems ccsejc, November 2003 21

Thin Clients
Refers to software layer that
supports window-based user
interface on a computer that is
local to user while executing
applications on remote computer
Does not run own code
Programs are run by a powerful
compute server

Distributed Systems ccsejc, November 2003 22

Thin Client

Compute server
Network computer or PC

Thin network Application

Client Process

Distributed Systems ccsejc, November 2003 23

Spontaneous Networking
Describes the form of distribution
that integrates mobile devices and
other devices into a given network
Term used to encompass
applications that involve the
connection of both mobile and
non-mobile devices to networks in
an informal manner
Distributed Systems ccsejc, November 2003 24
Spontaneous Networking
Key Features
 easy connection to a local network
 easy integration with local services
Security Problems
 limited connectivity
 security and privacy

Distributed Systems ccsejc, November 2003 25

Spontaneous Networking
Discovery Services – accepts and
store details of services that are
available on the network and
respond to queries from clients
 Registration Service
 Lookup Service

Distributed Systems ccsejc, November 2003 26

Spontaneous Networking
(hotel)

Music
service Alarm
gateway service
Internet

Hotel wireless
network
Discovery
service
Camera

TV/PC Guests
Laptop PDA
devices

Distributed Systems ccsejc, November 2003 27

Interfaces and Objects
Server processes and objects
export interfaces
 define services
Several objects may be
encapsulated by server process
 pass reference to clients
 clients can use remote invocation

Distributed Systems ccsejc, November 2003 28

Design Requirements
Performance Issues
Quality of Service
Use of Caching and Replication
Dependability Issues

Distributed Systems ccsejc, November 2003 29

Performance Issues
Responsiveness (Availability)
 server load / performance
 communication / middleware / OS
delays
 implies
 few software layers
 small quantities transferred between
client/server

Distributed Systems ccsejc, November 2003 30

Performance Issues
Throughput
 rate at which computational work is done
Balancing Computational Load
 may reduce stress on heavily loaded servers
 task / process migration
 complex operation and incurs huge overhead
 feasible only for long-running task

Distributed Systems ccsejc, November 2003 31

Quality of Service
Non-Functional Requirements
 Reliability
 Security
 Adaptability
 Performance

Distributed Systems ccsejc, November 2003 32

Quality of Service
QoS often refers to timeliness
 Predictability and sufficient efficiency
 Deadlines
 Hard Real-Time
 e.g., reacting to sensor in nuclear plants
 Soft Real-Time
 e.g., multimedia streams

Distributed Systems ccsejc, November 2003 33

Use of Caching &
Replication
Cache Coherence / Consistency

Distributed Systems ccsejc, November 2003 34

Dependability Issues
Fault-Tolerance
 Replication in space / time
Security

Distributed Systems ccsejc, November 2003 35

Fundamental Models
Communicating Processes
(message passing)
 fundamental property of distributed
system

Distributed Systems ccsejc, November 2003 36

Fundamental Models
Interaction Model
 limitation of delays, differing notions
of time
Failure Model
 fault classification and tolerance
Security
 possible attacks, attack-resistant
design

Distributed Systems ccsejc, November 2003 37

Interaction Model
Distributed Algorithm
 describes behavior and state of processes
in a distributed system
 definition of steps to be taken by the
involved processes, including transmission
of messages
Execution speed is hard to predict
State is hard to define due to failures

Distributed Systems ccsejc, November 2003 38

Interaction Model
Performance of Communication
Channels
 Latency
 Receipt Time – Send Time
 Bandwidth
 possibly shared
 Jitter
 variations in delivery time

Distributed Systems ccsejc, November 2003 39

Interaction Model
Computer Clocks and Timing
Events
 Clock synchronization
 local clocks differ due to clock drift rate
 Logical clocks
 Outside reference source (e.g., GPS)
Clock Drift Rate – refers to the relative amount
that a computer clock differs from a perfect
reference clock

Distributed Systems ccsejc, November 2003 40

Interaction Model
Two Variants
 Synchronous Distributed Systems
 Asynchronous Distributed Systems

Distributed Systems ccsejc, November 2003 41

Interaction Model
Synchronous Systems
 time to execute each step of process has
lower and upper bounds
 each message transmitted is received
within a bounded time
 each process has a local clock whose drift
rate from real time has bound
 Problem: assumptions often not precise

Distributed Systems ccsejc, November 2003 42

Interaction Model
Asynchronous Systems
 No bounds on execution speed,
message delays, clock drift rates
 Example: Internet

Distributed Systems ccsejc, November 2003 43

Interaction Model
Event Ordering
 System execution can be described
as a series of events
 Issues:
 time stamping events
 perfect synchronization impossible in a
loosely-coupled system
 logical time – ordering without clock
synchronization

Distributed Systems ccsejc, November 2003 44

Real-Time Ordering of
Events
send receive receive
X
1 m1 4
m2
send
receive
2 3 Physical
Y
receive time

send
Z
receive receive

m3 m1 m2
A
receive receive receive
t1 t2 t3

Distributed Systems ccsejc, November 2003 45

Failure Model
Processes and communication
links may fail
Different ways of failing
 Omission failures
 Arbitrary failures
 Timing failures

Distributed Systems ccsejc, November 2003 46

Processes and Channels

process p process q

send m receive

Communication channel
Outgoing message buffer Incoming message buffer

Distributed Systems ccsejc, November 2003 47

Omission Failures
Process Omission Failure
 crash (fail-silent) – requires timeout
 fail-stop
Communication Omission Failure
 failure to deliver a message
 network transmission error or lack of
buffer space
 send-omission / receive-omission /
channel-omission

Distributed Systems ccsejc, November 2003 48

Arbitrary Failures
also called Byzantine failures
worst possible failure
exhibit malicious behavior
in process: omits intended processing
steps; takes unintended steps
on communication medium: message
corruption; spawning / multiple delivery

Distributed Systems ccsejc, November 2003 49

Timing Failures
applicable in synchronous
distributed systems
 limits on execution time, delivery
time, clock drift rates
missed deadline
 most critical in real-time systems

Distributed Systems ccsejc, November 2003 50

Omission & 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 or Process/channel exhibits arbitrary behaviour: it may
(Byzantine) channel send/transmit arbitrary messages at arbitrary times,
commit omissions; a process may stop or take an
incorrect step.
Distributed Systems ccsejc, November 2003 51
Timing Failures
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.

Distributed Systems ccsejc, November 2003 52

Reliable Communication
Validity
 any message in outgoing message
buffer is eventually delivered to
incoming message buffer
Integrity
 message received is identical to one
sent; no messages are delivered
twice

Distributed Systems ccsejc, November 2003 53

Security Model
There is a need to secure
 Processes
 Channels
 Encapsulated Objects (resources,
etc.)

Distributed Systems ccsejc, November 2003 54

Protecting Objects
Access rights Object
invocation

Client
result Server

Principal (user) Network Principal (server)

verify identity of client, check access rights

verify identity of server for response

Distributed Systems ccsejc, November 2003 55

Securing Processes
Problems
 open network
 exposed interfaces

Distributed Systems ccsejc, November 2003 56

The Enemy
is able to
 send any message to any process
 read or copy any message between a
pair of processes
Copy of m

The enemy
m’
Process p m Process q
Communication channel

Distributed Systems ccsejc, November 2003 57

Threats to Processes
False Identities
 not difficult to forge source address of
a message
 server must know identities of clients
to decide whether to reject requests
 clients need to validate server
responses

Distributed Systems ccsejc, November 2003 58

Threats to Comm.
Channels
Eavesdropping
Message Altering
Message Injection
Copy and Replay of Messages
Solution: Secure Channels

Distributed Systems ccsejc, November 2003 59

Defeating Threats
Cryptography
 hiding a message’s contents
Authentication
 proof of identity
 usually involves encryption as well
Secure Channels
 based on both cryptography and
authentication

Distributed Systems ccsejc, November 2003 60

Secure Channels

Principal A Principal B

Process p Secure channel Process q

Distributed Systems ccsejc, November 2003 61

Other Possible Threats
Denial of Service
 enemy interferes with activities of
authorized users by making excessive
and pointless invocations that result
to resource overload
Mobile Code
 process receives and executes
program code from elsewhere

Distributed Systems ccsejc, November 2003 62

Summary
Architectural Fundamental
Model Model
 Middleware  Interaction Model
 Client/Server  Failure Model
Model  Security Model
 Design
Requirements
 Quality of Service

Distributed Systems ccsejc, November 2003 63