System Models

Detailed Study Notes

CS5429 — Distributed Systems

Lecture 02: System Models

Source: Lecture slides by Adeesha Wijayasiri, adapted from

Distributed Systems: Concepts and Design, 5th Edition
by George Coulouris, Jean Dollimore, Tim Kindberg and Gordon Blair
1. Introduction to System Models
A “model” is a way of describing and reasoning about a distributed system, stripping away
unnecessary detail so that the essential properties of the system can be understood. This lecture
introduces three complementary ways of modelling a distributed system.
• Physical models – consider a distributed system purely in terms of the hardware that
makes it up — the computers and devices that constitute the system and how they are
interconnected — without going into details of the specific technologies used.
• Architectural models – describe a system in terms of the computational and
communication tasks performed by its computational elements (processes, objects,
components, services). The two most commonly used architectural styles are client-server
and peer-to-peer.
• Fundamental models – take a more abstract perspective, used to describe solutions to
individual issues that are faced by almost all distributed systems. There are three
fundamental models:
– Interaction model — concerned with the performance of communication and the
difficulty of keeping a global notion of time.
– Failure model — concerned with the ways in which a system may fail and how
those failures can be tolerated.
– Security model — concerned with how the system can be protected against attack.

Difficulties and Threats for Distributed Systems

Before designing or analysing a distributed system, it helps to understand the inherent difficulties
that all such systems share:
• Widely varying modes of use – different components, applications and users place very
different (and sometimes conflicting) demands on the system, e.g. in terms of reliability,
security, scalability and performance.
• Wide range of system environments – a distributed system must accommodate a huge
variety of hardware, operating systems, networks, programming languages and data
formats.
• Internal problems – include the lack of a global clock (clock drift across machines), the
difficulty of determining the precise current state of remote processes, and
inconsistencies arising from concurrent updates.
• External threats – include attacks on the confidentiality, integrity and availability of
data and services — e.g. eavesdropping, message tampering, denial of service and
unauthorised access.

2. Physical Models
A physical model is a representation of the underlying hardware elements of a distributed system
that abstracts away from the architectural details of specific computer and networking technologies
employed.
Baseline Physical Model
The baseline physical model represents a distributed system as an extensible set of computer nodes
interconnected by a computer network, providing the facilities needed for nodes to pass messages
to one another. The word “extensible” indicates that nodes can be added to (or removed from) the
system over time.

Three Generations of Distributed Systems

Generation 1 — Early Distributed Systems
Early distributed systems emerged from the late 1970s onward and were characterised by:
• Typically 10 to 100 nodes interconnected by a local area network (LAN).
• Limited connectivity to the wider Internet.
• Support for only a small range of services, for example:
– Shared local printers
– File servers
– Email
– File transfer across the Internet (e.g. via FTP)
Generation 2 & 3 — Internet-Scale and Contemporary Distributed Systems
As networking matured, distributed systems became internet-scale: an extensible set of nodes
interconnected not only by local networks but by a network of networks — the Internet itself.
Contemporary distributed systems may comprise hundreds of thousands of nodes, and have given
rise to several new computing paradigms:
• Mobile computing – laptops, smartphones and tablets that move from location to
location. This mobility creates the need for additional capabilities such as service
discovery (finding nearby services) and support for spontaneous interoperation
(connecting automatically with the local environment).
• Ubiquitous computing – small, often embedded, computing devices are present in
everyday objects and environments, frequently operating in the background without the
user being explicitly aware of them.
• Cloud computing – large pools of computing and storage resources (nodes) that are
accessed over the network and that, collectively, provide a given set of services on
demand.
Table 1 — Summary comparison of physical models across the three generations of distributed
systems
Aspect Early Distributed Systems Internet-Scale Contemporary
Scale Small Large Ultra-large
Heterogeneity Limited — typically Significant, in terms of Added dimensions,
relatively homogeneous platforms, languages and including radically different
configurations middleware styles of architecture
Openness Not a priority Significant priority, with a Major research challenge —
range of standards existing standards not yet
introduced able to embrace complex
 Aspect Early Distributed Systems Internet-Scale Contemporary
systems
Quality of service In its infancy Significant priority, with a Major research challenge —
range of services introduced existing services not yet able
to embrace complex systems

3. Architectural Models
An architectural model describes a system in terms of the computational and communication tasks
performed by its computational elements. The major design concerns are to make the system
reliable, manageable, adaptable and cost-effective.

Architectural Elements
Describing a distributed system’s architecture amounts to answering four key questions:
• What are the entities that are communicating in the distributed system?
• How do they communicate — what communication paradigm is used?
• What (potentially changing) roles and responsibilities do they have in the overall
architecture?
• How are they mapped onto the physical distributed infrastructure — what is their
placement?
Each of these questions is addressed in the following subsections.

3.1 Communicating Entities

There are two complementary perspectives on what the “communicating entities” in a distributed
system actually are.
From a system perspective
The entities that communicate are processes. In some cases it is more useful to talk about even
finer-grained entities:
• Nodes – particularly in the context of sensor networks, where the physical device (e.g. a
sensor) is the natural unit of interest.
• Threads – the actual independently-schedulable endpoints of communication within a
process.
From a programming perspective
The natural unit of decomposition is the object (in object-oriented systems) or, more generally, a
component or service:
• Computation consists of a number of interacting objects, representing natural units of
decomposition for the problem domain at hand.
• Objects are accessed via interfaces, with an associated Interface Definition Language
(IDL), which describes the operations an object supports without revealing its internal
implementation.
3.2 Communication Paradigms
Three broad communication paradigms are used to connect the communicating entities of a
distributed system: interprocess communication, remote invocation, and indirect communication.
3.2.1 Interprocess Communication
Interprocess communication refers to the relatively low-level support for communication between
processes in distributed systems. It includes:
• Message-passing primitives.
• Direct access to the API offered by Internet protocols, i.e. socket programming.
• Support for multicast communication (sending a message to multiple recipients at once).
3.2.2 Remote Invocation
Remote invocation refers to calling a remote operation, procedure or method as though it were
local. It is typically implemented using request-reply protocols — a message-passing pattern that
underlies client-server computing.
• Remote Procedure Call (RPC) – allows procedures in processes on remote computers
to be called as if they were procedures in the local address space. RPC supports client-
server computing: servers offer a set of operations through a service interface, and clients
call these operations directly as though they were available locally.
• Remote Method Invocation (RMI) – strongly resembles RPC, but operates in a world
of distributed objects rather than procedures. RMI offers tighter integration with the
object-oriented programming framework, allowing objects on different computers to
invoke each other’s methods.
3.2.3 Indirect Communication
In RPC and RMI, the senders and receivers of messages must coexist at the same time and are
aware of each other’s identities — they are tightly coupled. Indirect communication relaxes these
constraints in two important ways:
• Space uncoupling – senders do not need to know the identity of the receiver(s) they are
sending to.
• Time uncoupling – senders and receivers do not need to exist (or be active) at the same
time.
There are several key techniques used to achieve indirect communication:
• Group communication – a message sent to a group of recipients (a multicast); the
sender does not need to know the identities of the individual group members.
• Publish-subscribe systems – also called distributed event-based systems. Publishers
distribute information items of interest, called events, to what may be a large number of
consumers (subscribers). This is a one-to-many style of communication.
• Message queues – offer a point-to-point service, as opposed to the one-to-many style of
publish-subscribe systems. Producer processes can send messages to a specified queue,
and consumer processes can either receive messages from the queue directly or be
notified of new arrivals.
 • Tuple spaces – also known as generative communication. Processes can place arbitrary
items of structured data, called tuples, into a persistent tuple space. Other processes can
read or remove tuples from the tuple space by specifying patterns of interest. Because the
tuple space is persistent, readers and writers do not need to exist at the same time.
• Distributed Shared Memory (DSM) – an abstraction used for sharing data between
processes that do not share physical memory. It gives processes the illusion of operating
on a common shared address space.
Table 2 — Relationship between communicating entities and communication paradigms
Communicating Entities Communication
(What is Paradigms (How they
communicating) communicate)
System-oriented entities Problem-oriented entities Interprocess Indirect communication
communication / Remote
invocation
Nodes Objects Message passing Group communication
Processes Components Sockets Publish-subscribe
Web services Multicast Message queues
––– Tuple spaces
Request-reply DSM
RPC
RMI

3.3 Roles and Responsibilities

Client-Server
Client-server is the architecture most commonly encountered. Clients invoke individual servers
directly; a process may itself act as a client of one server while also acting as the server for another
process (for example, a web server that is itself a client of a database server). The basic interaction
pattern is: a client sends an invocation to a server, the server processes the request, and returns a
result back to the client.
Peer-to-Peer (P2P)
In a peer-to-peer architecture, all of the processes involved in a task or activity play similar roles,
interacting cooperatively as peers without any distinction between clients and servers. Each peer
provides access to its own resources (“sharable objects”), while at the same time being able to
access the resources shared by other peers. This allows the workload to be spread across a
(potentially very large) set of interconnected peers, with the system able to scale simply by adding
more peers.

3.4 Placement
The placement of entities — where the various pieces of a distributed system run, physically — is
crucial in determining key properties of the system, namely:
• Performance
• Reliability
• Security
Several common placement strategies are used in practice:
Mapping services to multiple servers
Services can be implemented using several server processes operating on separate hosts, which
may communicate with each other to maintain consistency between (replicated or partitioned) data.
The service as a whole is then provided by multiple servers. A more tightly-coupled arrangement of
multiple servers — typically located close together and managed as a single resource — is referred
to as a cluster.
Caching
A cache is a store of recently used data objects that is kept closer to a client (or set of clients) than
the objects’ original location, in order to improve access performance. A classic example is the web
proxy server: clients send their requests to a proxy server, which either returns a cached copy of the
requested page or forwards the request to the appropriate web server and caches the response for
future requests.
Mobile Code
With mobile code, program code is transferred to and executed on the client machine. Applets are a
well-known example of mobile code (Web Applets). A typical interaction proceeds in two steps:
(a) the client requests a resource, and as part of the response the relevant applet code is downloaded
from the web server to the client; (b) the client then interacts directly with the applet, which runs
locally — only contacting the web server again if necessary.
Mobile Agents
A mobile agent is a running program — including both its code and its data — that travels from one
computer to another within a network, carrying out a task on behalf of its owner (for example,
collecting information), and eventually returning with the results. Possible uses of mobile agents
include:
• Software installation and maintenance across many machines.
• Collecting information from different vendors’ databases, for example to compare prices.
Both mobile code and mobile agents raise significant security concerns, since they involve
executing code that originates from a remote (and possibly untrusted) source on the local machine.

3.5 Architectural Patterns

Layering
A layered architecture partitions a complex system into a number of layers, each providing a
related set of services:
• Layers are organised vertically — each layer offers services to the layer above it.
• A given layer makes use of the services offered by the layer immediately below it.
• This produces a useful form of software abstraction.
• Higher layers remain unaware of the implementation details of lower layers, or of any
other layers beneath them.
Platforms and Middleware
Distributed systems and applications are organised as a stack of software and hardware service
layers:
• Applications, services
• Middleware
• Operating system
• Computer and network hardware
A platform for distributed systems and applications consists of the lowest-level hardware and
software layers — that is, the combination of the operating system together with the underlying
computer and network hardware (for example, Intel x86 / Windows, or ARM / Android).
Middleware is a layer of software that sits above the platform. Its purpose is to mask the
heterogeneity of the underlying platforms — differing hardware, operating systems, networks and
programming languages — and to provide application programmers with a convenient, uniform
programming model on which to build distributed applications.
Tiered Architecture
Tiering is a technique used to organise the functionality of a given (logical) layer and to place that
functionality into appropriate server processes and, as a secondary consideration, onto physical
nodes. A typical application can be functionally decomposed into three logical aspects:
• Presentation logic — handles user interaction and display.
• Application logic — implements the core processing and business rules.
• Data logic — manages persistent storage and retrieval of data.
Two common tiered configurations are the two-tier and three-tier architectures:
• Two-tier architecture – all three logical aspects (presentation, application and data
logic) are partitioned into just two physical processes — typically a client and a server.
– Advantage: low latency, since fewer network hops separate the logical components.
– Disadvantage: the application logic must be split (somewhat artificially) between
the two processes.
• Three-tier architecture – each of the three logical aspects runs in its own process (e.g.
client → application server → database server).
– Advantage: a one-to-one mapping from logical elements to physical servers,
simplifying management and scaling of each tier.
– Disadvantage: added complexity, increased network traffic and increased latency,
due to the extra communication hops between tiers.
Thin Clients
A thin client is a software layer — often supporting only a window-based user interface — that
runs on a local computer and is used either to run remote application programs or to access services
hosted on a remote computer. Thin clients enable access to sophisticated networked services (such
as cloud services) while making very few demands on the capabilities of the client device itself.
In a typical thin-client arrangement, a network computer or PC running the Thin Client
communicates over a network with a compute server, which runs the actual Application Process.
This concept led directly to Virtual Network Computing (VNC): a VNC client (thin client)
connects to and interacts with a VNC server, which executes the real applications and streams the
resulting display back to the client.
Other Commonly Occurring Patterns
• Proxy pattern – designed to support location transparency in RPC or RMI. A local
proxy object stands in for a remote object, so that the client can interact with the proxy as
though it were interacting with the remote object directly.
• Brokerage in web services – supports interoperability in potentially complex distributed
infrastructures by introducing three distinct roles: the service provider, the service
requestor, and the service broker. Brokerage is reflected, for example, in the registry used
by Java RMI and the naming service used by CORBA.
The web service architectural pattern brings these roles together: a Service Requestor and a Service
Provider interact directly to invoke and deliver a service, while a Service Broker sits between them,
supporting discovery and matching of requestors to suitable providers.

3.6 Associated Middleware Solutions

The task of middleware is to provide a higher-level platform for the development of distributed
systems, and, through layering, to abstract over the heterogeneity present in the underlying
infrastructure — thereby promoting interoperability and portability of applications.
Table 3 — Categories of middleware and representative example systems
Major Category Subcategory Example Systems
Distributed objects Standard RM-ODP
Platform CORBA

Platform Java RMI

Distributed components Lightweight components Fractal

Lightweight components OpenCOM

Application servers Sun EJB

Application servers CORBA Component Model

Application servers JBoss

Publish-subscribe systems — CORBA Event Service

— Scribe

— JMS

Message queues — WebSphere MQ

— JMS

Web services Web services Apache Axis

Grid services The Globus Toolkit

Peer-to-peer Routing overlays Pastry

 Major Category Subcategory Example Systems
Routing overlays Tapestry

Application-specific Squirrel

Application-specific OceanStore

Application-specific Ivy

Application-specific Gnutella

Limitations of Middleware
Some communication-related functions cannot be implemented completely and reliably by
middleware alone. Certain end-to-end guarantees (for example, application-specific notions of
“reliable delivery”) can only be fully and correctly implemented with the knowledge and active
participation of the applications running at the end points of the communication — middleware can
provide useful building blocks, but it cannot, by itself, guarantee these properties for every possible
application.
4. Fundamental Models
Fundamental models take an abstract perspective in order to describe solutions to the individual
issues faced by most distributed systems. Three fundamental models are considered: the interaction
model, the failure model, and the security model.

4.1 Interaction Model

Distributed algorithms are characterised by processes that interact with each other by passing
messages, which results in:
• Communication – information flow between processes.
• Coordination – the synchronisation and ordering of activities between processes.
Reasoning about interaction is complicated by two fundamental issues:
• Communication takes place with delays of considerable (and often unpredictable)
duration — the accuracy with which independent processes can be coordinated is
fundamentally limited by these delays.
• There is the additional difficulty of maintaining a single, consistent notion of time across
all the computers in a distributed system, since each machine has its own physical clock,
which may drift.
Performance of Communication Channels
• Latency – the delay between the start of a message’s transmission from one process and
the beginning of its receipt by another process.
• Bandwidth – the total amount of information that can be transmitted over a computer
network in a given period of time.
• Jitter – the variation in the time taken to deliver a series of messages — particularly
important for real-time and streaming applications.
Computer Clocks and Timing Events
• Clock drift rate – the rate at which a computer’s clock deviates from the time given by a
perfect (ideal) reference clock. Because every computer has its own physical clock,
which drifts independently of all others, maintaining a single global notion of time across
a distributed system is inherently difficult.
Two Variants of the Interaction Model
Depending on what assumptions can be made about timing, distributed systems are modelled as
either synchronous or asynchronous.
• Synchronous distributed systems – systems in which the following timing bounds are
known:
– The time taken to execute each step of a process has known lower and upper
bounds.
– Each message transmitted over a communication channel is received within a
known, bounded time.
– Each process has a local clock whose drift rate from real time has a known bound.
• Asynchronous distributed systems – systems that place no bounds on:
 – Process execution speeds.
– Message transmission delays.
– Clock drift rates.
The asynchronous model is the more general — and more realistic — model for systems such as
the Internet, but it makes reasoning about timing-related guarantees considerably more difficult.
Real-Time Ordering of Events: Logical Time
Because physical clocks across a distributed system cannot be perfectly synchronised, systems
often rely instead on logical time: events are ordered based on cause-and-effect relationships rather
than on physical clock readings. For example, the event of sending a message must always occur
before the event of receiving it, regardless of what each process’s local clock reads. This
relationship is typically illustrated with a space-time diagram, in which each process is drawn as a
horizontal timeline and diagonal arrows represent messages sent between processes — making the
causal ordering of events visually apparent even though physical time on each process’s local clock
may differ.

4.2 Failure Model

Faults can occur in any of the computers running a distributed system — including software faults
— or in the network connecting them. A failure model defines and classifies the faults that a system
may exhibit, which provides a basis both for analysing the effects that faults may have and for
designing systems that can tolerate them.
Omission Failures
An omission failure occurs when a process or communication channel fails to perform an action
that it is supposed to perform.
• Process omission failures – the most common (and simplest) omission failure of a
process is for it to crash. A crash is called fail-stop if other processes can detect — with
certainty — that the process has indeed crashed.
• Communication omission failures – occur when a communication channel fails to
transport a message that was submitted to it for transmission — commonly known as
dropping messages. Considering a message travelling from a process p’s outgoing
message buffer, across the communication channel, to a process q’s incoming message
buffer, three types of omission can be distinguished:
– Send-omission failure — the message is lost between the sending process and its
outgoing message buffer.
– Receive-omission failure — the message is lost between the channel and the
receiving process’s incoming message buffer.
– Channel-omission failure — the message is lost somewhere within the
communication channel itself.
Arbitrary (Byzantine) Failures
An arbitrary, or Byzantine, failure is used to describe the worst possible failure semantics, in which
any type of error may occur. A process or channel exhibiting an arbitrary failure may send or
transmit arbitrary messages at arbitrary times, may commit omissions, and a process may stop or
take an incorrect step — its behaviour is essentially unconstrained.
Table 4 — Classes of failure (general)
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, but other processes may not be able to
detect this state.
Omission Channel A message inserted into 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 placed in its
outgoing message buffer.
Receive-omission Process A message is placed in a process’s incoming message buffer, but that
process does not receive it.
Arbitrary Process or Process or channel exhibits arbitrary behaviour: it may send or transmit
(Byzantine) channel arbitrary messages at arbitrary times, commit omissions; a process may
stop, or take an incorrect step.

Timing Failures
Timing failures are applicable specifically in synchronous distributed systems, where explicit
bounds are set on process execution time, message delivery time, and clock drift rates. A timing
failure occurs whenever one of these bounds is exceeded.
Table 5 — Timing failures (synchronous systems only)
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.

Masking Failures
Knowledge of how a system can fail can be used to design a new (higher-level) service that masks
the failure of the components on which it depends. For example, a service might use error-
correcting codes to mask corrupted messages, or retransmission to mask lost messages — so that,
from the perspective of the service’s users, the system appears to operate correctly despite
underlying failures occurring.
Reliability of One-to-One Communication
A communication channel between two processes is considered reliable if it satisfies the following
two properties:
• Validity – any message placed in the outgoing message buffer is eventually delivered to
the corresponding incoming message buffer.
• Integrity – the message received is identical to the one that was sent, and no messages
are delivered twice (i.e. no duplication occurs).
4.3 Security Model
The modular nature of distributed systems, together with their openness, exposes them to attack
from both external and internal agents. A security model defines and classifies the forms that
attacks can take, providing a basis for the analysis of threats to a system and a basis for the design
of systems that are able to resist them.
In general, the security of a distributed system is achieved by securing the processes and the
communication channels used for their interactions, and by protecting the objects that those
processes encapsulate against unauthorised access.
Protecting Objects
Each principal (a user or a process) is granted access rights, which determine the operations it may
perform on which objects:
• Each invocation, and the corresponding result, is associated with the authority on whose
behalf it is issued — this authority is called a principal.
• A principal may be either a user or a process.
In the general model, a client (acting on behalf of a particular user-principal) sends an invocation
across a network to a server (acting on behalf of a server-principal). The server checks the
requested operation against the access rights associated with the relevant object, and — if
permitted — performs the operation and returns a result to the client.
Securing Processes and their Interactions
The central challenge here is securing communications that take place over open channels —
channels that may potentially be observed or interfered with by an attacker. A generic term for any
such attacker is the enemy, also called the adversary. The enemy is capable of:
• Sending any message to any process.
• Reading or copying any message sent between a pair of processes, whether or not it is the
intended sender or recipient of that message.
Diagrammatically: process p sends a message m to process q over a communication channel. The
enemy may intercept and copy m as it travels (producing a “copy of m”), and may also inject a
different, possibly forged, message m’ toward q.
Threats to Processes
A process may have no reliable way of determining the true source of a message it receives. This is
a problem both from the server’s perspective (is this request genuinely coming from an authorised
client?) and from the client’s perspective (is this reply genuinely coming from the legitimate
server?). A classic example is spoofing a mail server, where messages are made to appear as though
they originate from a trusted source when, in fact, they do not.
Threats to Communication Channels
An attacker with access to a communication channel poses a threat to both the privacy and the
integrity of the messages carried on that channel — for example, through eavesdropping (privacy)
or tampering with messages in transit (integrity). These threats can be defeated through the use of
secure channels.
Defeating Security Threats
• Cryptography – the science of keeping messages secure.
• Encryption – the process of scrambling a message in such a way as to hide its contents
from anyone other than the intended recipient(s).
• Authentication – based on shared secrets — messages are authenticated by proving that
the sender holds a secret known only to legitimate parties, thereby proving the identity
claimed by the sender.
Secure Channels
A secure channel is constructed on top of an underlying (insecure) communication channel
between a pair of processes, and provides the following properties:
• Each of the processes reliably knows the identity of the principal on whose behalf the
other process is executing (mutual authentication).
• A secure channel ensures the privacy and integrity (i.e. protection against tampering) of
the data transmitted across it.
• Each message includes a physical or logical timestamp, to prevent messages from being
replayed or reordered by an attacker.
Schematically, Principal A (running process p) communicates with Principal B (running process q)
over a secure channel, which guarantees the properties above despite the underlying channel itself
being potentially insecure.
Other Possible Threats from the Enemy
• Denial of Service (DoS) – the enemy interferes with the activities of authorised users by
making excessive and pointless invocations on services, or by flooding the network with
message transmissions. This results in the overloading of physical resources — such as
network bandwidth and server processing capacity — so that legitimate requests can no
longer be served.
• Mobile code – executing program code that originates from elsewhere — for example, an
email attachment or a downloaded applet — carries the risk that the code itself may be
malicious and could perform unauthorised actions on the host machine.
The Uses of Security Models
A security analysis typically involves the construction of a threat model, consisting of:
• Listing all the forms of attack to which the system is exposed.
• An evaluation of the risks and consequences associated with each form of attack.
This threat model then guides the selection of appropriate security mechanisms — such as
encryption, authentication protocols, access control and secure channels — to mitigate the
identified risks.
5. Case Study: Amazon Dynamo
Amazon Dynamo is used as a real-world case study that illustrates many of the architectural,
placement and failure-handling concepts discussed above, applied to a large-scale production
system.

5.1 Overview
• Dynamo is a highly available key-value storage system.
• It is designed for applications that work with many large datasets/objects which only
require primary-key access — that is, simple lookups by key, without the need for
complex relational queries or joins. Examples include:
– Shopping carts
– Best-seller lists
– Customer preferences
– Product catalogues
• Relational databases are not required for these use cases, and would be too slow or too
“bulky” (over-engineered) for the simple access pattern involved.
• Dynamo prioritises fast reads and high availability for writes.
• Dynamo is designed on the assumption that servers, disks and network switches are
always failing — partial failure is treated as the normal operating condition, not an
exception.

5.2 Architecture and Operation

• Data objects are replicated across multiple nodes — specifically, on a node’s “successor”
nodes in a ring-based layout (a consistent-hashing ring).
• All peer nodes learn about each other through gossiping — a gossip-based protocol is
used to disseminate membership and liveness information, avoiding the need for a
centralised directory.
• Clients can read from or write to any replica of an object — there is no single, designated
primary that must be contacted, which improves availability.
• Because different replicas of an object can be updated independently and concurrently,
Dynamo includes mechanisms to detect and reconcile different versions of the same
object.
Consistent-Hashing Ring
Nodes are arranged into a logical ring, based on their hashed identifiers (for example, nodes
labelled A through G). A given key, K, is also hashed onto a position on this ring. The node whose
identifier is the first one encountered when moving clockwise from K’s position is responsible for
(“coordinates”) that key. To provide fault tolerance, key K and its associated value are also
replicated onto the next several nodes encountered while continuing clockwise around the ring —
these are the “successor” nodes — so that the failure of any single node does not result in data loss.
High-Level Request Flow
At a high level, client requests are received and handled by page-rendering components. Requests
then pass through a request-routing layer, which directs them to aggregator services. These
aggregator services interact with Dynamo instances, and potentially with other datastores, in order
to assemble the final response that is returned to the client.

5.3 Reference
G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S.
Sivasubramanian, P. Vosshall and W. Vogels, “Dynamo: Amazon’s Highly Available Key-value
Store,” ACM SIGOPS Operating Systems Review, Vol. 41, No. 6, October 2007.
6. Quick-Revision Summary
6.1 The Three Ways of Modelling a Distributed System
• Physical model – hardware view — nodes and their interconnection.
• Architectural model – communicating entities, communication paradigms,
roles/responsibilities, placement (e.g. client-server, peer-to-peer).
• Fundamental models – interaction model, failure model, security model — abstract
reasoning tools for cross-cutting issues.

6.2 Key “What Is...?” Questions to Revise

• What is interprocess communication, remote invocation, and indirect communication —
and how do they differ?
• What is the difference between RPC and RMI?
• What is space uncoupling vs. time uncoupling, and which indirect-communication
techniques rely on each?
• What is the difference between a two-tier and a three-tier architecture, and what are the
trade-offs of each?
• What is the difference between a synchronous and an asynchronous distributed system?
• What is the difference between latency, bandwidth and jitter?
• What is the difference between a send-omission, receive-omission and channel-omission
failure?
• What is a Byzantine (arbitrary) failure, and how does it differ from a crash/fail-stop
failure?
• What properties (validity and integrity) define a reliable communication channel?
• What is a principal, and how are objects protected using access rights?
• What properties does a secure channel guarantee?
• Why does Amazon Dynamo use a key-value model rather than a relational database, and
how does it achieve high availability?

6.3 Glossary of Key Terms

Term Meaning
Node A computer or device that is part of a distributed system.
Middleware Software layer that masks heterogeneity and provides a uniform programming
model above the platform (OS + hardware).
RPC / RMI Mechanisms for invoking remote procedures (RPC) or remote object methods
(RMI) as if they were local.
Group communication Sending a message to a group of recipients without needing to know their individual
identities.
Publish-subscribe One-to-many communication where publishers emit events that interested
subscribers receive.
Tuple space Persistent shared space where processes place and retrieve structured data items
(tuples).
Term Meaning
Cluster A tightly coupled group of servers managed as a single resource.
Cache / Proxy Stores recently used data closer to clients to improve performance.
Mobile code / agent Program code (and, for agents, data) that moves between computers to execute
remotely.
Clock drift The rate at which a local clock deviates from a perfect reference clock.
Logical time Ordering of events based on cause and effect rather than physical clock readings.
Fail-stop A crash failure that other processes can reliably detect.
Byzantine failure Arbitrary, unconstrained failure behaviour — the worst-case failure model.
Principal The user or process on whose behalf an invocation or result is issued.
Secure channel A channel providing mutual authentication, privacy, integrity and protection against
replay/reordering.
Threat model A listing of possible attacks together with an evaluation of their risks and
consequences.