System Models

Why Model a Distributed System?

A distributed system is a collection of computers that cooperate by sending each other messages over a network. Real ones are enormously complicated: thousands of machines, many programs, networks that slow down and machines that fail. To reason about such a thing at all, you have to leave most of the detail out and keep only what matters for the question you are asking. That is what a model does.

Models earn their keep in three ways. They help us classify and understand existing implementations and see their strengths and weaknesses. They let us build new systems from pre-validated building blocks, because a design pattern that is known to work can be reused. And they make our design assumptions explicit, so that we can check whether those assumptions really hold. For example, an algorithm that assumes "every message arrives within one second" is only safe on a network where that is true, and a model forces you to write that assumption down.

Three kinds of model exam

The textbook (CDK §2.1) looks at a distributed system from three levels, from the concrete to the abstract. Each answers a different question about the same system.

The difficulties every design must face

Whatever architecture you pick, the same four kinds of trouble will come for it. CDK §2.1 groups them like this, and each has a typical answer. Notice how the answers foreshadow the rest of the Part: redundancy, modular structure, failover and built-in security.

Design must look forward

The lecturer's warning is that a design which suits 10 users can be terrible for 10,000, so you must think about where the system is heading. His example is a dictionary server (a service that looks up word meanings), which could be built in three quite different ways.

Check yourselfA design document says: "messages may take arbitrarily long to arrive, and any process may crash at any time." Which kind of model is this statement part of?

1. A physical model
2. An architectural model
3. A fundamental model
4. None: it is an implementation detail

C, a fundamental model (specifically the interaction and failure models). It says nothing about which hardware is used (physical) or how components are arranged (architectural); it states assumptions that would hold whatever the architecture. A is wrong because no nodes or links are described; B is wrong because no roles or placement are described.

Check yourselfGive the three reasons for building models of distributed systems.

(1) To classify and understand implementations and identify their strengths and weaknesses; (2) to build new systems from pre-validated building blocks; (3) to make design assumptions explicit, so they can be checked against the real system.

Physical Models

The most concrete question you can ask about a distributed system is: what is it physically made of? The answer has changed enormously over forty years, from a few dozen office PCs to billions of phones, sensors and data-centre servers, and each change brought new problems. A physical model describes the hardware without getting lost in brand names or cable types.

Three generations of distributed systems exam

CDK Fig. 2.1 traces how the physical basis has grown. Read the picture and the table along the rows: the systems grow in scale and heterogeneity (variety of hardware and software), while openness (being built on published, standard interfaces so anyone can extend them) and quality of service (guarantees about performance and reliability) rise from low priorities to major research challenges.

Three assumptions that broke

In the earlier generations a node could be assumed to be static (it stays put), discrete (it is a separate, recognisable computer) and autonomous (it works on its own). Three trends have broken each of these assumptions in turn.

Systems of systems

At the ultra-large scale we meet systems of systems: complex systems whose subsystems are systems in their own right, which come together to perform a task. Flood prediction is the textbook example.

Check yourselfIn which generation did openness first become a significant priority, and what made it necessary?

The Internet-scale generation (1990s on). Systems now spanned many organisations with significant heterogeneity of platforms, languages and middleware, so they could only work together through open standards and middleware such as CORBA and web services. In the early generation openness was not a priority; in the contemporary one it has become a major research challenge.

Check yourselfWhich trend breaks the assumption that nodes are autonomous?

1. Mobile computing
2. Ubiquitous computing
3. Cloud computing and clusters
4. Open standards

C. In cloud computing and clusters, pools of nodes jointly provide one service, so a node no longer works on its own. Mobile computing (A) breaks static; ubiquitous computing (B) breaks discrete; D is not one of the three trends.

Architectural Models: the Elements

Knowing the hardware tells you nothing about how the software is organised. Two systems on identical machines can behave completely differently depending on which program does what, and where. An architectural model captures exactly that organisation, so you can compare designs and predict how they will cope with growth and failure.

An architectural model does three things. It (i) simplifies and abstracts the functions of the individual components; it considers their (ii) placement, meaning how data and workload are distributed across machines; and it considers their (iii) interrelationships, meaning their roles and the patterns in which they communicate. The very first simplification is to classify every process as a server, a client or a peer.

Four key questions exam

Designing an architecture comes down to answering four questions. Understanding the trade-offs between the possible answers is the key design skill, and the rest of this Part takes the questions one at a time.

Question 1: what communicates?

There are two ways to answer. From a system-oriented view, the communicating entities are processes (running programs), so a distributed system is simply a set of processes plus interprocess communication (IPC), the mechanisms processes use to send each other data. Two caveats apply. In some sensor networks the tiny devices have no operating-system support for processes, so the entities are the nodes themselves. And, strictly speaking, the real endpoints of communication are threads, the separate sequences of execution inside a process (Part IV).

From a problem-oriented view, which is closer to how programmers think, there are three kinds of entity.

• Objects are the natural units of decomposition in object-oriented programs. They are accessed through interfaces written in an IDL (interface definition language), a notation that describes the methods an object offers independently of any programming language (Part VI).
• Components specify both the interfaces they provide and the interfaces they require. Because the dependencies are explicit, a component comes with a complete contract, which lets third parties build components and compose them.
• Web services are identified by a URI (Uniform Resource Identifier, a web-style name such as a URL). Their interfaces are described and discovered as XML (a text format for structured data), and they communicate by XML messages over Internet protocols such as HTTP.

The difference in use matters: objects and components typically build tightly coupled applications inside one organisation, whereas web services are complete services in their own right that can be combined across organisational boundaries.

Question 2: how do they communicate? exam

Once you know what communicates, you need to choose how. There are three paradigms, running from raw message exchange up to communication through a third party.

Remote invocation comes in three forms, each built on the one before.

• Request-reply is the primitive form: a pairwise exchange of a request message and a reply message. The messages carry the operation, its arguments and its results in encoded form; turning program data into a sequence of bytes for transmission is called marshalling. HTTP works this way, and request-reply underlies RPC and RMI.
• RPC (Remote Procedure Call) lets a program call a procedure in another process as if it were local, hiding the marshalling and messaging. It gives at least access transparency (local and remote calls look the same) and location transparency (the caller need not know where the procedure runs).
• RMI (Remote Method Invocation) is RPC for distributed objects: it adds object identity and the ability to pass references to remote objects as arguments and results.

Direct coupling versus space and time uncoupling

The paradigms also differ in how tightly they tie sender and receiver together. Remote invocation is directly coupled: the sender must name the receiver, and both must be running at the same moment. Indirect communication removes both requirements. It gives space uncoupling, because the sender need not know who the receivers are, and time uncoupling, because sender and receiver need not exist at the same time.

There are five indirect techniques; Part VII covers each in depth.

• Group communication delivers a message one-to-many, to a group identifier. Recipients join the group, and the system manages membership and member failures.
• Publish-subscribe uses an intermediary that routes events from many publishers to the subscribers that registered interest in them.
• Message queues are point-to-point: producers send messages to a queue, and consumers receive them from it or are notified when they arrive.
• Tuple spaces let processes put structured records (tuples) into a persistent space, where other processes can read or remove them by pattern.
• Distributed shared memory (DSM) lets processes read and write shared data as if it were in their own address space, even though there is no shared physical memory.

Check yourselfA stock-trading app posts "price changed" events; any number of dashboards that have registered interest receive them, and the app never knows which ones. Which paradigm, and which kind of uncoupling does it show most clearly?

It is indirect communication, specifically publish-subscribe. The app does not know who the receivers are, which is space uncoupling. (If the events were also stored for dashboards that start later, it would show time uncoupling too.) Remote invocation would not fit, because it requires the caller to name each receiver.

Check yourselfHow does a component differ from an object, and what does the difference buy you?

An object declares only the interface it offers. A component declares both the interfaces it provides and those it requires, so its dependencies are explicit. That gives a complete contract, which lets independent (third-party) developers build components and compose them without hidden dependencies.

Roles: Client-Server and Peer-to-Peer

The third key question is about roles and responsibilities: does one machine do the work for everyone, or does everyone share it? The two main answers, client-server and peer-to-peer, are the most important architectural styles in the subject.

Client-server exam

In a client-server architecture, client processes interact with individual server processes, possibly on separate hosts, to access the shared resources that the servers manage. A resource here means anything that can usefully be shared: a file, a database, a printer, a web page. This is the most important and most widely used architecture.

A search engine shows roles changing even more clearly. It is a server to millions of browsers, but its web crawlers (programs that fetch pages to index) act as clients of other web servers. The crawler threads and the query-answering threads run concurrently, synchronising only on the shared index they both use.

Peer-to-peer exam

In a peer-to-peer (P2P) architecture, all processes play similar roles and cooperate as peers, with no distinction between client and server. They run the same program and offer the same interfaces to each other.

The key insight is that the users' own computers and network links can support the service, so resources grow with the number of users: every new user brings storage, processing and bandwidth as well as demand. Each peer holds only part of the shared data, and the load is spread across many machines. Objects are replicated (copies are kept on several peers), both to spread the load and to make the system resilient when peers disconnect, which they do all the time. All of this makes P2P substantially more complex than client-server: something must decide where data goes, how to find it, and how to keep copies.

Examples include Napster (not pure P2P, because it had a central index), Gnutella, BitTorrent, a distributed whiteboard and blockchain. The slides also show P2P with a centralised index server, as used by WhatsApp, Skype and WeChat: a server helps peers find each other, and then the peers interact directly. The lecturer adds that P2P has no central point of failure or control, which makes it hard for an adversary to deny service, and that some peers contribute more than others (seeds in BitTorrent, super-peers elsewhere).

Static versus dynamic responsibility

The two styles also allocate responsibility differently. Client-server allocates it statically: a file server serves files, not web pages, and that never changes at run time. P2P allocates it dynamically: a search, for instance, may be delegated to different peers depending on who is online at that moment.

Check yourselfTrue or false: "A web server is a server, so it can never be a client."

False. Client and server are roles in an interaction. A web server is a client of DNS when it resolves a name, and of a file or database server when it fetches content. A search engine's crawlers are clients of other web servers.

Check yourselfWhy does a P2P file-sharing system's capacity grow as more users join, while a client-server system's capacity does not?

1. P2P uses faster networks
2. Each new peer contributes its own storage, processing and bandwidth
3. P2P compresses data better
4. Clients in client-server refuse to share

B. In P2P the users' own machines and links support the service, so each newcomer adds resources as well as demand. In client-server every newcomer only adds demand on the fixed server.

Check yourselfWhy is Napster described as "not pure P2P"?

Because it relied on a central index server to find which peer held which file. The file transfers themselves were peer to peer, but the lookup was client-server, the same hybrid as WhatsApp or Skype's directory.

Placement Strategies exam

The fourth key question is placement: deciding which machine and which process each service or data object lives on. It sounds like a deployment detail, but placement largely determines a system's performance, reliability and security. The right choice depends on the patterns of communication between components, on how reliable and loaded each machine is, and on the quality of the links between them. There are four strategies.

1 · Mapping services to multiple servers

A single server caps the whole system (2.4). The first fix is to let several servers on separate hosts provide one service together. They can split the work in two ways. In partitioning, each server manages its own share of the objects, as the Web does: each web server holds only its own pages. In replication, each server holds a copy of the same objects, as Sun NIS (Network Information Service) does: every NIS server holds a copy of the password file, so any of them can check a login.

A cluster is a closely coupled version of the same idea: up to thousands of cheap commodity computer boards in one place, working as one service. The lecture's examples are Google's clusters, to which clients are redirected via DNS; replicated Oracle databases; Kubernetes (a system that runs and replicates services across a cluster); and microservices, where an application is split into small independent services, each on its own servers, behind a load balancer that spreads incoming requests across them. The gains are load sharing, availability (the service is up when needed) and fault tolerance (it keeps working when parts fail).

2 · Caching exam

Browsers keep a cache of pages on the user's own machine, and before reusing a cached page they can validate it with a special HTTP request that asks the server whether it has changed. A web proxy server goes one step further and provides a shared cache for many clients, typically everyone in one organisation. A proxy in general is an intermediary that acts on behalf of someone else; here the proxy fetches pages on behalf of its clients.

The benefits: a proxy cache increases availability and performance by reducing the load on the wide-area network and on web servers. Proxies can also give machines inside an organisation controlled access to the outside through a firewall (a barrier that filters traffic between an internal network and the Internet). The slides add that proxies give replication transparency: the client cannot tell whether it is talking to the original or a copy. The cost is stale data: a cached copy can be out of date, which is why caches check whether a copy is up to date.

3 · Mobile code

Sometimes the slow part is the network itself: every click the user makes would need a round trip to the server. Mobile code solves this by moving the code instead: code downloaded from a server runs at the client. Java applets were the classic example. The user's request downloads the applet's code, and the user then interacts with it locally.

4 · Mobile agents exam

The idea is to "bring the small program to the big data". Instead of making many remote invocations across the network to a server that holds a large amount of data, the agent goes there and makes local invocations, which lowers the communication cost. Uses include software installation and maintenance, comparing prices across vendors, and mining distributed data; JADE is a toolkit for building agents.

The disadvantages are again about security, in both directions. The agent is a threat to every host it visits, so a host must decide which of its resources to allow, based on the securely attached identity of the user the agent acts for. The agent is itself vulnerable: if a host refuses it access, its task fails, and a hostile host could tamper with it. And because most of these tasks can be done in other ways (web crawlers, for instance, simply use remote invocation), mobile agents have limited applicability.

Mobile code and mobile agents are easy to confuse, so here is the difference side by side.

Check yourselfA university wants students' web browsing to be faster and to reduce its Internet bill, because many students load the same pages. Which placement strategy fits, and what is its main risk?

Caching with a shared web proxy server. Pages fetched by one student are kept in the proxy's cache, so later requests are answered locally, lowering latency and wide-area traffic (and the proxy can sit at the firewall). The main risk is stale data: a cached copy may be out of date, so the cache must check that its copy is up to date before using it.

Check yourselfWhich statement about mobile agents is correct?

1. They are downloaded once and run only at the client, like an applet.
2. They carry code and data between hosts, replacing remote invocations with local ones.
3. They are widely used because they pose no security risk.
4. They reduce the work each host does by running everything at home.

B. A describes mobile code. C is wrong: agents threaten the hosts they visit and are vulnerable themselves, which is one reason their use is limited. D is backwards: the agent goes to where the data is.

Other Client-Server Variants

Beyond the four placement strategies, the slides describe several more ways of dividing work between a user's device and the servers. They differ in one question above all: where does the application actually run?

Network computers and thin clients

Network computers download their operating system and applications from a remote file server and run them locally. Because nothing important is stored on the machine, users can move between machines freely, and upgrades are made once, centrally. The approach has since been superseded by virtual network computing (below).

Thin clients have clear advantages: weak, cheap devices gain access to powerful services; maintenance, upgrades and security are handled centrally; and users have access from anywhere. The drawback is that highly interactive graphics, such as CAD (computer-aided design) or image processing, suffer unacceptable delay, because every mouse movement must go to the server and every new frame must come back, adding network and operating-system latency to each action.

VNC (Virtual Network Computing) shows how simple the protocol can be. A viewer talks to a VNC server using a framebuffer protocol (the framebuffer is the block of memory holding the screen's pixels), whose single operation places a rectangle of pixels at a given position on the screen. Because that is so low-level, it works with any operating system or application.

Today's cloud applications used through a browser, such as an online spreadsheet, follow the same thin-client, client-server idea. The trend is to move complexity out of end devices and into Internet services.

Mobile devices and spontaneous networking

The last variant deals with devices that move. A laptop or phone joins and leaves networks (a hotel's wireless LAN, say) and wants to use whatever local services are there, such as a printer or music. It needs two things: an easy way to connect, such as DHCP (a protocol that automatically hands a newly arrived device a network address), and a discovery service. A discovery service has two parts: a registration service, where servers publish the services they offer, and a lookup service, where clients find services that meet their requirements. Apple's Bonjour and UPnP work like this; naming in general is covered in Part IX.

Summary of the variants exam

Every variant buys a benefit at a cost. This table is worth learning as a whole, because a 5-mark question often asks for a variant, a reason for using it, and its downside.

Check yourselfA design firm considers giving its engineers thin clients connected to a central compute server for their 3D CAD work. What is the main objection?

Thin clients are usually not suitable for highly interactive graphical work. Every rotation of a 3D model would need input sent to the server and new screen images sent back, so network and OS latency would make the response unacceptably slow.

Check yourselfIn one sentence each, how do a network computer and a thin client differ in where the application runs and what the network carries?

A network computer downloads the OS and applications and runs them locally, so the network carries code and files. A thin client runs nothing but the UI; the application runs on the remote server, so the network carries UI events up and screen updates down.

Architectural Patterns

Designers keep meeting the same problems, and the same arrangements of elements keep solving them. An architectural pattern is such a recurring composite structure, built from the elements of the previous sections, that is known to work well in given circumstances. Learning the patterns means you can recognise a design quickly and reuse one that works. This section covers layering, tiering and AJAX, and then three more patterns: proxy, brokerage and reflection.

Layering exam

In layering, a system is split into a stack of layers. Each layer uses the services of the layer below and offers a service (an abstraction) to the layer above, hiding how it is implemented. A programmer working at one layer only needs to understand the interface of the layer directly beneath.

Tiered architectures exam

Tiering is easy to confuse with layering, but the two work in different directions. Layering is a vertical organisation into levels of abstraction. Tiering takes the functionality within one layer, typically the application, and places it onto appropriate servers, which is a horizontal spread across machines. To tier an application, you first divide it into three kinds of logic:

• Presentation logic handles user interaction and updates the view the user sees.
• Application logic, also called business logic, implements what the application actually does (the rules of the business).
• Data logic handles persistent storage, usually through a DBMS (database management system).

The two classic arrangements are two-tier and three-tier. They trade latency (the delay before a response) against maintainability (how easy the system is to change and keep running).

Systems can also have more tiers, which is called multi-tier (or n-tier, or cascade). Wikipedia is built this way, and so is J2EE (Java 2 Enterprise Edition), where a request passes along a chain of four tiers.

AJAX

Standard web interaction has three problems. It blocks the user until a whole new page arrives; it re-sends a whole page even for a tiny change; and it cannot reflect changes on the server until the user reloads. AJAX (Asynchronous JavaScript And XML) fixes these by letting JavaScript code running in the browser request data from the server in the background, via the XmlHttpRequest object, and then update only part of the page. It is the glue between tier-1 (browser) and tier-2 (server) components. CDK illustrates it with a page of football scores.

Notice that the two calls behave differently, on purpose. The call from browser to server is asynchronous, because a delayed reply must not freeze the user interface. In three-tier designs the call from the server to the database is synchronous, because the server cannot continue without the data. Google Maps fetches its map tiles in the same way as the user drags the map.

Other patterns: proxy, brokerage, reflection

• Proxy. A local object with the same interface as a remote object forwards calls to it. This gives location transparency in RPC and RMI (Part VI), and a proxy can also encapsulate caching or replication behind that interface.
• Brokerage. Three roles: a service provider, a service requester and a service broker that matches requests to providers. Examples are the Java RMI registry, the CORBA naming service and web-service registries.
• Reflection. Combines introspection, which is discovering properties of a program at run time (for example, asking an object what methods its interface has), and intercession, which is modifying the program's structure or behaviour dynamically. Both work through a meta-level interface, a layer that describes the program itself. Java reflection, for example, is what lets RMI dispatch incoming calls generically: the server can invoke a method chosen by name at run time without code written for each method.

Check yourself"Layering and tiering are two names for the same idea." Explain why this is wrong.

Layering is a vertical organisation of a system into levels of abstraction (hardware, OS, middleware, applications), each using the one below. Tiering is horizontal: it takes the functionality within one layer (the application) and divides it into presentation, application and data logic placed onto appropriate servers. They are complementary: a three-tier application still runs on top of the layer stack on each machine.

Check yourselfIn the AJAX example, why is the browser-to-server call asynchronous but the server-to-database call synchronous?

The browser call is asynchronous so that a slow reply cannot freeze the user interface: the user keeps working and the page is patched when the data arrives. The server-to-database call is synchronous because the server cannot build its response until it has the data, so there is nothing useful to do while waiting.

Check yourselfThe Java RMI registry is an example of which pattern?

1. Layering
2. Proxy
3. Brokerage
4. Reflection

C, brokerage. Servers publish (bind) remote objects in the registry under names, and clients find them there, then invoke the objects directly. (The client then calls through a proxy, which is a different pattern used in the same system.)

Middleware and Design Requirements

Middleware raises the level of programming abstraction and hides heterogeneity, and both aims serve one goal: interoperability (programs on different platforms can work together) and portability (a program can move to another platform unchanged). But how much can middleware really hide? This section sorts middleware into categories and then explains its limits.

Six categories of middleware

CDK Fig. 2.12 sorts middleware by the programming abstraction it offers. The categories overlap, since real platforms are hybrids, and besides its programming abstractions middleware also provides infrastructural services such as security and transactions.

The limits of middleware: the end-to-end argument exam

The classic example is transferring a very large email over TCP (the Internet's reliable stream protocol, Part III). TCP guarantees delivery while the connection lasts, but it cannot recover from a major network interruption that breaks the connection. Only the mail application knows how much of the message has been safely stored, so the mail service itself must record its progress and resume over a new connection.

Hence middleware cannot hide all communication concerns. Correctness needs checks at several levels, and the right behaviour for middleware depends on the application, which is what motivates adaptive middleware that can be tuned to each application's needs.

Design requirements (slides)

These requirements come from the slides; CDK 5th edition does not list them separately. They are the qualities an architecture is judged by.

Check yourselfState the end-to-end argument and give the textbook example.

Some communication-related functions can be completely and reliably implemented only with the knowledge and help of the application at the end points, so the communication system alone cannot provide them fully. Example: a very large email sent over TCP. TCP cannot recover from a major network interruption that breaks the connection, so the mail service records its progress and resumes over a new TCP connection. Therefore middleware cannot hide every communication concern.

Check yourselfWhich of these is not one of CDK's middleware categories?

1. Distributed objects
2. Message queues
3. Thin clients
4. Peer-to-peer

C. A thin client is a client-server variant (2.6), not a middleware category. The six categories are distributed objects, distributed components, publish-subscribe, message queues, web services and peer-to-peer.

Fundamental Models: Interaction

The architectural models of the previous sections differ a great deal, but underneath they all consist of processes communicating by sending messages over a network. The fundamental models keep only that essence, so that we can reason precisely about what any distributed system can and cannot do. There are three: the interaction model (this section), the failure model (2.10) and the security model (2.11).

What the interaction model describes

Processes interact by passing messages, and that gives two things: communication (information flows between processes) and coordination (processes synchronise and order their activities). The behaviour of the whole system is a distributed algorithm: a definition of the steps taken by each process, including the transmission of messages between them. Each process has its own private state (its variables), which no other process can read directly; the only way to learn about another process's state is to receive a message from it.

Two significant factors exam shape this interaction and make distributed algorithms hard: (1) communication performance is often a limiting factor, and (2) it is impossible to maintain a single global notion of time. We take them in turn.

Performance of communication channels exam

A channel is the path a message takes from one process to another. Three properties describe how well it performs.

• Latency is the delay between the start of a message's transmission by one process and the beginning of its receipt by another. It includes the time for the first bits to reach the destination (long for a satellite link, for example), the network access delay, which grows as the network gets busier, and the operating system's communication processing at both ends.
• Bandwidth is the total amount of information that can be transmitted over the network in a given time, such as 100 Mbps (megabits per second). It is shared by all the channels using the same network.
• Jitter is the variation in the time taken to deliver a series of messages. It distorts audio and video playback: if successive video frames arrive at uneven intervals, the picture stutters.

Clocks and drift exam

Each computer has its own hardware clock, which it uses to timestamp events. Unfortunately, clocks drift away from perfect time, and different clocks drift at different rates.

So clocks that are set equal will diverge unless they are corrected. GPS receivers give about 1 µs accuracy, but not indoors and not cheaply. Otherwise a computer with an accurate clock can send time messages to the others, as NTP (the Network Time Protocol) does. But each time message takes a variable amount of time to arrive, so the receiver never knows exactly how old the time it was told is. As a result, no guaranteed bound on the difference between clocks is possible this way.

Synchronous versus asynchronous systems exam

The two factors above (unpredictable delays, unreliable time) are exactly what separates the two basic models of a distributed system. The question is whether anything about timing is guaranteed.

You can always guess bounds, but a design that relies on bounds nobody guarantees is unreliable. Modelling a system as synchronous is still useful, because it tells you how the system is likely to behave. Real systems, though, are usually asynchronous, because processes share processors and channels share networks, so nothing stops a process or a message from being delayed by the others. Some problems are still solvable asynchronously: a browser lets the user get on with other things while a page loads, however long that takes. Others, such as delivering each multimedia frame before its deadline, need the synchronous model.

The Pepperland example

CDK makes this concrete with a story. Two divisions of the Pepperland army, Apple and Orange, are camped on two hills with the enemy in the valley between. They can win only if they charge together, and they must agree on who leads the charge and when. They communicate only by messengers who are reliable (never captured, in this version) but travel at variable speed.

Event ordering exam

Often we need to know whether one event happened before, after or concurrently with an event at a different process. With no global clock, that is surprisingly hard. Consider a mailing list: X posts a message titled Meeting (m1); Y replies (m2); Z replies to both (m3). Because each message suffers its own independent delay, user A receives them in the order m3, m1, m2, so A sees replies before the message they answer.

If the clocks were perfectly synchronised, each message could carry a timestamp, t1 < t2 < t3, and A could sort by them. Since that is impossible, Lamport's logical time infers the order from two facts that need no clocks: a message is always received after it is sent, and a reply is always sent after receiving the message it answers. Events are numbered so that later events always get larger numbers. In the example, X sends m1 at 1, Y receives m1 at 2, Y sends m2 at 3 and X receives m2 at 4. (The details are in CDK chapter 14.)

Check yourselfA client's request has had no reply for 10 seconds. In an asynchronous system, which conclusion is justified?

1. The server has crashed.
2. The network has lost the request.
3. The server is not responding; it may have crashed, be slow, or the messages may be delayed.
4. The server is fail-stopped.

C. In an asynchronous system there are no bounds on process speed or message delay, so a timeout cannot distinguish a crash from slowness or delay. A and B are possibilities, not conclusions. D is wrong because fail-stop means the failure can be detected with certainty, which needs a synchronous system.

Check yourselfDistinguish latency from jitter with a video-call example.

Latency is the delay from the start of sending a frame to the start of its receipt; high latency makes the conversation lag (you hear answers late). Jitter is the variation in that delay from frame to frame; high jitter makes frames arrive unevenly, so the picture and audio stutter even if the average delay is small.

Check yourselfWhy can't NTP give a guaranteed bound on the difference between two computers' clocks?

Because the time messages themselves suffer variable message delays. When a computer receives "the time is T", it cannot know exactly how long the message spent in transit, so it cannot know exactly how far its own clock is from T. Without a bound on message delay (an asynchronous system), there can be no bound on clock skew.

The Failure Model

In a distributed system, both the processes and the communication channels can go wrong. To design anything that copes, you first need a precise vocabulary for how they can go wrong, because the remedy depends on the kind of failure. CDK classifies failures, following Hadzilacos and Toueg, into three groups: omission failures, arbitrary failures and timing failures.

Omission failures exam

In an omission failure, a process or channel fails to perform actions it is supposed to. It does not do anything wrong; it just fails to do something.

Process omission: crash and fail-stop

For a process, the basic omission failure is a crash: the process halts and executes no further steps, ever. Other processes try to detect crashes with timeouts: "if I hear nothing within T seconds, assume it has crashed". But, as 2.9 showed, in an asynchronous system a timeout only tells you the process is not responding. A fail-stop failure is a crash that other processes can detect with certainty. That is possible only in a synchronous system with guaranteed message delivery, where no reply within the bound really does mean the process has failed.

Communication omission: three places a message can vanish

Omissions also happen in communication. To send a message, process p puts message m into its outgoing buffer (memory managed by the operating system); the channel moves m to q's incoming buffer; and q then takes it from there. A message can be lost at each of these three steps, which gives three kinds of omission.

A checksum, mentioned in the figure, is a small value computed from a message's bytes and sent with it; the receiver recomputes it, and if the two disagree the message was damaged in transit and is thrown away.

Arbitrary (Byzantine) failures exam

Arbitrary failures are the worst possible failure semantics, because any error can occur. A process may produce wrong values or results, omit processing steps, or take extra steps it should not. They are also called Byzantine failures. Crucially, they cannot be detected by non-response, because the faulty process may still reply, or may arbitrarily choose to omit a reply.

The classification table exam

CDK Fig. 2.15 brings the omission and arbitrary failures together. Learn it as a table: for each class, what it affects and what happens. Notice that fail-stop and crash differ only in whether others can detect the failure.

Timing failures exam

A timing failure occurs when a stated time bound is exceeded. Since only synchronous systems state time bounds, timing failures apply only to them. There are three classes.

In an asynchronous system, by contrast, a slow server has no timing failure, because nothing was ever promised. Timing failures have a high impact wherever lateness itself is the harm: in video conferencing and streaming, where late frames are useless; in real-time control such as avionics, car braking or industrial plants; and in trading systems. Real-time operating systems give timing guarantees, but general-purpose ones (Windows, Linux) do not.

Failure detection and the impossibility of agreement

Pepperland illustrates failure detection too. Suppose the two divisions send each other regular status messengers ("still here"). In an asynchronous system, neither can tell whether the other has been defeated or its messenger is just slow. In a synchronous system, a missing messenger proves defeat, although the defeat may have happened at any time after the last messenger left.

Now make things worse: suppose messengers can be captured, so the channel can lose messages. The impossibility of agreement over lossy channels exam says that Apple and Orange then cannot guarantee to decide consistently, however clever their protocol. The stepper walks through the argument.

Masking failures exam

Knowing the failure classes lets us build reliable services from unreliable parts. A service masks a failure of one of its components either by hiding it completely or by converting it into a more acceptable type of failure.

• Checksums turn an arbitrary failure (a corrupted message) into an omission, because the corrupted message is detected and discarded.
• Retransmission hides omissions, as TCP does.
• Replication hides a server crash.
• A crashed process can be replaced and restored from state saved on disk.

Reliable one-to-one communication exam

"Reliable" is used loosely in everyday speech; here it has a precise two-part definition.

Integrity faces two threats. The first is retransmitting protocols that do not reject duplicates: if a sender resends a message whose acknowledgement was lost, the receiver may get it twice. The fix is sequence numbers, so the receiver can spot a number it has already seen. The second is malicious injection of spurious messages, replay of old ones, or tampering, which needs security measures (2.11).

Applying the failure model to a project

In a TCP client-server system such as Assignment 1, the failure model looks like this. The channels use TCP, which masks omission, duplication and corruption, so the channels can be treated as reliable while the connection lasts; a connection can still break, which shows up in Java as an IOException. Processes may crash, but they are not assumed to be Byzantine. And because the system is asynchronous, a socket timeout or a heartbeat (a periodic "I'm alive" message) can only suspect a failure. The client below shows this.

import java.io.*;
import java.net.*;

public class PingClient {
    public static void main(String[] args) throws IOException {
        try (Socket s = new Socket("localhost", 4444)) {      // connect to server
            s.setSoTimeout(2000);                              // block at most 2 s on a read
            PrintWriter out = new PrintWriter(s.getOutputStream(), true);
            BufferedReader in = new BufferedReader(
                    new InputStreamReader(s.getInputStream()));
            out.println("PING");                               // request
            System.out.println("Reply: " + in.readLine());     // reply within the bound
        } catch (SocketTimeoutException e) {
            // Asynchronous system: the server is only NOT RESPONDING.
            // It may have crashed, be overloaded, or the reply may be delayed.
            System.out.println("Server suspected failed (not certain)");
        }
    }
}

1. new Socket("localhost", 4444) opens a TCP connection to a server on this machine, port 4444. The try-with-resources form closes the socket automatically when the block ends.
2. s.setSoTimeout(2000) sets a 2000 ms (2 s) timeout: any later read on this socket blocks for at most 2 s, then throws SocketTimeoutException. This is the client imposing its own bound on an unbounded system.
3. The PrintWriter (with auto-flush true) and BufferedReader wrap the socket's byte streams so the client can write and read lines of text.
4. out.println("PING") sends the request; in.readLine() blocks waiting for the reply line and prints it if it arrives within 2 s.
5. If 2 s pass first, the catch block runs. The comment is the whole lesson: in an asynchronous system the client can only say the server is suspected failed, not that it has crashed.

Check yourselfWhat exactly is the difference between a crash failure and a fail-stop failure, and what does fail-stop require of the system?

In both, the process halts and remains halted. In a fail-stop failure other processes can detect that it has halted, with certainty; in a crash they may not be able to. Certain detection requires a synchronous system with guaranteed message delivery, where no reply within the bound proves failure.

Check yourselfA web server in an ordinary (asynchronous) Internet system takes 30 seconds to answer a request. Is this a timing failure?

1. Yes, a performance failure of the process
2. Yes, a performance failure of the channel
3. No, because no time bound was ever stated
4. No, because it eventually replied

C. Timing failures are defined only relative to a stated bound, so they exist only in synchronous systems. In an asynchronous system a slow server has made no promise and so has not failed. D is a near-miss: replying eventually does not matter; what matters is that there was no bound to exceed.

Check yourselfA channel delivers every message exactly once, but occasionally flips a bit so the content is wrong. Which reliability property fails, and how would you mask the failure?

Integrity fails, because the message received is not identical to the one sent (validity holds: everything is delivered). Mask it with a checksum: corrupted messages are detected and discarded, converting the arbitrary failure into an omission, and retransmission then hides the omission, which is what TCP does.

Check yourselfClassify each: (a) a process's clock runs 1 s/hour fast in a system that promised 1 ms/hour; (b) a router drops packets because its buffer is full; (c) a server returns a wrong balance; (d) a process completes send but the message never enters its buffer.

(a) Clock (timing) failure of a process. (b) Channel omission: lack of buffer space at a gateway. (c) Arbitrary (Byzantine) failure of a process. (d) Send-omission, a process failure.

The Security Model

The failure model assumed that things go wrong by accident. The security model assumes that someone is trying to make them go wrong. Because a distributed system is open (anyone on the network can send it messages), we need a precise picture of what an attacker can do, so that we can say what each defence protects against. Part X covers the mechanisms in depth; this section sets up the model.

Protecting objects

Objects are protected by checking who is asking against what they are allowed to do. Access rights specify who may perform which operations on an object: the owner of a private mailbox may read and delete its messages, while a shared web page may be readable by anyone. A principal is the authority on whose behalf an invocation is made or a result is issued; it may be a user or a process. The server is responsible for verifying the principal behind each invocation and checking its access rights, rejecting requests that are not allowed (for example by consulting an ACL, an access control list naming who may do what). The client, in turn, may check the principal behind the server, to be sure the result really came from the service it meant to use.

The enemy exam

To reason about threats we assume an enemy (also called an adversary) with two powers. It can send any message to any process, and it can read or copy any message sent between processes. It can do this from any computer attached to the network, whether that computer is legitimately connected or not. This is deliberately pessimistic: a design that is safe against this enemy is safe against weaker ones too.

This enemy gives rise to four kinds of threat.

• Threats to processes. A receiver cannot be sure who sent a message, because IP source addresses can be forged. So a server cannot tell which principal sent an invocation, and a client cannot tell whether a result came from the real server or from a spoofer (an impostor pretending to be it).
• Threats to channels. The enemy can copy, alter or inject messages, which threatens their privacy and integrity, or it can save messages and replay them later. Replaying a "transfer $100" message, for instance, would repeat the transfer.
• Denial of service. The enemy sends excessive, pointless invocations or floods the network, overloading the bandwidth or the servers so that legitimate users cannot be served. An example is saturating the computer that controls a building's door locks.
• Mobile code. Code that a host receives may be a Trojan horse: it looks useful, but uses the host process's access rights for other purposes. Hosts must be built carefully, for example by running such code in a sandbox.

Defeating the threats exam

Three techniques defeat these threats, and each builds on the one before.

1. Cryptography and shared secrets. If a process can prove that it knows a secret shared only by itself and one other process, that identifies it as the sender. Encryption scrambles a message using a key, so that only someone holding the decryption key can recover the original.
2. Authentication. The message includes an encrypted portion containing enough of the message to prove it is authentic. For example, a request to a file server can carry the principal's identity, the file ID and a timestamp, encrypted with a key shared only by the client and the file server. The server decrypts that portion and compares it with the rest of the request: if they match, only someone who knew the key could have made it.
3. Secure channel. Encryption and authentication are combined to build a secure channel on top of an existing communication service. It has three properties: (1) each process reliably knows the principal behind the other; (2) the data keeps its privacy and integrity; and (3) each message carries a physical or logical timestamp, which stops it being replayed or reordered. VPNs and SSL/TLS are examples (Part X).

Security has a price in processing and management effort. So the sensible approach is to build a threat model, a list of all the forms of attack with their risks and consequences, and to balance the cost of each countermeasure against the risk it removes.

Check yourselfWhich capability is not assumed of the enemy in the CDK security model?

1. Sending any message to any process
2. Reading or copying any message between processes
3. Acting from any computer connected to the network, legitimately or not
4. Reading the private memory of the server process

D. The enemy works on the network: it can send any message and read or copy any message, from any connected computer. Reading a process's private memory is not one of the enemy's assumed powers.

Check yourselfAn attacker records a valid "transfer $500 to Bob" message and sends it again an hour later. Which threat is this, and which property of a secure channel defeats it?

It is a replay, a threat to channels. It is defeated by property (3) of a secure channel: each message carries a physical or logical timestamp, so the receiver recognises the old message and rejects it. (Encryption alone would not help: the attacker never needed to read the message, only to resend it.)

Check yourselfWhat is a principal, and what two checks does a server make on each invocation?

A principal is the authority (a user or a process) on whose behalf an invocation is made or a result issued. The server (1) verifies the identity of the principal behind the invocation and (2) checks that principal's access rights for the requested operation on the object, rejecting it if they are not sufficient.

Exam Practice and Tutorial 5

This section collects the common mistakes, the real past-exam questions on this topic, a full self-test, and the official Tutorial 5 answers. Try each question before opening the answer.

Past exam questions (2016) exam

2016 Q1(b) · 5 marksGeneral-purpose applications (e.g. a spreadsheet) are provisioned in the cloud and used through a web browser. Which architectural model best describes this, and why? Give three reasons supporting it, and an application for which it is unsuitable.

Model: client-server with thin clients, in the form of a cloud-hosted, multi-tier service. The browser handles only presentation, while the application logic and data run on remote cloud servers.

Reasons (any three):

• installation, upgrades and backups are done centrally;
• it works on any device with a browser, from anywhere;
• clients need little CPU or storage;
• shared data enables collaboration;
• cloud servers scale elastically with demand, through replication and load balancing;
• security administration is centralised.

Unsuitable for: highly interactive, latency-sensitive graphics (CAD, image or video editing, fast-action games), apps that must work offline, and hard real-time control, because network latency and jitter make the response unacceptable.

2016 Q3(a) · 3 marksBriefly explain three fundamental aspects of a communication channel important to a distributed system.

• Latency is the delay from the start of transmission to the start of receipt, made up of propagation time, network access delay and OS processing. It limits responsiveness and affects the choice of timeouts.
• Bandwidth is the amount of data that can be transmitted per unit time, and it is shared by all channels on the network. It limits throughput.
• Jitter is the variation in delivery time of successive messages, and it harms multimedia and real-time streams.

2016 Q3(b) · 2 marksWhat is a timing failure? Give an example where it would have significant impact.

A timing failure is the exceeding of a stated time bound in a synchronous system: a clock drifting beyond its bound, a process step taking too long, or a message taking longer than its bound.

Example: video conferencing, where frames that arrive late are useless and the audio breaks up; or an aircraft or vehicle control system missing a deadline.

2016 Q2(b)-styleState the failure model of a simple multi-threaded TCP client-server system (e.g. Assignment 1).

• Channels: TCP masks omission, duplication, reordering and corruption, so validity and integrity hold while connected. A connection may still break, raising an IOException, and there is no automatic reconnection.
• Processes: subject to crash failures of the client or server. No Byzantine behaviour is assumed, though malformed requests are rejected rather than crashing the server.
• Timing: the system is asynchronous, so timeouts or heartbeats can only suspect a crash.
• Recovery: if the server crashes, completed writes have been persisted and are restored on restart. If a client crashes, the server closes that socket and frees the thread.

Self-test

Q5Name and define the three types of system model.

1. A physical model describes the hardware nodes and networks, abstracted from specific technology.
2. An architectural model describes the components' tasks, their placement and their relationships, as in client-server or P2P.
3. A fundamental model gives a formal description of the properties common to all architectures: interaction, failure and security.

Q6Compare client-server and peer-to-peer.

Client-server is asymmetric and allocates responsibility statically, which keeps management simple and central. Its weaknesses are limited scalability and a single point of failure.

Peer-to-peer is symmetric and allocates responsibility dynamically, so capacity grows with the number of users, and because objects are replicated there is no central point of failure. The price is complexity, and security and availability are harder to achieve.

Q7Describe the four placement strategies.

1. Multiple servers provide one service by partitioning objects (as the Web does) or replicating them (as NIS does), which improves performance and availability.
2. Caching keeps recently used objects near clients, in the browser or a proxy, which lowers latency and load.
3. Mobile code, such as an applet, runs at the client, giving responsiveness and push updates, but it needs a sandbox.
4. Mobile agents are programs that visit resources carrying their data. They reduce communication but raise security issues for both the host and the agent.

Q8Define a mobile agent. How does it differ from mobile code, and why is its use limited?

A mobile agent is a running program (code and data) that travels between computers performing a task for someone, and returns with the results. It differs from mobile code such as an applet, which is downloaded once and runs at the client; an agent instead migrates from host to host with its state.

Its benefit is that it replaces remote invocations with local ones. Its use is limited because hosts must protect their resources from it, which means authenticating whom it acts for; because the agent itself can be refused access or tampered with; and because the same tasks can be done by remote invocation.

Q9Describe the three generations of distributed systems.

1. Early systems had 10–100 homogeneous nodes on a LAN. Openness was not a priority, and QoS was in its infancy.
2. Internet-scale systems are global and cross organisations. Their significant heterogeneity led to open standards, middleware and QoS services.
3. Contemporary systems add mobile nodes (which move and need discovery), ubiquitous nodes (embedded in objects) and cloud nodes (pools of nodes). They are ultra-large, openness and QoS have become research challenges, and they include systems of systems.

Q10Compare two-tier and three-tier architectures.

Both divide an application into presentation, application and data logic. A two-tier architecture needs one message exchange per operation, which gives low latency, but its application logic is split across processes. A three-tier architecture keeps the logic in one place, which makes it maintainable, and it gives clear roles and supports thin clients. The cost is three servers to manage, and extra latency and traffic.

Q11Define middleware and explain the end-to-end argument with an example.

Middleware is software that masks heterogeneity and provides a convenient programming model, such as RMI or CORBA. The end-to-end argument says that some functions need application knowledge at the end points, so the communication layer cannot fully provide them. For example, a large mail transfer resumes on a new TCP connection after a major interruption.

Q12Define synchronous and asynchronous systems; what does the Internet's nature imply for failure detection?

A synchronous system has known bounds on process step time, message delay and clock drift, whereas an asynchronous system has no bounds. The Internet is asynchronous, so timeouts cannot distinguish crashed processes from slow ones or from delayed messages, and fail-stop detection is impossible.

Q13Why can't physical clocks order events perfectly, and how can order be inferred?

Physical clocks drift at different rates, so the skew between them grows, and synchronisation is limited by variable message delays. Order can instead be inferred logically, since a send precedes its receive and a receive precedes the reply to it. Lamport logical timestamps are built on this.

Q14Classify failures and explain masking.

Failures are classified as omission failures (crash, fail-stop, and send, channel and receive omission), arbitrary or Byzantine failures, and timing failures (clock and performance). Masking hides a failure or converts it into a more benign one. Checksums convert an arbitrary failure into an omission, retransmission hides omissions, replication hides crashes, and a process can be restarted from saved state.

Q15Define reliable communication and the threats to integrity.

Reliable communication has validity, meaning outgoing messages are eventually delivered, and integrity, meaning each message is identical to what was sent and there are no duplicates. Integrity is threatened by retransmission that delivers duplicates, which is fixed with sequence numbers, and by malicious injection, replay and tampering, which is fixed with secure channels.

Q16Describe the security model's enemy, threats and defences.

The enemy can send any message and can read or copy any message. The threats are forged identities (of servers and of clients), the copying, altering, injecting and replaying of messages, denial of service, and mobile code. The defences are access rights checked against authenticated principals, cryptography, authentication, and secure channels, which give principal identity, privacy and integrity, and timestamps against replay.

Tutorial 5 (Week 6): official answers official

These are the tutors' official answers posted on Ed (Tutorial 05, Week 6). Staff have confirmed tutorial content is examinable, so learn these definitions as given.

T5-1Briefly explain the difference between a client-server and a peer-to-peer architecture.

In a client-server architecture, a client requests processing or information that it needs from a server. The client waits in a blocking fashion for the reply containing the result, then carries on with its own execution. There are many variants (2.6).

A peer-to-peer architecture suits ad-hoc groupings of participants. There is no central point of failure, so it is reliable, and no central point of control, so it is hard for an adversary to deny service. Some peers typically contribute more than others (seeds, super-peers). Examples are Napster and BitTorrent.

T5-2Briefly explain each architecture variation, giving a reason or benefit for its use.

The tutors answered with the CDK figures. The definitions below are theirs; where their slides only showed a figure, the benefit is taken from CDK and 2.6.

• Services provided by multiple servers. Several server processes interact to provide one service. Objects are partitioned across them (for example, web servers) or replicated (for example, Sun NIS). Benefit: scalability and reliability: the load is shared, and the service survives one server failing.
• Proxy servers and caches. A cache is a store of recently used objects that is closer to the client. New objects are added, replacing existing ones. On a request, the cache is checked for an up-to-date copy, which is fetched if none is available. Benefit: lower latency for clients, and less load on servers and the wide-area network.
• Mobile code and mobile agents. Mobile code is downloaded to the client and executed there (applets, for example). Mobile agents are running programs, both code and data, that travel from one computer to another. Benefit: mobile code gives responsive interaction because it runs locally, and an agent cuts communication by doing its work where the data is.
• Network computers download their OS and application software from a remote file system, and the applications run locally. Benefit: central management and upgrades, and users can work at any machine.
• Thin clients. Application software is not downloaded but runs on the compute server (UNIX, for example); the client only presents the UI. Benefit: cheap, low-power devices get powerful services, and administration is central. However, thin clients are usually not suitable for highly interactive graphical activities.
• Tiered architecture. Tiering is complementary to layering: layering organises services vertically, while tiers spread an application's functions across machines. In two-tier, the client handles view, controls and data manipulation, and the server handles application and data management. In three-tier, the user view and controls are on the client, application logic is on an application server, and a database manager is on a database server. Benefit: each tier can be developed, scaled and maintained independently.

Ed practice quiz (Week 6)

The questions are from the Ed practice quiz; the answers are the guide's worked answers.

Practice 1Devices share files directly with no central server, and the rest carry on if half go offline. Which architecture?

Peer-to-peer: there is no central point of failure or control.

Practice 2DNS runs on many servers, each holding part of the data and cooperating to answer queries. Which variant?

A service provided by multiple servers: the data is partitioned or replicated, which improves reliability and scalability.

Practice 3The browser keeps local copies of images and refetches only if a copy might be outdated. Which variant?

Proxy server / caching.

Practice 4Terminals with no storage or OS; all applications run on a central UNIX server. What is this a poor fit for?

This is a thin client, so it is a poor fit for highly interactive graphical applications such as video editing, because of network latency.

Practice 5Browser, application server and database server as three tiers. What is the advantage over two-tier?

Each tier can be developed, scaled and maintained more independently.