Characterization of Distributed Systems

What Is a Distributed System? exam

Before we can talk about how to build distributed systems, we need to agree on what one is. The question sounds easy, but there are two standard definitions, and they look at the same thing from opposite ends: one from the inside (how the parts work together) and one from the outside (what the user experiences). The exam expects you to know both.

Definition 1: Coulouris (CDK), the mechanism

A component here is any running piece of the system: a program, a server, a database. A networked computer (also called a host) is a machine joined to others by a network. A message is a sequence of bytes that one process sends to another over that network. The word that carries the whole definition is "only". The computers have no shared memory: a program on one machine cannot simply read a variable that lives on another. Everything one part learns about another, it learns by receiving a message. As you will see in 1.3, every difficulty in this subject follows from that one restriction.

Definition 2: Tanenbaum, the user's view

This definition says nothing about messages. It describes the goal: however many machines are really involved, the user should feel they are using one system. That idea is called a single-system image, and the general property of hiding the separate parts is called transparency. Transparency is the most examined idea in this Part and has its own section, 1.9.

The computers can be on different continents or in the same room; the definitions don't care about distance. What matters is that they cooperate on one task or service.

Lamport's quip: what it feels like from the inside

Leslie Lamport, a founder of the field, joked that a distributed system is one in which your work stops because "some machine I have never heard of has crashed". The joke packs in two serious ideas. The first is independent failure: one machine can die while everything else keeps running. The second is hidden dependency: your work quietly relies on machines you never knew existed. The stepper below acts out the lecturer's example, a crashed DHCP server. (DHCP, the Dynamic Host Configuration Protocol, is the service that hands a computer its IP address, the number that identifies it on the network, when it joins.)

A computer network is not a distributed system exam

Every distributed system runs over a computer network, which makes the two easy to confuse. The difference is what each one is for and what it lets you see. A computer network is the plumbing: a medium that moves messages between computers using protocols (agreed rules for formatting and exchanging messages), such as TCP and UDP running over IP, the Internet Protocol. (TCP gives a reliable stream of bytes, UDP sends single unreliable packets; Part III covers both.) In a network the computers are visible and explicitly addressed: you name the machine you want by its IP address. A distributed system is built on top of a network and uses it to provide applications and services, and it hides the fact that many computers are involved.

The two share some problems, such as openness and reliability, but they tackle them at different levels: a network worries about whether a packet arrives, a distributed system about whether a service keeps working. And because a distributed system sits on top of a network, its designer must never assume the network is 100% reliable.

Parallel systems versus distributed systems

The lecturer's notes also compare distributed systems with parallel systems, machines built to run one computation faster by using many processors. Parallel systems come in two kinds. A multiprocessor has several CPUs that share memory over a common bus; an SMP (symmetric multiprocessor), like a multi-core desktop, is the example. A multicomputer has no shared memory: each node has its own, and the nodes are joined by a fast interconnect. MPPs (massively parallel processors) and clusters are examples, and they use homogeneous (identical) hardware and software.

The boundary between parallel and distributed is blurring. A cluster that is extended over the years ends up with several generations of hardware, so it becomes heterogeneous (made of different kinds of machine). And desktop grids such as SETI@home do parallel computation on ordinary home PCs by harvesting their idle processor cycles, which is a distributed system doing a parallel system's job.

Check yourselfWhich statement best captures the difference between the CDK and Tanenbaum definitions?

1. CDK requires the computers to be far apart; Tanenbaum allows them in one room.
2. CDK describes the mechanism (message passing only); Tanenbaum describes the user's view (it looks like one computer).
3. CDK allows shared memory; Tanenbaum does not.
4. They are the same definition in different words.

B. CDK is about how the parts cooperate: only by passing messages, so no shared memory (which rules out C). Tanenbaum is about what users experience: a single coherent system, i.e. transparency. Neither definition cares about distance (A is wrong), and they emphasise different things (D is wrong).

Check yourselfSelf-test Q2: Compare the CDK and Tanenbaum definitions, and a DS with a network.

CDK's definition is about the mechanism, message passing, whereas Tanenbaum's is about the user's view: the system appears as a single computer, which is transparency.

A network moves packets between hosts that are explicitly addressed. A distributed system is built on top of a network, is focused on applications, and hides the multiplicity of computers.

Check yourselfEd practice quiz: a browser talks to a single web server over HTTP. Is that a distributed system?

Yes. It is independent computers (the user's machine and the server) coordinating solely by message passing to deliver one service, which is exactly the CDK definition. The number of machines, whether anything is replicated, and whether the server is multithreaded are not part of the definition, so "only two machines" doesn't disqualify it.

Why Build One? Resource Sharing exam

Distributing a system makes it harder to build (the rest of this Part is a catalogue of how much harder), so there had better be good reasons. This section gives them, and then defines the vocabulary of resource sharing, the main reason of all, whose terms are examined as definitions.

The main motivation: resource sharing

According to CDK, resource sharing is the main motivation for building a distributed system. Beyond that, two course sources each give five practical reasons: the lecture slides and the official Tutorial 1 answer. Their lists overlap but are not identical, so combined they give six. They are ordered below from most to least compelling, and each is tagged with where it comes from.

1. Scalability (both sources; the slides call it "power imbalance" or "load variation"). One machine can't cope, so the load is spread over several, and capacity grows by adding machines. Distributing a big computation over many computers is the example.
2. Reliability (both). Keeping copies at several sites lets the system tolerate faults, as with long-term preservation and backup, or replicated servers.
3. Availability (tutorial only). Replicas keep the service up when one of them fails, which gives high uptime: a website stays up when one of its servers crashes.
4. Inherent distribution (slides only). Sometimes the information, people or activity is naturally spread out: web pages written by different authors, virtual teams working together (CSCW, computer-supported cooperative work), or a supermarket chain's stores and inventory.
5. Functional separation (both). Computers have different capabilities and purposes, so dividing the work between them gives modularity. Clients and servers are one example; sensors that collect data, separate from the computers that process it, are another.
6. Economy (both). Expensive resources can be shared and cheap machines combined: one printer for many users, or a "supercomputer" built from networked PCs.

The vocabulary of resource sharing exam: definitions

Because resource sharing is the point, the words used to describe it are examined as definitions. Learn these four precisely; the rest of the subject uses them constantly.

Why "only through exported operations"? Because that matches physical reality. A resource, such as a disk, sits inside one computer, and other computers can reach it only by sending a message that asks for one of the service's operations. They can never touch the disk directly.

A process is simply a running program. Notice that a server is a process, not a machine: in everyday speech people call the computer "the server", but in this subject the word means the program.

Clients and servers behave differently. Clients are active and short-lived: they start an interaction and finish when they have their answer. Servers are passive, waking only when requests arrive, and they run continuously.

Most importantly, client and server are roles in a single request, not fixed identities. A server can itself be a client of another server. In an object-oriented system the same idea appears as client objects invoking methods on server objects, which is what remote method invocation is about (Part VI).

Check yourselfTutorial 1, Q3 (official answer): List three reasons for using a distributed system.

This is the tutors' official answer, which staff confirmed is examinable. Any three of: economy (cost-effective), reliability (fault tolerance), availability (high uptime), scalability (extendible) and functional separation (modularity). The overall motivation is resource sharing, whether of hardware (disks, printers, scanners), software (files, databases) or other resources (processing power, memory, bandwidth).

Check yourselfSelf-test Q3: Give five reasons for building a DS.

1. Functional separation. Different computers take different roles, such as client and server.
2. Inherent distribution. The information or activity is naturally spread out, as with web pages, CSCW and chains of stores.
3. Load beyond one machine (scalability). When one computer can't cope, the work is spread over several.
4. Reliability. Replicas and backups at several sites let the system tolerate faults.
5. Economies. Expensive resources such as printers can be shared, and PC clusters can act as supercomputers.

Behind all of these is the overall motivation, resource sharing.

Check yourselfWhich is the correct definition of a service?

1. A computer that stores shared files.
2. A running process that accepts requests from other computers.
3. A distinct part of a system that manages a collection of related resources and presents their functionality only through a set of exported operations.
4. Any hardware or software entity that can usefully be shared.

C. B is the definition of a server (a process), D is the definition of a resource, and A confuses the machine with the service. The key phrase for a service is "only through a set of exported operations".

Consequences, Characteristics & Goals exam

The CDK definition said components cooperate only by passing messages. That single word has consequences: the moment you spread a system over several computers, you inherit a set of problems you never had on one machine. This section names them, and they are the reason every later Part exists.

1. Concurrency

The computers are autonomous: each runs on its own and coordinates with the others only by exchanging messages. So concurrent execution, many things happening at the same time, is the normal state of affairs rather than a special case. The catch is that when several of them use the same resource (a file, a bank balance, the last copy of a book), access to shared resources must be coordinated, or they will trample each other's work. The upside is real too: you can increase capacity simply by adding computers. Concurrency as a challenge comes back in 1.8.

2. No global clock

Programs often need to agree on when something happened: which bid arrived first, which file version is newer. On one computer that's easy, because there is one clock. In a distributed system every computer has its own clock, and clocks drift apart. They can be synchronised, but only to a limited precision, which the lecturer puts at milliseconds at best. The reason is again messages: the only way to tell another computer the time is to send it a message, and message delays vary, so the receiver never knows exactly how old the time it was told is.

Here is what that means in practice. Two nodes each write a log entry stamped with their own clock. Each clock is a little wrong, and in different directions, so the timestamps can put events in the wrong order.

3. Independent failures

On one computer, a crash takes everything down at once. In a distributed system one component can fail while the others keep running, and the others don't find out straight away. A network fault, for instance, isolates computers without stopping them: both sides carry on, each unable to hear the other. The truly hard part is that a program can't tell a failed network from a slow one, or from a crashed server: in every case, the reply just hasn't arrived. The stepper shows three different worlds that look identical from the client's side.

4. Heterogeneity (the slides' addition)

The lecture slides add a fourth consequence: heterogeneity, meaning the computers, operating systems, networks and programming languages involved can all be different. CDK treats this as a challenge rather than a consequence (see 1.6), but a question asking for four consequences expects it.

Characteristics and goals (slides)

The slides also list the characteristics of a distributed system, which restate the consequences from a slightly different angle. Its activities run in parallel and interact by message passing, since there is no shared memory; its resources are shared; there is no global state (no process can know the current state of the whole system, because everything it learns arrives late, in messages); and there is no global clock.

Finally, the slides give the goals of a distributed system: connecting users and resources, transparency, openness, scalability, enhanced availability, and concurrency. Most of these reappear as the challenges of 1.5, which makes sense: a goal is just a challenge you have met.

Check yourselfSelf-test Q1: Define a DS and give its three consequences.

CDK defines a distributed system as one in which components located at networked computers communicate and coordinate their actions only by message passing. Three consequences follow. The first is concurrency: access to shared resources must be coordinated. The second is that there is no global clock, because synchronisation is limited by variable message delays. The third is independent failures: a component can't tell a crash from a slow network.

Check yourselfTutorial 1, Q4 (official answer): Briefly explain four consequences of using distributed systems.

The tutors' official answer (examinable) names four: concurrency, heterogeneity, no global clock, and independent failures. CDK lists only three; heterogeneity is the slides' addition, and a question asking for four expects it as the fourth. Explain each in a line: concurrent execution means shared resources need coordinated access; heterogeneity means different hardware, OSs, networks and languages must interoperate; there is no single clock, and clocks can be synchronised only to limited precision because message delays vary; and a component can fail while the rest keep running, without them knowing at once.

Check yourselfEd practice quiz: node A logs an event at 10:00:05 by its clock, and node B logs one at 10:00:03 by its clock. You may conclude…

1. B's event happened two seconds before A's.
2. A's event happened after B's, but by an unknown amount.
3. Nothing about their real order.
4. The events were concurrent.

C. Nothing about their real order. There is no global clock and local clocks drift, so timestamps taken on different machines can't be compared. The figure above shows a world in which A's event really came first despite its later timestamp.

Check yourselfA client has sent a request and received no reply after 30 seconds. Which conclusion is justified?

Only that no reply has arrived yet. The request may have been lost, the server may have crashed, the reply may have been lost, or the server or network may just be slow. This is the "independent failures" consequence: in a message-only system a failed network (or server) can't be told apart from a slow one, so the client can at best suspect a failure.

Examples and Trends

Definitions are easier to hold onto when you can picture real systems. This section tours the examples CDK uses, the Internet that most of them run on, and the four trends that are shaping today's distributed systems. The examples are background; the trends are examinable.

Where distributed systems appear

Almost every application domain relies on them: finance (eCommerce, banking), the information society (search engines, social networks), entertainment (online games, streaming), healthcare (patient records), education (e-learning), transport (GPS, maps), science (grids and clouds for big computations) and the environment (sensor networks that give flood warnings). CDK picks three to study, because each shows a different side of the subject.

CDK's three examples

The Internet and intranets

The Internet is a vast collection of interconnected networks of many types, and it is itself a huge distributed system with open-ended services. An intranet is a portion of the Internet that is separately administered by one organisation and protected by a firewall, a filter at its boundary that blocks messages by their source, destination or protocol. Firewalls can also block legitimate sharing, however, so finer-grained security mechanisms are needed too (Part X). ISPs (Internet Service Providers) connect individual users and organisations to the Internet, and backbones, high-capacity network links, connect the intranets to each other.

Four trends exam

Four developments are reshaping distributed systems. For each, know what it is and what new challenge it brings.

1. Pervasive networking and the modern Internet

Many kinds of network, such as WiFi, Bluetooth and cellular, are all abstracted by the Internet protocols, so a device can connect anywhere, at any time, without its software caring which kind of network it is on.

2. Mobile and ubiquitous computing

These overlap but are distinct. Mobile computing is computing while on the move or away from home, with continued access to your home intranet. Using resources that happen to be nearby, such as the printer in the hotel you are visiting, is called location-aware or context-aware computing, and its challenges are variable connectivity and outright disconnection. Ubiquitous computing means many small, cheap computing devices embedded in everyday objects, so many that they are scarcely noticed. A device visiting such an environment needs spontaneous interoperation (working with devices it has never met, without set-up) and service discovery (finding out which services are available here).

3. Distributed multimedia

These systems support continuous media, such as audio and video, as well as discrete media (text, pictures). Continuous media have a temporal dimension: a video is only correct if its frames arrive at the right rate and within a maximum delay. That is a question of quality of service (QoS; see 1.8). Webcasting is an example. To manage this, a system needs an extensible range of encoding formats, QoS mechanisms, resource scheduling, and a way to adapt when the required QoS can't be met.

4. Distributed computing as a utility (cloud)

Here computing resources are rented, not owned, the way you rent electricity from the grid instead of running your own generator. The resources can be physical, namely storage and processing (often on virtualized nodes, i.e. simulated machines carved out of real ones), or software services. A cloud is a set of Internet-based application, storage and computing services sufficient for most users' needs; the idea is "everything as a service", paid for per use. Clouds run on clusters: interconnected commodity or blade computers that cooperate to give one high-performance capability. Grid computing, aimed at science, was a precursor.

Check yourselfWhat is the difference between mobile computing and ubiquitous computing, and what does a device visiting a ubiquitous environment need?

Mobile computing is computing on the move or away from home, keeping access to your home intranet and using nearby resources (location- or context-aware computing); its challenges are variable connectivity and disconnection. Ubiquitous computing is many small, cheap devices embedded in everyday objects, scarcely noticed. A visiting device needs spontaneous interoperation and service discovery.

Check yourselfWhy does distributed multimedia raise a problem that ordinary file transfer doesn't?

Continuous media (audio, video) have a temporal dimension: frames must arrive at a set rate and within a maximum delay, or the result is wrong even if every byte eventually arrives. That needs quality-of-service guarantees, resource scheduling and adaptation when QoS can't be met. A file transfer only needs the bytes to arrive correctly, however long it takes.

The Eight Challenges at a Glance exam

Everything so far has explained why distributed systems are attractive and why they are awkward. The design problems that result are organised as a list of challenges, and this list is the core of the Part. CDK lists eight; the slides' summary lists the first seven and leaves out quality of service. Sections 1.6 to 1.9 take them one at a time; here is the whole set, with the question each one asks of a scenario.

The scenario technique exam

A favourite exam question gives you a scenario (a campus computer lab, an online shop, a ride-sharing app) and says "list and explain N challenges with respect to this example". The marks go to answers that are tied to the scenario, not to a recited list. The reliable way to get them is to take each challenge through four steps.

Check yourselfWhich challenge is in CDK's list of eight but missing from the lecture slides' summary?

1. Openness
2. Transparency
3. Quality of service
4. Concurrency

C. Quality of service. The slides list the first seven (heterogeneity, openness, security, scalability, failure handling, concurrency, transparency); CDK adds QoS as the eighth.

Check yourselfA student answers "Scalability: the system must handle lots of users" for a 1-mark part of a scenario question. What is missing?

Almost everything after the name. There is no proper definition (remains effective as users and resources grow significantly), no instance from the scenario (which server, which load spike), and no remedy (replication, caching, partitioning). "Lots of users" is generic, so it earns little of the "with respect to this example" credit.

Heterogeneity & Openness

The first two challenges are about difference. Heterogeneity asks how computers that are built differently can work together at all. Openness asks how a system can keep growing when new parts come from different people. They sound alike, and the exam likes to check that you can tell them apart.

Heterogeneity: five aspects

Heterogeneity means variety: the parts of a distributed system differ from each other, yet they must interoperate. CDK lists five aspects in which they can differ. Notice that nearly every solution is either an agreement (protocols, formats, standards) or middleware that hides the difference.

An API (application programming interface) is the set of functions a program calls to use something, here the operating system's networking. The slides list further aspects of heterogeneity: communication architectures, software interfaces, security measures, and information representation, such as ASCII versus EBCDIC (two different codes for turning characters into numbers, so the same byte means a different letter on each).

The byte-order problem, step by step

Hardware heterogeneity is easiest to see in byte order. A whole number (an int) takes four bytes in memory, and machines disagree about which byte goes first. A little-endian machine stores the least significant byte first; a big-endian machine stores the most significant byte first. Send the raw bytes from one kind to the other and the number changes.

Middleware exam

Examples are CORBA, which works across different programming languages, and Java RMI (Remote Method Invocation), which works within a single language, Java. Middleware usually runs over the Internet protocols (which already hide the differences between networks), and on top of them it gives programmers a uniform computational model: one way of thinking about the whole system, such as remote object invocation, remote event notification, remote SQL database access, or distributed transactions. Part IV and Part VI go deeper.

Mobile code and the virtual machine approach

Mobile code is code sent from one computer to run on another, such as a Java applet or the JavaScript in a web page. It runs straight into heterogeneity, because a compiled program (an executable) is tied to one instruction set and operating system. The virtual machine approach gets round this. Programs are compiled not for a real processor but for a virtual one (Java bytecode), and the JVM (Java Virtual Machine), the program that runs bytecode, is implemented once per platform. After that, every program runs everywhere.

Check yourselfSelf-test Q4: What is middleware? How are heterogeneity and mobile code handled?

Middleware is a software layer that gives a programming abstraction and masks the differences between networks, hardware, operating systems and languages; CORBA and Java RMI are examples. Differences between networks are masked by the Internet protocols. Mobile code has the problem that executables are tied to an instruction set and OS, and the virtual machine approach solves it: the JVM is implemented once per platform, so the same bytecode runs everywhere.

Check yourselfA little-endian client sends a raw 4-byte integer to a big-endian server, which reads a different value. Which aspect of heterogeneity is this, and what is the fix?

Computer hardware heterogeneity: the two machines represent data differently in memory (byte order). The fix is an agreed external data format: both sides convert to and from one agreed representation for data in transit.

Openness exam

Openness requires the key interfaces to be published: the exact rules for talking to each service are written down where anyone can read them. Publishing often bypasses slow official standardization. The IETF (Internet Engineering Task Force) publishes RFCs ("Requests for Comments"), which specified TCP/IP and then FTP, email and telnet; publishing them is what made the Web possible. The W3C publishes the Web's standards in the same way, and the slides name other bodies too: ANSI, ISO, IEEE and OMG.

Open distributed systems have three properties:

1. They publish their key interfaces.
2. They use a uniform communication mechanism, with published interfaces to shared resources.
3. They can mix heterogeneous hardware and software from different vendors, but each component's conformance must be tested (checked against the published standard).

The benefits are extensibility at both the hardware and the software level, and vendor independence: you are never locked in to one supplier. Publication is only the start, though; integrating components built by different people is the hard part. The slides add the IEEE POSIX view, in which open specifications for interfaces, services and formats give application portability (a program moves between systems), interoperability (systems work together) and user portability (people's skills move with them). For example, Chrome, Firefox or a Python client can all talk to a server written in Java.

Openness versus heterogeneity

Check yourselfSelf-test Q10: What is openness, and how does it differ from heterogeneity?

Openness is extensibility and re-implementability: new services can be added and used by many clients. It is achieved by published interfaces (RFCs, W3C), a uniform communication mechanism, and conformance testing, and it gives vendor independence. Heterogeneity is about coping with platform differences, whereas openness is about extending the system through published interfaces.

Check yourselfWhich of these is not one of the three properties of an open distributed system?

1. Key interfaces are published.
2. A uniform communication mechanism with published interfaces to shared resources.
3. All components come from the same vendor, so they are guaranteed compatible.
4. Heterogeneous components from different vendors can be mixed, with conformance tested.

C. Single-vendor is the opposite of openness; vendor independence is one of its benefits. A, B and D are the three properties.

Security & Scalability exam

The next two challenges are about pressure from outside. Security asks what happens when someone wants the system to misbehave. Scalability asks what happens when far more people want to use it than it was built for. Both come up in nearly every scenario question.

Security: the components

The information resources in a distributed system are valuable, and messages travel over networks that others can see. Security of information resources has three components, plus a fourth that the slides add.

The slides also list the mechanisms used: encryption (scrambling data so only a key-holder can read it, e.g. the Blowfish and RSA algorithms), authentication (proving who someone is, e.g. by password or public key) and authorization (deciding what an authenticated party may do, e.g. with ACLs).

Firewalls are not enough

A firewall guards the boundary of an intranet, so it is tempting to think it solves security. It doesn't, because it doesn't govern how users inside the intranet use resources, nor the use of resources outside it.

Encryption meets two challenges. The first is sending sensitive data secretly, such as patient records or credit card numbers. The second is identifying the remote user or agent: is this really a doctor? Is this really my bank? Two problems, however, are not fully solved:

• Denial of service (DoS). The service is flooded with pointless requests so that genuine users can't get in. It is mostly countered by catching the culprits afterwards rather than by preventing it.
• Security of mobile code. An email attachment may seem harmless but in fact access local resources or join a DoS attack.

Security is covered in depth in Part X.

Check yourselfSelf-test Q9: Give the security components, and two unsolved challenges.

The components are confidentiality, integrity and availability, and the slides add non-repudiation. Encryption gives secrecy and lets you authenticate the remote party. Two challenges remain unsolved: DoS, and the security of mobile code. Firewalls are not enough, because they don't control insiders.

Check yourselfA customer orders a TV online, then claims they never placed the order. Which security component is at stake, and which mechanism addresses it?

1. Confidentiality; encryption
2. Integrity; a checksum
3. Non-repudiation; a digital signature
4. Availability; a firewall

C. Denying having sent something is repudiation; a digital signature on the order is proof of sending. This is exactly the bookstore's "a customer denies ordering" case in 1.10.

Scalability: the definition exam

The four challenges of scalable design exam

The challenges below use big-O notation: O(n) means "grows in proportion to n", and O(log n) means "grows like the logarithm of n", which is very slowly: doubling n only adds a constant amount.

1. Controlling the cost of physical resources. The resources needed for n users should grow at most O(n), so the system can be extended at reasonable cost. If 1 file server supports 20 users, then 2 should support 40. The point is to add servers rather than overload one.
2. Controlling performance loss. For data that grows with the system, access time should grow no worse than O(log n), which means using hierarchic rather than linear structures. The example is the DNS table that maps names to addresses.
3. Preventing software resources running out. Future demand is hard to predict, but over-provisioning costs too, because oversized fields waste space in every message. The example is 32-bit IPv4 addresses running out, which led to 128-bit IPv6 and much software change. Y2K-like problems (two-digit years) are of the same kind.
4. Avoiding performance bottlenecks. The answer is decentralized algorithms. DNS's predecessor was one master hosts file that everyone consulted, whereas DNS partitions the table across locally run servers. A popular ("hot") web page, similarly, is handled by caching and replication.

Scaling techniques, and a web example

The general techniques for scaling are replication (keeping copies), caching (keeping recently used data close to where it is used), multiple servers sharing common tasks, hierarchy, and partitioning (splitting data or work into parts handled by different servers). The lecturer gives a web example: static web content scales by adding servers and adjusting DNS so the name points at all of them, but dynamic content also needs the back-end database to be replicated and synchronised.

Check yourselfSelf-test Q7: Explain the four challenges of scalable design.

1. Cost of physical resources. This should grow at most O(n) with the number of users, for example one server for every 20 users.
2. Performance loss. Access time should grow at most O(log n), which hierarchic structures such as DNS achieve.
3. Software resources running out. IPv4's 32-bit addresses ran out, which led to IPv6's 128-bit addresses.
4. Bottlenecks. These are avoided by decentralizing, as when the single hosts file gave way to DNS, and by caching and replicating hot data.

Check yourself"System X is scalable because it answers every request in under 10 ms." What is wrong with this claim?

It confuses speed with scalability. Response time today says nothing about how cost and performance grow when users and resources increase significantly. To show scalability you would argue that resources needed grow at most O(n), access time at most O(log n), no software resource runs out, and there is no central bottleneck.

Failures, Concurrency & QoS exam

The next three challenges come straight from the consequences in 1.3. Independent failures become the failure handling challenge; concurrent execution becomes the concurrency challenge; and the timing demands of multimedia become quality of service.

Failure handling: three words to keep apart exam

The slides define three terms that are easy to confuse, and the exam rewards getting them exactly right.

What makes failures hard in a distributed system is that they are partial: some components fail while others continue (the "independent failures" consequence). The system must keep going around the broken parts.

Five techniques for dealing with failures exam

CDK gives five techniques. The slides list only the first four; CDK adds redundancy.

1. Detecting a failure means noticing it. Checksums (a number computed from the data and sent with it; if the receiver's recomputation differs, the data was corrupted) detect corrupted data, and heartbeats (regular "I'm alive" messages) are another means. A crashed remote server, however, can't be detected, only suspected: as 1.3 showed, silence looks the same whether it is crashed or slow.
2. Masking hides a detected failure, or makes it less severe. You can retransmit lost messages, write data to two disks, or drop a corrupt message (so it looks merely lost, which retransmission can then fix). Masking is not guaranteed in the worst case: if every retry is lost, or both disks fail, it can't help.
3. Tolerating a failure means exposing it to the client or user in a controlled way. A browser that reports "cannot contact server" instead of waiting forever is tolerating the failure; timeouts and exceptions are the usual tools.
4. Recovery means rolling back permanent data to a consistent state after a crash, using rollback and logs (a log records each change so it can be undone or redone).
5. Redundancy means duplicating components: at least two routes between any two routers, each DNS table held on at least two servers, or a replicated database with client failover (clients switch to a replica when the main copy fails). Its difficulty is keeping replicas of fast-changing data up to date.

Availability

A distributed system can achieve high availability precisely because failures are independent: a failure only affects the work that uses the failed component, so users or servers can move to other computers. One crashed PC in a lab doesn't stop anyone else.

Check yourselfSelf-test Q8: Define fault, failure and fault tolerance, and list the failure-handling techniques.

A fault is the cause, and a failure is a deviation from the specification; fault tolerance means there is no failure despite faults. The techniques are:

1. Detecting failures, for example with checksums, although a remote crash can only be suspected.
2. Masking them, for example by retransmission or mirrored disks.
3. Tolerating them, by reporting the error or using timeouts.
4. Recovering from them, by rollback.
5. Redundancy, such as two routes, or replicated DNS and databases with failover.

Availability is the proportion of time the system is usable.

Check yourselfAn email client can't reach its server and shows "Server unavailable, will retry in 5 minutes". Which technique is this?

1. Detecting
2. Masking
3. Tolerating
4. Recovery

C. Tolerating. The failure is exposed to the user in a controlled way rather than hidden (masking) or left to hang. If the client had silently retried until it worked, never showing anything, that would be masking.

Concurrency

Several clients may access a shared resource at the same time; in an online auction, for instance, bids pile up near the deadline. A server can't sidestep this by serving one request at a time, because that limits throughput (the number of requests handled per second). So servers process requests concurrently, typically in threads (several sequences of execution running inside one process and sharing its memory; Part IV). But uncontrolled interleaving corrupts data: when two threads' steps mix in an unlucky order, the result can be something neither intended. In CDK's example, concurrent bids "Smith: $122" and "Jones: $111" end up stored as Smith: $111, Jones: $122. The stepper shows one way that can happen.

A lock is a token only one thread can hold at a time; a thread that wants it while another holds it must wait. A semaphore is a counter-based generalisation of a lock. In Java, marking a method synchronized means a thread must hold the object's built-in lock to run it. Here is the auction item written as a safe shared object, exactly as in the study guide:

// Shared auction item, safe for concurrent client threads (threads: see §4)
public class AuctionItem {
    private String bidder = "none";
    private int amount = 0;

    // synchronized: one thread at a time per object, so (bidder, amount) change together
    public synchronized boolean bid(String who, int value) {
        if (value <= amount) return false;   // reject bids that are not higher
        bidder = who;
        amount = value;
        return true;
    }

    public synchronized String leader() {     // consistent read of both fields
        return bidder + ": $" + amount;
    }
}

Reading it line by line:

• The two private fields, bidder and amount, are the shared state. Because they are private, the only way to touch them is through the two methods, which are both synchronized.
• bid is synchronized, so while one thread is inside it no other thread can enter bid or leader on the same object. The check (value <= amount) and the two assignments therefore happen as one indivisible unit: nobody can sneak in between setting bidder and setting amount, which is exactly the gap the stepper above exploited.
• The check also enforces the auction's rule: a bid that isn't higher than the current one is rejected (return false).
• leader is synchronized too. Without that, a reader could see the new bidder with the old amount halfway through someone else's bid. Synchronizing the read gives a consistent snapshot of both fields.

The slides add three further requirements for concurrency:

• Scheduling must be fair: no waiting client should be starved forever.
• Dependencies must be preserved. In a distributed transaction, for instance, the buyer's funds must be checked before the order is finalized.
• Deadlock must be avoided: the situation where two parties each hold a resource the other is waiting for, so neither can ever proceed.

Check yourselfSelf-test Q11: How should a shared object deal with concurrent requests?

Processing requests serially limits throughput, but uncontrolled interleaving corrupts data, as with the swapped Smith/Jones bids. The object should therefore synchronize its operations, using locks, semaphores or synchronized. It should also schedule fairly, preserve dependencies with transactions, and avoid deadlock.

Check yourselfIn AuctionItem, why is leader() synchronized when it only reads?

So the read is consistent. If it weren't synchronized, it could run while another thread is halfway through bid(), after bidder has changed but before amount has, and report a winner with the wrong amount. Synchronizing it means it can only run when no bid() is in progress on that object.

Quality of service

Quality of service (QoS) is the eighth challenge, the one CDK lists and the slides' summary leaves out. It concerns a system's non-functional properties, meaning not what it does but how well: reliability, security and performance, plus adaptability to changing configurations.

Performance here has a specific meaning: the ability to meet timeliness guarantees. A stream of video frames, for example, must be shown within time limits; a frame that arrives late is as bad as one that never arrives. Meeting such deadlines needs guaranteed computing and network resources. Applications reserve the resources they need, resource managers provide the guarantees, and reservations that can't be met are rejected. This applies to the operating system (CPU time, memory) as well as to the network. Ordinary networks perform well, but they give no guarantees under heavy load.

Check yourselfWhich four properties does QoS cover, and what does "performance" mean in that context?

QoS covers the non-functional properties reliability, security and performance, plus adaptability to changing configurations. Performance means the ability to meet timeliness guarantees (e.g. video frames shown within time limits), which requires guaranteed resources: applications reserve, resource managers guarantee, and unmeetable reservations are rejected.

Transparency exam: most examined

Tanenbaum's definition said a distributed system should appear to its users as a single computer. Transparency is the name for achieving that: hiding the fact that the system is made of separate parts. It is the most heavily examined idea in this Part, usually as "list and explain the transparencies" or "which transparency does this example show?"

"Transparent" here means "invisible", as in a clear pane of glass: you look straight through the machinery without noticing it. The eight forms below come from two standards, ANSA (the Advanced Networked Systems Architecture) and ISO RM-ODP (the Reference Model for Open Distributed Processing), although CDK replaces their migration transparency with the broader mobility transparency. For each one, know what it enables and an example.

The eight transparencies, one picture each

Check yourselfSelf-test Q5: List and define the eight transparencies, with examples.

1. Access transparency means local and remote resources are used with the same operations, as with an NFS mount.
2. Location transparency means resources are used without knowing where they are, as with URLs and DNS.
3. Concurrency transparency means processes share resources without interference, so two customers ordering the last book do not disrupt each other.
4. Replication transparency means replicas are used without users knowing of them, as with the google.com replicas.
5. Failure transparency means faults are concealed, as when email retries until it is delivered.
6. Mobility transparency means resources and clients can move without affecting users, as when a call continues across cells.
7. Performance transparency means the system can be reconfigured under load.
8. Scaling transparency means the system can grow without changing its structure or algorithms.

Check yourselfEd practice quiz: a user is served by one of forty machines on three continents without knowing which. Which property is this?

Transparency, specifically location transparency (they don't know where the machine is) and replication transparency (they don't know there are forty copies).

Check yourselfMatch each example to its transparency: (a) your laptop opens a file in a mounted network drive with the usual Open dialog; (b) a video-call app keeps the call going as you walk from WiFi onto mobile data; (c) a shop's site adds servers at Christmas and nobody's app needs updating.

(a) Access: identical operations for local and remote files. (b) Mobility: the client moves without affecting the call. (c) Scaling (growth without changing structure or client code); if the servers are added and removed automatically as load varies, that is also performance transparency.

Network transparency exam

Are URLs transparent?

A URL such as http://www.a.com/page.html names a server by its DNS name, not its IP address, so it is location-transparent: the server can change address and DNS will follow. But it is not mobility-transparent: move the page to another domain, and every link to the old URL breaks. The stepper shows both.

Replication and URLs: two views that both hold

Replication and URLs need more care. CDK says identifiers containing domain names prevent full replication transparency: DNS can map one name to several hosts, but each lookup returns only one, so a replication scheme that wants to use all its replicas must name each one separately. The lecturer, on the other hand, cites DNS mapping a name to many hosts as an example of replication transparency from the user's view, because the user types one name and is served by some replica. Both points hold: they are looking at the system from different sides.

When transparency fails, or isn't wanted

Transparency has limits. Middleware can't make a network failure vanish completely; what it does is turn network and process failures into exceptions that the program must handle, a controlled exposure (the "tolerate" technique from 1.8).

And transparency isn't always wanted. A location-aware user wants to know where things are: they want the nearest printer, not any printer, or the local mail server. Hiding location would be unhelpful there.

Two extra transparencies from the slides

The slides add two application-level transparencies that are not among CDK's eight. Persistence transparency masks the deactivation and reactivation of objects (an object can be saved to disk and brought back without its users noticing). Transaction transparency hides the coordination needed to make a group of operations happen all together or not at all.

Check yourselfSelf-test Q6: What is network transparency? Is an HTTP URL location-transparent? Mobility-transparent?

Network transparency is access and location transparency together, as with an email address. An HTTP URL is location-transparent, because it uses a DNS name rather than an IP address. It is not mobility-transparent, though, because moving a page to a new domain breaks the links to it.

Check yourselfNetwork transparency consists of…

1. all eight transparencies
2. access and location transparency
3. location and mobility transparency
4. access, location and failure transparency

B. Exactly two: access and location. C confuses location with mobility; D adds failure, which email happens to show too but which is not part of the definition.

Worked Scenarios exam: scenario

Knowing the eight challenges is half the job; the other half is spotting them in a scenario you have never seen, which is how the exam asks. This section works through two scenarios in full: the lecture's online bookstore, and the computer-lab question from the 2016 final exam.

The online bookstore (from the slides)

The slides apply the challenges to one scenario: customers connect to your web server to browse and order books. Each challenge is introduced by a "what if…?" question, which names the challenge it raises and leads to a remedy. That is exactly the pattern to follow in an exam answer. The numbered badges in the picture match the rows of the table.

A few terms from the table: a load balancer spreads incoming requests across several servers; a transaction is a group of operations that either all happen or none do, so a crash mid-order can be rolled back; and LAMP (Linux, Apache, MySQL, PHP) and J2EE (Java's enterprise platform) are ready-made software stacks built on open standards.

The computer lab: 2016 final exam, Q1(a) past exam, 5 marks

Check yourselfPractice: a university library runs an online catalogue used from three campuses; students search it and place holds on books. Give three challenges with respect to this example, using the four-step recipe.

One possible answer (other well-applied challenges are equally valid):

1. Concurrency: shared resources must be used concurrently without interference. Two students may place a hold on the last available copy at the same moment, so the hold operation must be synchronized (a lock or a transaction) so that only one succeeds and the other sees a consistent "unavailable".
2. Failure handling: the service should keep working despite faults. If the catalogue server at one campus crashes, students there should fail over to a replica; the crash is suspected by timeout, and a hold half-recorded during the crash is rolled back.
3. Transparency (location and replication): users shouldn't need to know where the catalogue runs or how many copies there are. Students on every campus use one name for the catalogue, and DNS or a load balancer picks a replica for them.

Check yourselfIn the bookstore, "a customer denies having ordered" is filed under security. Which component, and which mechanism?

Non-repudiation (the slides' fourth security component), provided by a digital signature on the order, which proves who sent it.

Case Study: the World Wide Web

The Web is the distributed system everyone has used, which makes it a good place to see the ideas of this Part working together: resource sharing, client and server roles, openness, and the limits of transparency. CDK treats it briefly, and so does the exam.

What the Web is

The Web is a system for publishing and accessing resources and services over the Internet. It is open in two ways. First, its standards are freely published, so any browser that conforms to them works with any conforming server. Second, it can be extended with new content types (via browser plug-ins) and new URL schemes. It rests on three components.

1. HTML

HTML (HyperText Markup Language) specifies a page's content, its layout and its links to other resources, written like <A HREF="url">text</A>. Only the browser interprets HTML; the server just states the content type of what it sends.

2. URLs

URLs (Uniform Resource Locators, a kind of URI, Uniform Resource Identifier) identify resources. They take the general form scheme:scheme-specific-identifier, with schemes such as http:, mailto: and ftp:. An HTTP URL has the form http://servername[:port][/pathName][?query][#fragment] (square brackets mark optional parts). It identifies both the server, by its DNS name (the default port is 80), and the resource on that server.

3. HTTP

HTTP (HyperText Transfer Protocol) is the protocol between browsers and servers. Its main features:

• It is a request-reply protocol: the browser sends a request, the server sends back one reply. GET retrieves a resource, and POST supplies data to the server (e.g. a filled-in form). Errors come back as status codes, such as 404 (not found).
• It labels content with MIME content types such as text/html or image/gif, so the browser knows how to handle what arrives; the browser states which types it prefers.
• It fetches one resource per request, so a page with 9 images takes 10 requests (one for the page, one per image). That is why browsers make requests concurrently.
• It provides simple access control by a password challenge.

The stepper traces a browser fetching a page with one embedded image, the example from CDK.

Dynamic pages, downloaded code and web services

Dynamic pages. Here the URL names a server program (in CDK's terms a CGI program, from the Common Gateway Interface), not a file. The program generates HTML from the query string (with GET) or from the request body (with POST), often by consulting a database. The browser can't tell the result from static content: either way, HTML arrives.

Downloaded code is mobile code (1.6) on the Web. JavaScript validates input and updates parts of a page, asynchronously in the case of AJAX (the page fetches data in the background without reloading). Applets are downloaded Java programs.

Web services. HTML is tied to presentation (how a page looks), which makes it unsuitable for programs talking to programs. XML, by contrast, is self-describing structured data. In the REST style, every resource has a URL and accepts the same small set of operations: GET, POST, PUT, DELETE.

The Web's problems

Check yourselfSelf-test Q13: Name the Web's three technologies. How does a dynamic page differ from a static one?

The three technologies are HTML, which gives content and links; URLs, which give the server's DNS name, path, query and fragment; and HTTP, a request-reply protocol with GET and POST, MIME types, and one resource per request. A dynamic page is generated by a server program (CGI) from the query or POST data, often using a database, but the browser sees no difference from a static one.

Check yourselfA page contains 4 images and nothing else embedded. How many HTTP requests does the browser make to display it, and why?

1. 1
2. 4
3. 5
4. It depends on the MIME type

C. 5. HTTP fetches one resource per request: one request for the page, then one for each of the 4 images.

Check yourselfTake apart http://www.w3.org/standards/faq.html#conformance.

Scheme http; server www.w3.org (a DNS name; no port given, so the default 80); path standards/faq.html; fragment conformance, a part within the page. There is no query.

Pitfalls & Tutorial 1 exam

This last section pulls the Part together: one picture of how the ideas connect, the mistakes that most often cost marks, and the official Tutorial 1 answers, whose wording is the closest thing you have to what markers expect.

Common pitfalls

Tutorial 1 (Week 2): official answers official

These are the tutors' official answers from Ed, Tutorial 01, condensed. Staff confirmed tutorial content is examinable, and this wording is the closest thing to what markers expect, so reuse it.

T1-1Provide a definition of a distributed system.

Give both definitions. According to Coulouris, it is a system in which hardware or software components located at networked computers communicate and coordinate their actions only by passing messages. According to Tanenbaum, it is a collection of independent computers that appears to its users as a single coherent system.

T1-2Briefly explain the difference between a computer network and a distributed system.

A computer network is a collection of spatially separated, interconnected computers that exchange messages based on specific protocols. Computers are addressed by IP addresses, so they are visible to users. A distributed system, by contrast, is multiple computers on the network working together as one system. The spatial separation of the computers and the communication between them are hidden from users. The contrast to draw is therefore visibility versus transparency. For a full answer, add that every distributed system relies on the services of a network.

T1-3List three reasons for using a distributed system.

Any three of: economy (cost-effective), reliability (fault tolerance), availability (high uptime), scalability (extendible), and functional separation (modularity). The overall motivation is resource sharing, whether of hardware (disks, printers, scanners), software (files, databases) or other resources (processing power, memory, bandwidth).

T1-4Briefly explain four consequences of using distributed systems.

The four are concurrency, heterogeneity, no global clock, and independent failures (1.3). CDK lists only three; heterogeneity is the slides' addition, and a question asking for four expects heterogeneity as the fourth.

Ed practice quiz (Week 2)

Ed doesn't show the answers to its practice quiz, so the answers below are worked out from the course material rather than official. Items 3–5 also appear earlier in this Part, next to the idea they test.

Ed quiz 1According to Coulouris, components coordinate their actions…

Only by passing messages.

Ed quiz 2Tanenbaum's definition emphasises that a distributed system…

Is a collection of independent computers that appears to its users as a single coherent system.

Ed quiz 3–5(a) Served by one of forty machines on three continents without knowing which? (b) Is a browser talking to one web server over HTTP a DS? (c) A logs 10:00:05, B logs 10:00:03: what can you conclude?

(a) Transparency: location and replication. (b) Yes: independent computers coordinating solely by message passing to deliver one service; the number of machines, replication and multithreading are not part of the definition. (c) Nothing about their real order: there is no global clock, and local clocks drift.