The blueprint of the paper

The paper walks the syllabus from front to back, so the question number tells you the chapter before you read it. The last question is always short notes.

• Q1 is chapter 1 in almost every sitting: a definition worth two marks, then a list worth six or eight.
• The middle of the paper is the mechanism half: clocks, mutual exclusion, election, replication and commit protocols, each wanting an algorithm and a diagram.
• The last question is short notes, and it repeats: MACH, JINI, process resilience, CORBA services, distributed deadlock and recovery come round again and again.

What to study first

These topics were asked in eight or more of the 22 sittings. Learn them before anything else; each link opens its card.

1. Lamport's clock: ordering without a clock TOP 11/22
2. Definition: many computers, one system TOP 10/22
3. NFS: the architecture, the protocol and the mount TOP 10/22
4. What CORBA is, and the components to draw TOP 10/22
5. Why no two computers agree on the time TOP 10/22
6. One primary does the work and tells the others TOP 10/22
7. Every replica does the work TOP 10/22
8. One phase, and then two TOP 10/22
9. The five challenges, and why each one fights the others TOP 9/22
10. What a DFS is, and the requirements it must meet TOP 9/22
11. The services to name, with one line each TOP 9/22
12. Choosing a new coordinator when the old one dies TOP 9/22
13. Cycles that no single server can see TOP 9/22
14. The three words, and the five requirements TOP 9/22
15. Backward and forward recovery TOP 9/22
16. RPC: the ten steps, and Sun RPC as the case study TOP 8/22
17. Proxy, dispatcher, skeleton, and the two modules under them TOP 8/22
18. Three reasons, three ways, one problem TOP 8/22

Definition: many computers, one system TOP 10/22

81 Bh · 81 Ba · 80 Bh · 78 Bh · 76 Ch · 75 Ash · 72 Ka · 71 Ch · 70 Ch · 70 Asa2+62+86+2

Read that definition as three separate claims, because an examiner marks each one. First, the machines are independent: each has its own processor, its own memory and its own clock, and each could be switched off without permission from the others. Second, the only way they can affect each other is by sending a message over a network, because there is no shared memory for them to write into. Third, the user is not supposed to notice any of this: the whole point is that the collection behaves like one machine.

Why "single coherent system" is the load bearing phrase. A paper often quotes it and asks you to justify it (2071 Chaitra). The justification is that the user sees one interface, one name for a resource and one answer, while the system quietly decides which machine actually serves the request. When you use Gmail you do not choose a server, do not know which country holds your mail, and do not care that the machine that answered you yesterday has since been replaced. That illusion is what distinguishes a distributed system from a mere network of computers.

Three terms that are easy to confuse, and are worth separating before you meet them in a question:

• Distributed program: a program written to run across several machines of a distributed system at once.
• Distributed programming: the practice of writing such programs, which means thinking about messages, failures and ordering instead of about a single call stack.
• Distributed computing: the general field, the one this subject is about.

A distributed system is not a parallel system. In a parallel computer every processor reaches the same shared memory, so processors exchange information by writing to an address that the others can read. In a distributed system each computer has its own private memory, so the only exchange possible is a message across a network. That single difference is why delay, message loss and partial failure dominate everything in this course, and why a parallel algorithm cannot simply be moved onto a distributed system.

A network is not a distributed system either. The internet by itself only carries packets. What makes the web, or DNS, or a banking network a distributed system is the layer of software running above the network that coordinates those machines into a single service. Your lecture notes make this point explicitly: the internet provides the communication channels, and the services built on top of it are the distributed systems.

Why anyone leaves a centralized system HOT 4/22

80 Bh · 79 Bh · 75 Ch · 72 Ch2+64+4

Several papers ask this directly: "differentiate centralized and distributed" (2072 Chaitra), "why is a distributed system preferred over a centralized system" (2075 Chaitra), "compare in terms of qualities, advantages and complexities" (2080 Bhadra). One table answers all three.

Where "decentralized" and "networked" fit. The lecture slides draw a three way split that is worth a line in an answer. A system is centralized if its components are all at one site. It is decentralized if components are at different sites with little or no coordination. When a decentralized system has no coordination it is merely networked; when those scattered components do coordinate closely, it is distributed. Coordination, not geography, is what makes it distributed.

And the parallel system, which examiners like to slip into the same question: its processors are tightly coupled and share one memory, so it is fast but bounded by one box. A distributed system is loosely coupled and shares nothing, so it is slower per message but unbounded in size.

The four reasons a distributed system is preferred, if you have room for only four:

• Better price to performance: many cheap microprocessors beat one large machine.
• No single point of failure: one node dying leaves the service running.
• Incremental growth: add a machine rather than replace the system.
• Resource sharing across sites, which a single machine cannot offer at any price.

The four goals a designer aims at HOT 7/22

81 Bh · 81 Ba · 80 Ba · 76 Ash · 69 Ch · 68 Ch · 68 Ba4+42+86+2

"Goals of DS" appears as a short note and as an eight mark question. The four are resource sharing, openness, transparency and scalability. Take them in that order, because transparency is large enough to have its own card next.

1. Resource sharing, the main goal. Users should be able to reach remote resources, a printer, a database, a file, a search engine, and share them in a controlled and efficient manner. The point is not only convenience:

• It lowers cost, because one expensive resource serves many users instead of one per user.
• It enables collaboration, which is why people wanted networks in the first place.
• It creates the security problem. Making sharing easy makes unauthorised access easy too, so a sharing system must also be a protecting system.

2. Openness. An open system offers its services by published, standard rules that fix the syntax and semantics of each service, so anyone can write a component that fits. In practice that means publishing interfaces, and the interfaces are written in an Interface Definition Language.

Openness buys two properties that papers ask for by name. Interoperability is the ability of two independent implementations to work together by relying on each other's published services. Portability is the ability of an application written for one distributed system to run correctly on another that offers the same interfaces, without being modified. Both follow from the same act of publishing the interface, and both are why you can add or replace a component later without disturbing the rest.

IDL comes back twice: in chapter 2 for RMI, and in chapter 4 where CORBA IDL is the whole basis of the architecture.

3. Transparency is hiding the fact that the resources and processes are spread over many machines, so the user sees one coherent system. It is big enough that the next card is entirely about it.

4. Scalability. A system is scalable if it keeps working well as it grows. Growth comes in three independent directions, and a design can scale in one while failing in another:

• Size: more users and more resources can be added.
• Geography: users and resources may sit anywhere, however far apart.
• Administration: the system stays manageable even when it spans many independent administrations, each with its own rules.

Neuman's test, worth quoting: a system is scalable if it can absorb added users and resources without a noticeable loss of performance or increase in administrative complexity. Notice that the test has two halves, performance and administration, and most designs fail on the second one first.

The eight forms of transparency HOT 6/22

79 Bh · 75 Ch · 75 Ash · 69 Ch · 68 Ch · 67 Mng4+42+63+7

The name is a little backwards at first reading. Transparent here does not mean "you can see through to the machinery"; it means the machinery is invisible. The goal is often called the single system image: a collection of computers that looks like one computer.

What each one hides, with the example that makes it stick:

• Access: hides the difference in data representation and how a resource is reached. You open a remote file with the same call you use for a local one.
• Location: hides where a resource is. A URL names a page without telling you which machine holds it.
• Migration: hides that a resource may move to another location. Your mailbox moves to a new server and your address does not change.
• Relocation: hides that a resource may move while it is in use. This is the one students drop: migration is moving between uses, relocation is moving during use, such as a phone call surviving a handover between cells.
• Replication: hides that there are several copies. You read "the" file and never learn which of the four replicas answered.
• Concurrency: hides that the resource is being shared by several competing users at the same time.
• Failure: hides the failure and recovery of a resource. A retry against another replica turns a crash into a slightly slower response.
• Persistence: hides whether a resource is in memory or on disk.

Total transparency is not actually wanted, and saying so earns marks in the "challenges" question. Hiding everything costs performance, and pretending a remote operation is local misleads the programmer about what it costs. The notes give a neat example: if you print from your phone, strict location transparency would let the system pick any printer in the world, when what you want is the printer in this room. Here breaking location transparency gives the better outcome.

The five challenges, and why each one fights the others TOP 9/22

80 Ba · 76 Ch · 76 Ash · 74 Ash · 72 Ch · 72 Ka · 71 Ch · 69 Ch · 68 Ba2+66+22+8

Your lecture notes organise this as five challenges, and that is the list to reproduce: transparency, scalability, dependability, performance and flexibility. The reason this question is worth six or eight marks is that the examiner wants the tension, not just the names: every one of these pulls against at least one other.

• 1. Transparency as a challenge. Full transparency trades against performance and scalability, and it confuses local with remote operations. It is also not always achievable, because there are physical limits on how fast a message crosses a wide area network.
• 2. Scalability as a challenge. Growth breaks systems in three ways. Size: more users and resources overload a design that must process every request. Geography: greater distance means greater delay and more chance of communication failure. Administration: as it grows, a system crosses administrative domains, each with its own policies.
• 3. Dependability as a challenge. This is the subtle one. Distribution offers higher availability through replication, but it also means more components must work for a single service to function. Dependability then demands consistency, security, concurrency control and fault tolerance together, and all four are hard.
• 4. Performance as a challenge. Every system wants maximum performance, but in a distributed system performance conflicts directly with transparency, security, dependability and scalability. Each of those is bought with extra messages, extra checks or extra copies, and each costs time.
• 5. Flexibility as a challenge. A flexible system can be configured to give exactly the services a user needs, which requires extensibility, openness and interoperability. Those contradict the other desirable properties, which is why flexible systems are rarely also simple or fast.

The Coulouris list is the alternative answer and some questions (2074 Ashwin, 2072 Kartik) are phrased to expect it. It names the challenges as heterogeneity, openness, security, scalability, failure handling, concurrency, transparency and quality of service. If a question says "challenges associated with different requirements", give this list with a line each; if it says "design challenges", give the five above. Either is accepted when each item carries a reason.

Pitfalls: the false assumptions, a favourite short note (2068 Baishakh). Every one of these is something a first time developer silently assumes and is always wrong about: the network is reliable; the network is secure; the network is homogeneous; the topology does not change; latency is zero; bandwidth is infinite; transport cost is zero; there is one administrator.

Architectural, fundamental and Enslow's model HOT 6/22

81 Bh · 80 Ba · 78 Bh · 71 Ch · 71 Shr · 70 Asa2+66+2

"Models of DS" is asked in three different senses, and the safest answer covers all three briefly and then expands the one the question names. The three senses are the physical and architectural model (what the parts are and how they are arranged), the fundamental model (what you are allowed to assume about them), and Enslow's model (how far the system is decentralized).

1. The architectural model describes the parts and their roles:

• Client server: a passive server holds a resource and waits; an active client sends a request and waits for the reply. Simple, and the basis of the web, DNS and NFS.
• Peer to peer: every node is both client and server, and there is no central authority. Scales well, and is harder to secure and manage.
• Multiple servers, proxy and cache, mobile code and mobile agents are the variations built on top of those two.

2. The fundamental models state the assumptions an algorithm is allowed to make. There are three, and papers ask "what is fundamental model" as a two mark tail (2080 Baishakh, 2071 Chaitra):

• Interaction model: how processes communicate and what you may assume about timing. A synchronous system has known bounds on message delay, processing time and clock drift; an asynchronous system has no bounds at all, which is what the internet really is. Most hard results in this subject come from that distinction.
• Failure model: what kinds of failure can occur, so an algorithm can say what it tolerates. Omission failures (a process or channel fails to do something, such as crashing or dropping a message), arbitrary or Byzantine failures (a process does the wrong thing, possibly maliciously), and timing failures (right answer, too late), which only exist in a synchronous system.
• Security model: what the threats are, which means assuming an enemy can copy, alter, replay or inject messages, and defining which principals may perform which operations.

The failure model here is the short version of chapter 9, and the arbitrary case becomes the Byzantine generals problem.

3. Enslow's model answers the question "how distributed is it, really". Enslow said a system is distributed only if all three of these are decentralized to a degree:

• Hardware: from one CPU with one control unit, through multiprocessors, up to multicomputers with multiple CPUs, multiple I/O systems and local memories.
• Control: from a single fixed control point, through fixed and then dynamic master and slave arrangements, up to multiple heterogeneous control points.
• Data: from a centralized database with a single copy, through replicated and partitioned databases, up to a partitioned database with no master file or directory.

So the one line answer to "how are hardware, data and control distributed" (2070 Ashad Q1) is: a system counts as distributed when it sits high on all three axes at once, and a system that decentralizes only the hardware is a multicomputer, not a distributed system.

Chapter 1 in one screen

• Definition, three phrases: independent computers, message passing only, single coherent system.
• Three characteristics: concurrency, no global clock, independent failures. Each one creates a later chapter.
• Four goals: resource sharing, openness, transparency, scalability.
• Eight transparencies: access, location, migration, relocation, replication, concurrency, failure, persistence.
• Five challenges: transparency, scalability, dependability, performance, flexibility. Coulouris version: heterogeneity, openness, security, scalability, failure handling, concurrency, transparency, quality of service.
• Six advantages: economic, speed, inherent distribution, reliability, incremental growth, the deriving force. Three disadvantages: hard and costly to build, coordination overhead, correctness hard to guarantee.
• Three scalability directions: size, geography, administration.
• Three fundamental models: interaction, failure, security.
• Enslow's three axes: hardware, control, data.
• Three families: grid is heterogeneous, cluster is homogeneous, cloud is on demand.

Objects that live in another process HOT 7/22

80 Bh · 79 Bh · 76 Ash · 74 Ash · 72 Ka · 71 Shr · 69 Ch3+52+42+6

Why bother. A programmer already knows how to call a method. If a remote object can be called with the same syntax as a local one, then the whole apparatus of the network, the sockets, the byte order, the retries, disappears behind a familiar line of code. That is location transparency applied to objects: the remote object and the local object look alike inside the calling program.

The three terms the paper asks for, and they are separate things:

• Remote object: an object that can receive remote invocations. Ordinary objects can receive only local invocations, from other objects in the same process that hold a reference to them.
• Remote object reference: the identifier that lets an object in another process reach a remote object. Without it there is no way to name the target. A reference can be passed on, which is how A in the figure obtains the reference to F through B.
• Remote interface: the interface a remote object publishes, stating which of its methods may be invoked from another process. Methods outside the remote interface stay private to the process.

What IDL buys, in one line: it is the contract that makes heterogeneity survivable. Sun RPC calls its IDL XDR, CORBA calls its own CORBA IDL, and Java RMI uses Java interfaces instead, which is why Java RMI works only between Java programs.

Two consequences worth a mark each. First, a chain of invocations may cross several processes, so an action started in one place can end up executing in four. Second, distributed garbage collection becomes necessary: a remote object must not be collected while some far away process still holds a reference, so RMI adds a module that counts remote references and cooperates with each machine's local collector.

RMI, the request reply protocol, and invocation semantics HOT 5/22

81 Bh · 80 Bh · 76 Ash · 71 Ch · 70 Asa2+63+54+4

Underneath, every RMI is a request reply exchange. The client sends a request message naming the object and the method, and the server sends a reply carrying the result. The message carries five fields, and a question that says "message structure" wants exactly these:

• messageType: an integer, 0 for a request and 1 for a reply.
• requestId: an integer, so a reply can be matched to its request and a duplicate can be recognised.
• objectReference: which remote object is being invoked.
• methodId: which method of it.
• arguments: an array of bytes, the marshalled parameters.

Now the interesting part. A local call runs exactly once: the machine either runs the method or crashes with it. A remote call has a network in the middle, so the request can be lost, the reply can be lost, or the server can crash halfway. What the caller is promised depends on which three fault tolerance measures the implementation uses:

• Retry request message: retransmit the request until either a reply arrives or the server is assumed to have failed.
• Duplicate filtering: the server recognises retransmitted requests by their request id and does not execute them twice.
• Retransmission of results: the server keeps a history of replies, so a lost reply can be resent without re-executing the method.

• Maybe semantics: no fault tolerance measures at all. The method may be executed once or not at all, and the caller cannot tell which. It suffers omission failure when a message is lost and crash failure when the server dies. Acceptable only when an occasional failed call does not matter.
• At least once semantics: retry, but no duplicate filtering, so the procedure is re-executed on every retransmission. The caller either gets a result, meaning the method ran at least once, or an exception. It suffers crash failures and arbitrary failures, because a method executed twice may return a wrong value. It is safe only for idempotent operations, those that give the same result however often they run.
• At most once semantics: retry, duplicate filtering and retransmission of results together. The caller either receives the result of exactly one execution, or an exception. This is the strongest an RMI system offers, and it is what Java RMI and CORBA provide.

RMI transparency is the hiding of marshalling, message passing, and the work of locating and contacting the remote object, so that a remote invocation looks like a local one. It is deliberately incomplete: the semantics above differ from a local call, and the remote interface must declare the extra exceptions, so the programmer is warned that this call can fail in ways a local call cannot.

RPC: the ten steps, and Sun RPC as the case study TOP 8/22

81 Bh · 81 Ba · 80 Bh · 76 Ash · 71 Shr · 70 Ch · 69 Ch · 67 Mng2+63+54

How RPC differs from RMI, in the two ways that matter: RPC has no object references, so you call a procedure by name and number rather than a method on a particular object, and it cannot create new instances of objects. Otherwise it uses the same request reply protocol and the same three invocation semantics.

The working of RPC, step by step, which is worth five or six marks on its own:

1. The client procedure calls the client stub in the normal way, as an ordinary local call.
2. The client stub builds the message, packing the procedure identifier and the arguments, and calls the local operating system.
3. The client's OS sends the message to the remote OS.
4. The remote OS gives the message to the server stub.
5. The server stub unpacks the parameters and calls the server procedure.
6. The server does the work and returns the result to its stub.
7. The server stub packs the result in a message and calls the local OS.
8. The server's OS sends the message to the client's OS.
9. The client's OS gives the message to the client stub.
10. The client stub unpacks the result and returns it to the client, which never knew it had left the machine.

What a stub actually does is marshalling: turning the arguments, which are machine specific bit patterns, into an agreed external representation that any machine can read, and back again at the other end. That is the step that makes heterogeneity survivable, and it is the step that costs the time.

Case study: Sun RPC

Sun RPC was designed for client server communication in the Sun Network File System, which is why it turns up again in section 2.10. Its features:

• Transport: runs over UDP or TCP. Over UDP the request and reply lengths are restricted, in theory to 64 kilobytes.
• Semantics: at least once, which is why NFS operations are designed to be idempotent.
• Interface language: XDR, with an interface compiler rpcgen used with C.

The XDR rules examiners ask about:

• It supplies a program number and version number instead of an interface name. The version number changes when a procedure changes, and both are sent in the request so client and server can confirm they agree.
• A procedure definition is a procedure signature plus a procedure number, and the number is what the request carries.
• Only a single input parameter is allowed. Several inputs must be wrapped in a structure.
• The outputs are returned as a single result.
• rpcgen generates the client stub, the server main procedure, dispatcher and server stub, and the marshalling and unmarshalling procedures, all from the interface definition.

Binding: how the client finds the server's port. A local binding service called the port mapper runs at a well known port on each computer. Each port mapper records the program number, version number and port number of every service on its machine. When a server starts, it registers its program number, version number and port with the local port mapper. When a client starts, it makes a remote request to the port mapper on the server's host, giving the program and version numbers, and gets back the port.

Authentication. Sun RPC messages carry an extra field for authentication information, which matters for critical operations such as reaching the network file system. The header names the style in use, and the supported styles are none, UNIX style, shared key and Kerberos style.

The comparison the paper asks for every other year HOT 6/22

78 Bh · 75 Ch · 74 Ash · 72 Ch · 70 Ch · 70 Asa3+54+42+6

This is asked as "differentiate", "compare" and "how is RMI superior to RPC". One table answers all three, and the last row is the one that earns the "superior" mark.

Why RMI is called superior: it keeps the object model across the network. Because a remote object reference can be passed as a parameter and returned as a result, a program can build and traverse a structure of remote objects, which RPC cannot express at all. It also inherits the object oriented advantages of encapsulation, inheritance and polymorphism, and it gives at most once semantics without the programmer arranging it.

The three differences to lead with, if the question is only worth two marks:

• RPC calls a procedure; RMI invokes a method on an object.
• RPC has no object references, so objects cannot be passed or returned.
• RMI gives at most once semantics by default, where RPC is usually configured for maybe or at least once.

Proxy, dispatcher, skeleton, and the two modules under them TOP 8/22

81 Ba · 80 Ba · 79 Bh · 76 Ch · 75 Ch · 72 Ch · 72 Ka · 71 Shr3+52+62+8

"Functionalities provided by RMI software" is a standing question. RMI software is the layer between the application objects and the request reply protocol, and it is made of three generated classes and two modules.

The three generated classes, each with one job:

• Proxy (client side). One proxy object per remote object the client uses. It implements the same remote interface, so the client's code calls it exactly as if it were the remote object. Its method bodies marshal the arguments, send the request, wait, unmarshal the result and return it. The client never knows it exists.
• Dispatcher (server side). One per class of remote object. It receives the request message, reads the methodId and calls the matching method of the skeleton.
• Skeleton (server side). One per class of remote object. It unmarshals the arguments, invokes the method on the real object, which is called the servant, then marshals the result and sends the reply.

The two modules underneath, which are not generated and are shared by everything:

• Communication module: carries out the request reply protocol. It pairs a reply with its request by request id, applies the chosen invocation semantics, and hands an incoming request to the right dispatcher.
• Remote reference module: translates between local object references and remote object references, using a remote object table that records every remote object held by this process and every proxy it holds for remote objects elsewhere. It is what creates a proxy the first time a remote reference arrives from outside.

The binder, and static against dynamic RMI

A client still has to obtain that first remote reference, and it does so from a binder: a service that maps textual names to remote object references. In Java this is the RMI registry: the server calls bind or rebind to register a name, the client calls lookup to get back a proxy.

• Static RMI: the remote interface is known when the client is compiled, so the proxy and skeleton classes are generated ahead of time and the call is checked by the compiler. It is fast and safe, and it cannot call anything the programmer did not know about.
• Dynamic RMI: the interface is discovered at run time. The client asks an interface repository what methods the object offers, builds the invocation as data, and sends it. It is slower and unchecked, and it can call a service that did not exist when the client was written. CORBA calls these two the static and dynamic invocation interfaces.

Two extra services the RMI software may provide, and papers do ask for them: an activation service, which restarts a remote object on demand so servers need not run forever, and distributed garbage collection, which keeps a remote object alive while any proxy anywhere still refers to it.

The request reply protocol under all of this is the one in 2.2, and the same layering reappears as the ORB in chapter 4.

What a DFS is, and the requirements it must meet TOP 9/22

79 Bh · 76 Ch · 76 Ash · 73 Shr · 72 Ch · 72 Ka · 71 Ch · 70 Ch · 70 Asa2+682+3+2

Start from the plain file system. A file system gives an abstract view of secondary storage and is responsible for global naming, file access and overall file organisation. Those three jobs are handled by the name service, the file service and the directory service. Two terms the paper separates: the file service is the specification of what the file system offers its clients, and a file server is a process on some machine that implements it.

Why a distributed one matters, which answers "how does DFS encourage sharing a storage device":

• It supports sharing of information as files across the whole intranet, so one copy of a document serves everybody instead of a copy per machine.
• It lets programs store and access remote files exactly as local ones, so no application has to be rewritten to use shared storage.
• It separates the storage from the workstation, so an expensive, backed up, managed disk array serves many cheap diskless clients, which is the economic argument.

The requirements of a DFS, the standard seven point list:

• Transparency of access, location, mobility (migration), performance and scaling. Access and location transparency together give network transparency.
• Concurrent file updates must be controlled, so that simultaneous writers do not corrupt a file.
• File replication must be supported, to raise scalability and fault tolerance.
• Hardware and operating system heterogeneity: the service interfaces must be definable so they can be implemented on different systems.
• Fault tolerance: the service must continue to operate through client or server failures.
• Consistency: files must keep a consistent state, which in UNIX means one copy update semantics.
• Security: access control mechanisms must protect the files.

Two more that are always accepted: efficiency, since the DFS must perform comparably with a local file system, and naming, since users need one global name structure rather than a different path on every machine.

Does the server remember you between calls? HOT 6/22

81 Bh · 80 Bh · 80 Ba · 76 Ash · 75 Ch · 74 Ash2+63+54

This is asked in six of the twenty two sittings, usually as the two mark opener before a file system question. Get the definitions exact, then give the trade off.

The three points that decide it, if the question is worth only two marks:

• Stateful is faster, because the file name is parsed once and the server can read ahead.
• Stateless recovers instantly, because a restarted server has nothing to rebuild.
• Stateless needs idempotent operations, since every request may be retried.

Advantages and consequences of statelessness, which is a short note in its own right: it gives fast crash recovery, since a restarted server needs no recovery protocol and a client cannot tell a slow server from a crashed one; it makes the server simple and its memory bounded; and the cost is larger request messages, worse performance, and the loss of server side locking, which is why NFS needs a separate lock manager. Sun NFS chose stateless for exactly this reason: fast crash recovery was the design goal.

Three modules, and what each one owns HOT 7/22

80 Bh · 78 Bh · 73 Shr · 72 Ka · 70 Ch · 70 Asa · 69 Ch4+42+63+5

This is the diagram behind "draw and explain distributed file service architecture", worth four to six marks in six different sittings. The design exists so that the three jobs of a file system can be implemented separately, and so that the server modules can be stateless.

• Flat file service. Implements operations on the contents of files. It knows nothing about names: files are identified by a Unique File Identifier, a long bit string unique across the whole distributed system. Operations: Read, Write, Create, Delete, GetAttributes, SetAttributes. Read and Write take the position explicitly, which is what makes the service stateless.
• Directory service. Provides the mapping between text names for files and their UFIDs, and is therefore the thing that turns a path into a file. Operations: Lookup, AddName, UnName, GetNames. A directory is stored as an ordinary file in the flat file service, so a hierarchy is built by directories naming directories.
• Client module. Runs on each client computer and integrates and extends the two server services behind a single application programming interface, so an ordinary program sees a normal file system. It holds the state that the stateless server does not: the current directory, the open files and their positions, and the server addresses. It also caches recently used blocks, which is where the performance comes from.

Why split it this way? Because the two responsibilities scale differently and fail differently. Keeping names out of the flat file service lets the same file be named in several directories, lets the file service stay stateless, and lets a UFID be checked for access rights independently of the path used to reach it.

NFS: the architecture, the protocol and the mount TOP 10/22

81 Bh · 81 Ba · 80 Ba · 78 Bh · 76 Ch · 75 Ch · 75 Ash · 72 Ch · 71 Shr · 69 Ch2+63+52+7

NFS is the single most asked topic in chapter 2. "Explain the operation and architecture of any one modern distributed file system" almost always means this.

What it is: the first commercially successful network file system, developed by Sun Microsystems for their diskless workstations, designed for robustness, adequate performance and transparent access, with the protocol specification published so that many implementations exist.

The six properties the lecture notes list, which is the list to reproduce:

• It is both an implementation and a specification of how to access remote files.
• It focuses on sharing a file system in a transparent way.
• It uses the client server model, and a node can act as both client and server.
• It uses mount to make a server file system visible from a client.
• It is stateless: all client requests must be self contained.
• It is machine and operating system independent.

The architecture in three parts, which is how the answer should be organised:

• 1. The protocol. Built on the Sun RPC mechanism and the XDR standard for representing data. It is stateless, which is what makes crash recovery easy: every procedure call carries all the information needed to complete it, so a server that restarts simply starts answering again.
• 2. The server side. The server issues a file handle for each file, made of three parts: the file system identifier, which names the disk partition and is stored in its super block; the i-node number, which names the file within that partition; and the generation number, stored in the i-node and incremented when the i-node is reused, so a stale handle to a deleted file is rejected rather than silently pointing at a new one.
• 3. The client side. Presents a transparent interface to NFS through the virtual file system, which keeps a v-node per open file recording whether it is local or remote. The mapping from a remote file name to a remote file address is set up at boot time through a remote mount.

The mount operation, since a question may ask how the remote file system appears: the client sends a mount request naming a remote directory, the server's mount service checks its export list and returns the file handle for that directory, and the client grafts it onto a point in its own local name space. From then on any path below that point is resolved through the NFS client. Hard mounting makes a process block until the server answers; soft mounting returns an error after a few retries.

The operations NFS offers fall into five groups: search for a file within a directory; read a set of directory entries; manipulate links and directories; read and write file attributes; and read and write file data.

Design issues on NFS, which is its own question (2078 Bhadra): the statelessness forces every request to carry the offset and makes UNIX open and close semantics hard to reproduce; caching at the client gives the performance but creates a consistency problem, solved only approximately by validating cached blocks against the file's modification time on a timer; locking is not in the protocol and needs a separate lock manager, which is stateful; and security rests on the UNIX user id in the RPC credentials, which the server has to trust.

DNS: a distributed hierarchical database HOT 7/22

80 Bh · 79 Bh · 78 Bh · 75 Ash · 74 Ash · 73 Shr · 71 Ch4+42+3+21+4

DNS is asked in seven sittings, sometimes as "verify that DNS is a distributed hierarchical database system", which is a request to justify all four words. Do them in order.

• Database: it stores records, the name to address mappings and others, and answers queries against them.
• Hierarchical: the name space is a tree. An unnamed root at the top, then top level domains, then second level domains, and so on, with a full stop as the separator. A name is read right to left, from the most general to the most specific.
• Distributed: no machine holds the whole database. It is cut into zones, and each zone is served by its own authoritative name servers, which are run by whoever owns that part of the tree. Delegation is by NS records pointing at the servers of the zone below.
• And it behaves as one: any client asking any resolver gets the same answer, which is the single coherent system property of chapter 1 applied to naming.

The working mechanism, with the standard example. Suppose a client wants the address of www.example.com:

1. The client issues a DNS query for the address of the name to its local DNS server.
2. The local server, holding no answer, queries a root name server.
3. The root returns the address of the top level domain server for com.
4. The local server queries the TLD server.
5. The TLD server replies with the name and address of the authoritative server for the domain.
6. The local server queries that authoritative server.
7. It replies with the address of www.example.com.
8. The local server returns the address to the client, which then requests the web content from it directly.

Recursive and iterative queries, which is a two mark definition pair:

• A recursive query is sent to a DNS server and requires a complete answer: the server must resolve it fully, asking others on the client's behalf, or return a failure.
• An iterative query may be answered with a referral to another DNS server, leaving the asker to continue.
• Root hints are the file of root server addresses that lets a resolver start at all.
• Caching is what makes the whole thing fast: every resolver keeps answers for the record's time to live, so the root servers are asked far less than the step list suggests.

• A: address, maps a host name to an IP address.
• CNAME: alias, maps one name to another name, which is then resolved.
• NS: authoritative name server for a domain, which is how delegation works.
• MX: mail exchanger for a domain.
• PTR: domain name pointer, used for reverse lookup from an address to a name.
• SOA: start of authority, the parameters of a zone, including its serial number.

Valid DNS names use only A to Z, a to z, 0 to 9 and the hyphen, and a full stop separates the labels.

Chapter 2 in one screen

• Distributed object: object in another address space. Needs a remote object reference, publishes a remote interface, described in an IDL.
• Request reply message: messageType, requestId, objectReference, methodId, arguments.
• Three semantics: maybe (nothing), at least once (retry only), at most once (retry plus duplicate filtering plus retransmitted reply).
• RPC in ten steps: client, client stub, client OS, server OS, server stub, server, and back.
• RMI software: proxy, dispatcher, skeleton, plus the communication module and the remote reference module. Binder is the RMI registry.
• Sun RPC: XDR, rpcgen, port mapper, at least once, program and version and procedure numbers.
• DFS requirements: transparency, concurrent updates, replication, heterogeneity, fault tolerance, consistency, security.
• File service architecture: flat file service (UFID), directory service (names), client module (single API and cache).
• NFS: stateless, mount, virtual file system, file handle of filesystem id plus i-node number plus generation number, Sun RPC and XDR.
• Stateless wins on crash recovery, loses on performance.
• HDFS: one NameNode with the namespace in RAM, DataNodes with 128 MB blocks, heartbeat every 3 seconds, every tenth is a block report, rack aware pipelined write.
• DNS: hierarchy, zones, delegation by NS records, recursive against iterative, records A, CNAME, NS, MX, PTR, SOA.

Why a distributed system needs threads HOT 5/22

80 Ba · 79 Bh · 72 Ka · 70 Ch · 70 Asa44+2+22+2

The execution environment is the other half of the definition and it is what makes the comparison clean. A process consists of an execution environment, the local kernel managed resources, plus one or more threads that share it. The execution environment holds the address space, the communication interfaces such as sockets and ports, and the synchronisation resources such as semaphores. The thread holds only its own program counter, registers, stack and scheduling state.

Why threads matter in a distributed system, which is the four mark version of this question:

• Multiple users need concurrency. A server must serve many clients at once, and without threads a single process would handle them strictly one after another.
• A thread can block on a system call without blocking the process. This is the key one. A remote call takes milliseconds, and in that time the other threads keep working, so a server can hold many logical connections open at the same time.
• Threads of one process can run in parallel on different processors, so a multiprocessor server is actually used.
• Threads share a common buffer, which makes patterns such as producer and consumer easy to implement, and makes caching in a server natural.

Three server threading architectures, since papers ask how the threads are organised in practice:

• Thread per request: the I/O thread creates a new worker for every request and discards it afterwards. It maximises throughput and suits a connectionless service such as NTP, and the creation cost is paid on every call.
• Thread per connection: one thread per client connection, which matches the TCP model and is the most commonly used. A busy connection can starve a quiet one.
• Thread per object: one thread per remote object, with requests queued for it. Each object has exactly one thread, so no synchronisation is needed inside the object.
• Worker pool: a fixed set of workers takes requests from a queue, which bounds the resources used and allows priorities.

One big kernel, or a small one with servers around it HOT 6/22

79 Bh · 76 Ash · 75 Ash · 73 Shr · 72 Ka · 71 Shr342+3

This is the most asked topic in the chapter, and the answer is always the same shape: define both, give the table, then say which one suits a distributed system and why.

Which one for a distributed operating system, and why. The microkernel, for three reasons your notes give directly:

• The services of a distributed system are complex, and the microkernel's separation of them into servers makes that complexity manageable.
• It gives faster communication among processes with low overhead, which is what a distributed system does constantly.
• It is extensible: a distributed system needs services that were not anticipated, and a new server can be added without touching the kernel, and can even be placed on a different machine.

The honest counterpoint, worth a line if the question says "in your view": pure microkernels lost on performance, so real systems are hybrid. They keep a microkernel structure but move the performance critical servers back into kernel space, which is what Windows NT and macOS actually do.

Three answers to "make these machines work together" HOT 6/22

78 Bh · 75 Ash · 74 Ash · 72 Ch · 70 Ch · 69 Ch2+44+44

Why NOS is preferred over DOS in practice, which is asked directly (2069 Chaitra) and surprises students who expect the more advanced answer to win:

• Existing applications. Users invest in applications that solve their current problems. They will not move to a new operating system that cannot run those applications, even if it is more efficient.
• Autonomy. Users want a degree of control over their own machine even inside a close knit organisation, because they do not want their work slowed down by somebody else's process being scheduled onto it.

So the real answer is the third row of the table: a middleware layer on top of an ordinary network operating system. It gives the distribution transparency people want from a distributed OS while leaving each machine its own operating system and its own owner, which is why DOS is described as "middleware" in the comparison.

Characteristics of a distributed operating system, for the question that asks for them directly: a single system image; transparent resource access and process migration; global resource management and load sharing; data migration, moving a whole file or only the parts needed; computation migration, moving the computation to the data rather than the data to the computation; a global file system and a global name space; and tolerance of node failure.

Chapter 3 in one screen

• The stack: hardware, OS, middleware, applications. Hardware plus OS is the platform.
• Five core components: process manager, thread manager, communication manager, memory manager, supervisor.
• Kernel as resource manager: encapsulation, protection, concurrent processing.
• Protection: user mode plus a private address space plus system call traps. Or a type safe language.
• Process against thread: separate memory against shared memory; self contained against dependent; heavy against minimal; IPC against shared variables.
• Threads matter because a blocking call does not block the process.
• Threading architectures: thread per request, thread per connection, thread per object, worker pool.
• Invocation cost: marshalling, data copying, packet initialisation, scheduling and context switching. Fixed cost dominates. LRPC cuts it to one context switch.
• Monolithic: fast, all in one address space, a fault kills everything, recompile to extend. Microkernel: slower, servers in user space, faults contained, extensible. Microkernel wins for a distributed OS.
• NOS: own image per node, loosely coupled, offers local services to remote clients. DOS: single image, tightly coupled, hides and manages hardware. NOS plus middleware is what is actually used.

What actually differs, and why it differs HOT 4/22

75 Ch · 71 Ch · 70 Ch · 70 Asa42+43+5

Distributed applications are heterogeneous in four ways, and a question worth three or four marks wants all four with examples:

• Different hardware: mainframes, workstations, personal computers, servers.
• Different software: UNIX, MS Windows, IBM OS/2, real time operating systems.
• Unconventional devices: teller machines, telephone switches, robots, manufacturing systems.
• Diverse networks and protocols: Ethernet, FDDI, ATM, TCP/IP, Novell NetWare.

Why any of this is allowed to happen, which is the part students skip:

• Different hardware and software solutions are optimal for different parts of the system: a teller machine and a database server should not be the same computer.
• The different users who have to interact choose different vendors, and they cannot be forced to agree.
• Legacy systems already exist and cannot be thrown away, so the new system must speak to them.

Homogeneous against heterogeneous, the comparison some papers ask for directly: a homogeneous distributed system has the same hardware, operating system and network throughout, which makes it simple, fast and easy to manage, and is what a cluster is. A heterogeneous one differs on all of those, which is what a grid or any real corporate system is: harder to build, and it is what the world actually looks like. The integration of heterogeneous components is what forces the construction of a distributed system in the first place, and the communication between them is the problem middleware exists to solve.

The layer that makes heterogeneity survivable HOT 5/22

80 Ba · 78 Bh · 72 Ch · 72 Ka · 69 Ch2+62+83+5

What middleware does, the four point list from your notes:

• Hides the intricacies of distributed applications, so a programmer writes a call rather than a protocol.
• Hides the heterogeneity of hardware, operating systems and protocols.
• Provides uniform and high level interfaces, which is what makes applications interoperable, reusable and portable.
• Provides a set of common services, so that every application does not reimplement naming, security and transactions, which minimises duplicated effort and lets applications collaborate.

The role of middleware in a distributed system, which is a separate question in four sittings and wants the verbs, not the definition:

• It provides services the operating system does not, so the components of the system can communicate and manage data.
• Its major role is to handle communication between components, without assuming anything about the content beyond that the receiver can understand it.
• It performs load management: starting and stopping services and directing load to them.
• It provides authentication and authorisation, audit and logging.
• It provides interoperability between applications running on different operating systems.

Middleware compared with an operating system, a neat line that earns a mark: an operating system provides an API for using the underlying hardware; middleware provides an API for using the underlying operating system. Both support other programs, control their interaction and prevent interference, but middleware does it across a network.

What counts as middleware. Quite a lot qualifies to some degree, which is worth saying because examiners accept the range: file transfer packages and email, web browsers, and the proper article, CORBA. The usual classification is RPC and RMI middleware, message oriented middleware, object request brokers and transaction processing monitors.

What CORBA is, and the components to draw TOP 10/22

80 Bh · 79 Bh · 78 Bh · 76 Ch · 76 Ash · 75 Ch · 74 Ash · 73 Shr · 72 Ch · 69 Ch342+4

Who made it. The Object Management Group (OMG) is a non profit industry consortium formed in 1989 to develop, adopt and promote standards for building distributed heterogeneous applications. Its main achievement is the specification of the Common Object Request Broker Architecture.

What the specification actually is. It details the interfaces and characteristics of the Object Request Broker, that is, it specifies the middleware functions that let application objects communicate with one another no matter where they are located, who designed them, or in which language they are implemented. OMG provides only a specification; several products implement it to varying degrees.

The key concepts, which is a good six point answer on its own:

• CORBA specifies the middleware services used by the application objects.
• An object can be a client, a server, or both.
• Object interaction is through requests, and a request carries three things: an operation to be performed, a target object, and zero or more parameters.
• CORBA supports static and dynamic binding; dynamic binding identifies objects and parameters at run time.
• The interface is the contract between client and server. An IDL is defined for CORBA, and proxies and skeletons are generated by compiling it.
• CORBA objects do not know the implementation details underneath them: an object adapter maps the generic model onto a specific implementation.

• Client application and server object: the application code at each end.
• Proxy (static): the client side stub generated from the IDL, used when the interface is known at compile time.
• Dynamic invocation interface: the path used when it is not, building the request at run time.
• Interface repository: holds a standard representation of the available object interfaces, corresponding to the servers' IDL specifications. Clients read it to learn what operations an object offers and what parameters they take, which is what makes dynamic invocation possible.
• Server skeleton: the server side piece generated from the IDL, which invokes the right method on the server object.
• Object adapter: the interface between the server object implementation and the ORB.
• Implementation repository: holds the implementation details for the objects that implement each interface. Mainly it maps a server object's name to the file that implements the service, plus information about the object methods and what is needed to select one. Its contents may be specific to the operating system of that server and to that CORBA product. The object adapter uses it to resolve an incoming call and activate the right method through a skeleton.
• Object Request Broker (ORB): the bus underneath everything, carrying requests from client to object and results back.

Keep the two repositories straight, because a question often names only one: the interface repository answers "what can this object do", and the implementation repository answers "which code do I run and where is it".

The services to name, with one line each TOP 9/22

80 Bh · 80 Ba · 75 Ch · 72 Ch · 72 Ka · 71 Ch · 71 Shr · 70 Asa · 69 Ch2+444+2+2

CORBA specifies a long list of services and current products implement only some of them. Six are enough for a four mark note, and the first two are the ones an examiner looks for.

• Naming service. The basic way an object reference is generated is at the creation of the object, when the reference is returned. References can be stored together with associated information such as names and properties. The naming service lets clients find objects by name.
• Trading service. Lets clients find objects by their properties rather than by name, which is the directory service idea of chapter 2 applied to objects.
• Transaction management service. Provides two phase commit coordination among recoverable components that use transactions.
• Concurrency control service. Provides a lock manager that can obtain and free locks for transactions or for threads.
• Security service. Protects components from unauthorised users. It provides authentication, access control lists and confidentiality.
• Time service. Provides interfaces for synchronising time, and operations for defining and managing time triggered events.

Three more that are worth adding when the question is worth six or eight marks: the event service, which decouples suppliers and consumers of events as in chapter 2; the persistence service, which stores an object's state so it survives its process; and the life cycle service, which creates, copies, moves and deletes objects.

Notice how much of chapter 8 arrives here as a service: the transaction service is two phase commit and the concurrency service is locking, offered so that an application does not have to implement them.

Chapter 4 in one screen

• Heterogeneity in four kinds: hardware, software, unconventional devices, diverse networks. Because different parts need different solutions, users choose different vendors, and legacy systems exist.
• Middleware: a layer between applications and operating systems. Hides intricacies, hides heterogeneity, gives uniform high level interfaces, provides common services.
• OS gives an API for the hardware; middleware gives an API for the OS.
• IDL: declarative, language independent, compiled into proxies and skeletons, or client and server stubs for non object languages.
• OMG formed 1989, specified CORBA. Specification only, many products.
• A request carries three things: an operation, a target object, zero or more parameters.
• CORBA components: client application, dynamic invocation, static proxy, interface repository, ORB, object adapter, server skeleton, implementation repository, server object.
• Interface repository: what an object can do. Implementation repository: which code to run.
• Static invocation: compile time knowledge, low overhead. Dynamic invocation: run time discovery, huge overhead, identical to the server.
• Object adapter, four services: object registration, object reference generation, object upcalls, server process and object activation.
• CORBA services: naming, trading, transaction management, concurrency control, security, time.

Why no two computers agree on the time TOP 10/22

81 Bh · 81 Ba · 80 Ba · 74 Ash · 72 Ch · 72 Ka · 71 Shr · 70 Ch · 70 Asa · 69 Ch2+62+4+22+2+4

What a physical clock actually is. Every computer contains an electronic device that counts the oscillations of a crystal at a definite frequency and stores the count divided by the frequency in a register. That register is the clock, and the value it holds is the physical time.

Why they disagree. Different computers have different crystals, and no two crystals oscillate at exactly the same rate. Even a small difference accumulates: the clocks gradually drift out of synchronisation and report different values. That is the whole problem, and it cannot be removed, only corrected repeatedly.

Two measures to name: skew is the instantaneous difference between two clock readings, and drift rate is the rate at which they diverge. A clock with drift rate $\rho$ obeys

so two clocks can differ by up to $2\rho \Delta t$ after time $\Delta t$, and a system that must keep them within $\delta$ has to resynchronise every $\delta /(2\rho )$ seconds. That inequality is the reason clock synchronisation is periodic rather than a one time fix.

Why physical synchronisation is hard, which is asked directly in four sittings:

• No single correct source is reachable instantly. Reading a remote clock takes a message, and the message takes an unknown time.
• Message delay is variable. The best you can do is bound it, and on a wide area network the bound is poor.
• Clocks must never run backwards. A clock that is ahead cannot simply be set back, because a file could then be modified "before" it was created; it must be slowed until it catches down.
• Crystals drift with temperature and age, so the correction is never permanent.

Internal against external synchronisation, a distinction that decides which algorithm you use. For many applications it is enough that all the machines agree with each other, even if they are all wrong: if every machine believes it is 10:00 when it is really 10:02, a build still works, because only the internal consistency matters. That is internal synchronisation, and Berkeley's algorithm does it. When the clocks must also stay within a bound of real time, that is external synchronisation, and Cristian's method and NTP do it against UTC.

The international atomic clock, since 2081 Bhadra asks how it was established: a second is defined as 9,192,631,770 transitions of the caesium 133 atom. TAI, International Atomic Time, is the average of over 200 caesium clocks in national laboratories around the world. Because the earth's rotation is slowing, UTC is TAI with leap seconds inserted to keep it within 0.9 seconds of solar time, and UTC is what a time server broadcasts.

Ask a time server, and halve the round trip HOT 4/22

76 Ch · 75 Ash · 72 Ch · 72 Ka32+2+62+4

The setting. Cristian's algorithm relies on a time server S that holds UTC from a radio clock or another accurate source. Every other computer stays synchronised by making a procedure call to it. It achieves synchronisation only when the round trip times are short compared with the accuracy required, which is why it suits a local network.

The algorithm, three steps:

1. Process P requests the time from server S, noting $T_0$ on its own clock.
2. S prepares a response and appends the time $T$ from its own clock.
3. P receives the reply at $T_1$ and sets its clock to

The assumption being made, and you should state it: that the round trip is split equally between the request and the response. That is not always true, but it is reasonable on a LAN.

How accurate is it? Let $\text{min}$ be the minimum time to send a message one way. The earliest moment S could have written $T$ was $\text{min}$ after P sent its request, and the latest was $\text{min}$ before the reply arrived. So when P reads the reply, S's clock lies in the range

whose width is $\text{RTT}-2\text{min}$, giving an accuracy of

Improving it: make several requests and keep the reply with the shortest round trip, because that is the one least distorted by queueing.

The drawback, and the fix. If the time server fails, synchronisation becomes impossible, and a single server is also a target for attack. The answer is to provide the time from a group of synchronised time servers, which is exactly what NTP does.

Lamport's clock: ordering without a clock TOP 11/22

81 Bh · 81 Ba · 78 Bh · 76 Ch · 76 Ash · 75 Ch · 75 Ash · 73 Shr · 72 Ka · 70 Asa · 69 Ch2+62+82+2+4

The starting observation. If two processes never exchange messages, they have no way of affecting each other, so there is no need to order their events at all; such events are concurrent. Events on one machine can be ordered by the local clock. And when two processes do communicate, the send must have happened before the receive. Those three facts are all the ordering that physics gives us, and Lamport's contribution was to say that they are enough.

Partial and total order, two terms the paper uses: the system has a partial order because happened before relates some pairs of events and leaves concurrent pairs unrelated. If a causal relationship can be established among all events, the system has a total order, which is obtained in practice by breaking ties with the process identifier.

The implementation rules

Each process $P_i$ keeps a counter $C_i$, and obeys three rules:

1. Before each event in the process, increment the counter: $C_i:=C_i+1$.
2. When sending a message, include the counter value with the message: $m=(\text{data},t)$ with $t=C_i$.
3. On receiving a message carrying $t$, set the counter to be greater than the maximum of its own value and the received value before the message is considered received: $C_j:=max(C_j,t)+1$.

The limitation, which is asked as often as the algorithm

The clock guarantees one direction only:

but the converse is false. From $C(a)<C(b)$ you cannot conclude $a\to b$: the two events may be entirely concurrent and have simply picked up those numbers independently. So Lamport's clock cannot detect causality, only respect it, and that is why it is said not to be a true clock. Two more practical limits: the counters of different processes carry no relation to each other, and total ordering has to be faked with process ids.

The fix is the vector clock, and every paper that asks for "the issue in Lamport's timestamp, and your alternate algorithm" wants exactly that sequence.

An array instead of a counter, and now causality is visible HOT 5/22

80 Bh · 80 Ba · 76 Ch · 75 Ch · 74 Ash2+4+22+62+8

What the entries mean, which makes the rules obvious rather than arbitrary: $V_i[i]$ is the number of events $P_i$ has itself experienced, and $V_i[j]$ is $P_i$'s best knowledge of how many events $P_j$ has experienced. The vector is therefore a summary of everything this process knows about the whole system.

The implementation rules, four steps:

1. Initially all clocks are zero: $V_i[j]=0$ for every $i,j$.
2. On an internal event, a process increments its own element: $V_i[i]:=V_i[i]+1$.
3. On sending a message, it increments its own element and sends the entire vector with the message.
4. On receiving a message carrying vector $t$, it increments its own element and then updates every element by taking the maximum: $V_j[k]:=max(V_j[k],t[k])$ for all $k$.

How to compare two timestamps, which is the part that earns the marks. For vectors $u$ and $v$:

• $u=v$ if and only if $u[i]=v[i]$ for every $i$.
• $u\le v$ if and only if $u[i]\le v[i]$ for every $i$.
• $u<v$ if and only if $u\le v$ and $u\ne v$.
• $u\parallel v$, concurrent, if and only if neither $u<v$ nor $v<u$.

And here is the property Lamport's clock did not have:

The implication now runs both ways, so by comparing two timestamps alone you can say whether the events are causally related or concurrent. That is the whole advantage, and it is the answer to "how is the vector clock beneficial over Lamport's clock".

The disadvantage, and you should state it: the timestamp takes storage and message payload proportional to the number of processes, so a system with a thousand processes carries a thousand integers on every message. Lamport's clock costs one integer regardless of size. That trade, causality against payload, is the whole comparison.

What a global state is, and when a cut is consistent HOT 4/22

81 Bh · 80 Ba · 79 Bh · 73 Shr4+64

Why anyone wants it. Several practical jobs need a photograph of the whole system: detecting distributed deadlock, detecting termination of a distributed computation, taking a checkpoint to roll back to after a failure, and distributed debugging, that is checking whether some property held.

Why it is hard. There is no global clock, so the local states are recorded at different moments on different machines. Simply asking every process "what is your state" gives a set of answers taken at different times, which may add up to a situation that never existed.

The definitions, exactly as the paper wants them:

The types of cut you may be asked to identify:

• Consistent cut: no message is received inside the cut whose send lies outside it. Drawn as a line that no arrow crosses right to left.
• Inconsistent cut: at least one message is received inside the cut but sent after it. Such a state never existed and cannot be used as a checkpoint.
• Strongly consistent cut: a consistent cut that in addition contains no message in transit at all, that is, no arrow crosses it in either direction. Every send inside the cut has its receive inside it too.

The frontier of a cut is the set of the last events at each process, and the state of the cut is the set of local states at that frontier.

Chapter 5 in one screen

• Three physical algorithms: Cristian (external, one server, $T+\text{RTT}/2$), Berkeley (internal, master averages and sends adjustments), NTP (hierarchy of strata, three modes, offset from four timestamps).
• Cristian accuracy: $\pm (\text{RTT}/2-\text{min})$. Improve by keeping the shortest round trip.
• NTP: $d=(T_4-T_1)-(T_3-T_2)$, $o=\frac{1}{2}[(T_2-T_1)+(T_3-T_4)]$. Modes: multicast, procedure call, symmetric.
• Happened before: same process order; send before receive; transitive.
• Lamport rules: increment before an event; send the counter; on receive take $max$ then add one.
• Lamport limitation: $a\to b\Rightarrow C(a)<C(b)$ but not the converse.
• Vector clock: array of N; increment own element; send the whole vector; on receive take the element wise maximum. $a\to b⟺V(a)<V(b)$. Costs N integers a message.
• Causal ordering: deliver only when $t_m[i]=V_j[i]+1$ and $t_m[k]\le V_j[k]$ for all other $k$.
• Global state = local states plus channel states. Consistent if every receive has its send. Strongly consistent if nothing is in transit.
• Snapshot: assumptions reliable, FIFO, strongly connected, any initiator. Marker receiving rule and marker sending rule.
• Stable predicates (deadlock, termination) need one snapshot; unstable ones need possibly and definitely over the lattice.

The problem, and the three requirements HOT 5/22

81 Bh · 80 Bh · 73 Shr · 72 Ch · 70 Ch2+62+2+42+8

Why it matters. If two processes are allowed to be in competing critical sections at the same time, the result may be wrong, which is a race condition. Mutual exclusion is the process of ensuring that this destructive interaction does not occur, that is, of allowing only one process into the critical section at a time.

Why a distributed version is needed at all. On one machine you would use a semaphore or a monitor, both of which rest on shared variables and a single kernel. In a distributed system there are no shared variables and no common kernel, so mutual exclusion must be built from message passing alone. That constraint is what makes this chapter interesting.

Three communication scenarios, and only one of them needs it:

• One way communication usually needs no mutual exclusion at all.
• Client and server communication: several clients make requests to one shared server. Any coordination is handled by the server, and the clients never interact directly, so again no explicit mutual exclusion is needed.
• Inter process communication: processes exchange information to reach a conclusion about the system or an agreement among themselves. This is where distributed mutual exclusion is required.

The basic requirements, which is the two mark opener in five sittings:

• Safety: at most one process may execute in the critical section at a time.
• Liveness: a process is granted entry if no other process is executing within the critical section, so requests eventually succeed and there is neither deadlock nor starvation.
• Ordering, or fairness: requests are granted in happened before order, so a request made earlier is served earlier.

The two families of algorithm:

• Non token based, also called permission based. Each process freely and equally competes for the right to use the resource, and requests are arbitrated either by a central control site or by distributed agreement. This family holds the central coordinator, Lamport and Ricart-Agrawala algorithms.
• Token based. A logical token representing the access right is passed in a regulated fashion among the processes, and whoever holds it may enter. This family holds the Ricart-Agrawala second algorithm and the token ring algorithm.

How the algorithms are measured, because every comparison question uses these three: the number of messages per entry and exit, the client delay before entry, and the synchronisation delay between one process leaving and the next entering.

Drop the release message, and defer the reply instead HOT 6/22

79 Bh · 78 Bh · 75 Ash · 74 Ash · 72 Ch · 71 Shr2+62+84+5

What changed from Lamport. Ricart and Agrawala's algorithm is an extension and optimisation of Lamport's: it uses only two message types, REQUEST and REPLY, and no RELEASE. The trick is that a site which cannot grant permission simply defers its reply, and sends it later when it leaves the critical section. That deferred reply does the job the release message used to do.

To enter the critical section:

• When site $S_i$ wants to enter, it sends a timestamped REQUEST to all other sites.
• When site $S_j$ receives it, it sends a REPLY to $S_i$ if and only if $S_j$ is neither requesting nor currently executing the critical section, or $S_j$ is requesting but the timestamp of $S_i$'s request is smaller than its own. Otherwise the request is deferred.

To execute: $S_i$ enters when it has received a REPLY from all other sites.

To release: on exiting, $S_i$ sends a REPLY to all the requests it deferred.

Cost: $2(N-1)$ messages per entry, namely $N-1$ requests and $N-1$ replies, which is a third less than Lamport's algorithm.

The problems, asked as "measure the performance issue" in 2071 Shrawan:

• Message traffic is expensive: $2(N-1)$ messages for every single entry, and every process must be involved even though only one resource is contended.
• The failure of any one process blocks progress, because entry needs a reply from every other site, so one dead machine stops the system. There are now N points of failure instead of one.

The alternate algorithm that addresses both is the token based algorithm, which is exactly what that question wants next.

Whoever holds the token may enter HOT 4/22

75 Ch · 73 Shr · 71 Ch · 71 Shr2+610

The principle. A single token represents the right to use the resource. It is passed among the processes, and a process enters its critical section only while it holds the token. Safety is then free: there is one token, so there can be one process inside.

Ricart-Agrawala second algorithm

A process that wants the token sends a request to all the other processes competing for the resource. The request carries the requesting process's timestamp from its logical clock and its identifier. The token is initially given to one process arbitrarily.

The data each side keeps, and why:

• Each process $P_i$ records in ${\text{request}}_{P_i}[j]$ the timestamp of the last request it received from $P_j$.
• The token itself carries $\text{token}[j]$, the timestamp of $P_j$'s last holding of the token.
• So $P_j$ has a pending request exactly when ${\text{request}}_{P_i}[j]>\text{token}[j]$: it has asked more recently than it was last served. That one comparison is the whole bookkeeping.

The four rules:

1. Initialisation: every process is in state NO-TOKEN except one, $P_x$, which is TOKEN-PRESENT. All entries of $\text{token}[]$ and $\text{request}[]$ start at zero.
2. Requesting and entering: if $P_i$ has no token it sends a request $(T_{P_i},i)$ to all processes and waits until the token arrives; then it becomes TOKEN-HELD and enters. If it already holds the token it enters at once.
3. Handling an incoming request $(T_{P_j},j)$: set $\text{request}[j]:=max(\text{request}[j],T_{P_j})$, and if this process is TOKEN-PRESENT, release the resource.
4. Releasing: search $k$ in the order $[i+1,i+2,\dots ,n,1,2,\dots ,i-1]$; for the first $k$ with $\text{request}[k]>\text{token}[k]$, set $\text{token}[i]$ to the local clock, become NO-TOKEN, send the token to $P_k$ and stop searching. If nobody is waiting, $P_i$ keeps the token.

Advantages: it needs only $N-1$ requests and one reply, and the failure of a process that is not holding the token does not prevent progress. Also, a process that keeps the token can re-enter the critical section with zero messages.

Token ring algorithm

The algorithm, in three lines:

1. The token is initially given to one process.
2. When a process needs the critical section, it waits until it gets the token from its left neighbour and retains it; after leaving the critical section it passes the token to its neighbour in the clockwise direction.
3. If a process gets the token but does not need the critical section, it immediately passes it along the ring.

The problems:

• It adds load to the network, because the token keeps circulating even when no process wants it.
• If one process fails, no progress is possible until the faulty process is removed from the ring.
• If the process holding the token fails, the token is lost, so an election must be run to generate a new one.

Its delay is unbounded in the worst case: a process that has just passed the token on must wait for it to travel all the way round, so entry can cost up to $N-1$ hops even when nobody else wants it.

Choosing a new coordinator when the old one dies TOP 9/22

81 Bh · 81 Ba · 80 Bh · 79 Bh · 76 Ch · 75 Ash · 71 Ch · 70 Asa · 69 Ch2+62+2+42+4

Why an election is needed, which is a two or three mark part in five sittings. Give the three concrete places it is used, not a general sentence:

• Clock synchronisation: Berkeley's algorithm needs a master to average the times, and a new one if the master fails.
• Mutual exclusion: the central coordinator algorithm needs a coordinator at start up and whenever it crashes, and the token ring algorithm needs a new process elected to generate a fresh token when the token holder fails.
• Any distributed computing: a distributed algorithm does not assume a central coordinator already exists, so a master must be chosen to distribute the sub problems among the slaves and collect the partial results.

The two phases of any election algorithm: select a leader with the highest priority, then inform all processes about the winner.

The Bully algorithm

Its assumption: the system is synchronous and uses timeouts to identify process failure. Its rule: the process with the highest identifier wins, and a higher numbered process will bully a lower numbered one out of the coordinator position as soon as it comes back online, which is where the name comes from.

Its three message types: Election, sent to announce an election; Answer, sent in response to an election message; and Coordinator, sent to announce the identity of the elected process.

The algorithm as rules:

1. Rule for the initiator. Set state to ELECTION-ON; send an election message to every process with a higher identifier; wait for an answer. If no answer arrives before the timeout, this process is the coordinator and sends a coordinator message to all processes. Otherwise it waits for a coordinator message, and if none arrives before a timeout it restarts the election.
2. Rule for handling an incoming election message from $P_j$: reply with an answer message to $P_j$, and if this process is not already in an election, start its own election procedure.

Cost. In the best case the process with the second highest identifier notices the failure first; it finds nobody above it, declares itself and sends $N-2$ coordinator messages. In the worst case the process with the lowest identifier starts, sending $N-1$ election messages to processes that each start their own election, giving $O(N^2)$ messages.

Getting independent processes to decide the same thing HOT 5/22

79 Bh · 78 Bh · 76 Ch · 71 Shr · 70 Asa3+43+54+6

The three requirements, which are the marks in any "how is consensus achieved" question:

• Termination: eventually every correct process sets its decision variable.
• Agreement: the decision value of all correct processes is the same: if $P_i$ and $P_j$ are correct and have decided, then $d_i=d_j$.
• Integrity: if all the correct processes proposed the same value, then any correct process in the decided state has chosen that value.

How it is achieved in a synchronous system with crash failures. The standard algorithm runs in $f+1$ rounds, where $f$ is the maximum number of processes that may fail:

1. Each process keeps a set of the values it has seen, starting with its own proposal.
2. In each round, every process multicasts the values it has newly learned to all the others, and adds to its set every value it receives.
3. After $f+1$ rounds, every process applies the same deterministic function to its set, for example minimum, and that is the decision.

Why $f+1$ rounds: at most $f$ processes can fail, so at least one round must be one in which no process failed, and in that round everybody's set became identical. It is the same value function applied to the same set, so the decisions agree.

The result you must quote: the Fischer, Lynch and Paterson theorem, 1985. No consensus algorithm can be guaranteed to terminate in an asynchronous system if even one process may crash, because no process can distinguish a crashed process from a slow one. That is not a defect of any particular algorithm; it is a proof that none can exist.

What practical systems do about it, and this is the mark that separates a good answer: they weaken one requirement. They use timeouts and failure detectors to pretend the system is synchronous; they accept probabilistic termination, as Paxos and Raft do, which are always safe and only eventually live; or they use masking by replication so that agreement is not needed on every step.

Related problems, since papers name them: Byzantine generals, where one commander supplies the value and others may lie, and interactive consistency, where the processes must agree on a vector of values, one per process.

Agreement when some of the participants lie HOT 6/22

81 Ba · 80 Bh · 75 Ch · 71 Ch · 70 Ch · 70 Asa1+2+52+2+42+8

The story, which is also the specification. Three or more generals must agree to attack or to retreat. One general, the commander, issues the order; the others, the lieutenants, must decide what to do. One or more of the generals may be treacherous: a traitorous general may tell one lieutenant to attack and another to retreat. The difference from plain consensus is that here a single process supplies the value to agree on.

The requirements:

• Termination: eventually each correct process sets its decision variable.
• Agreement: the decision value of all correct processes is the same.
• Integrity: if the commander is correct, then all correct processes decide on the value the commander proposed. If the commander is faulty, they must still agree on something, but it need not be what the commander said.

The impossibility with three generals. Suppose the commander says "attack" to lieutenant 1 and "retreat" to lieutenant 2. Each lieutenant reports what it heard to the other. Lieutenant 1 now holds two contradictory values, one from the commander and one from lieutenant 2, and cannot tell whether the commander lied or lieutenant 2 did. A majority of two conflicting values does not exist, so there is no correct rule.

The solution with four generals, that is one commander and three lieutenants with at most one traitor:

1. The commander sends its value to each of the three lieutenants.
2. Each lieutenant forwards the value it received to the other two lieutenants.
3. Each lieutenant now holds three values: the one from the commander and two reports. It takes the majority of those three.

If the commander is correct, all three lieutenants received the same value, so the majority is that value even though the traitor reported something else. If the commander is the traitor, the three correct lieutenants each hold the same multiset of three values, so their majorities agree with one another, which is all agreement requires.

What it teaches, which is the phrasing 2075 Chaitra uses. Three things: agreement is possible even with malicious participants, but only if they are a small enough minority; the cost is high, since the message complexity is exponential in the number of rounds for the classic algorithm; and redundancy alone is not enough, because it is the ratio of faulty to correct processes that decides whether agreement is reachable at all.

Chapter 6 in one screen

• Requirements: safety (one at a time), liveness (no deadlock or starvation), ordering (happened before order).
• Central coordinator: request, OK, release. 3 messages. Coordinator is a bottleneck and a single point of failure.
• Lamport: REQUEST, REPLY, RELEASE, a queue at every site, enter when your request is at the top and you have a larger timestamp from everybody. $3(N-1)$ messages.
• Ricart-Agrawala: REQUEST and REPLY only, defer the reply instead of releasing. $2(N-1)$ messages. Any crash blocks it.
• Token based: one token, three states, $\text{request}[j]>\text{token}[j]$ means a pending request. $N-1$ plus one message, and zero if you hold the token.
• Token ring: pass clockwise, hold it if you need it. Load even when idle, and failure breaks the ring.
• Election is needed by Berkeley, the central coordinator, the token ring, and any master and slave computation.
• Bully: election, answer, coordinator. Best case $N-2$ messages, worst case $O(N^2)$. Needs a synchronous system with timeouts.
• Ring (Chang and Roberts): participant flag, forward the larger UID, two circuits. Worst case $3N-1$.
• R-multicast properties: integrity, validity, agreement. Orderings: FIFO, causal, total. Total by sequencer or by ISIS.
• Feedback suppression: NACK multicast to the whole group, after a random delay, so duplicate reports are suppressed.
• Consensus: termination, agreement, integrity. $f+1$ rounds in a synchronous system. FLP: impossible to guarantee in an asynchronous system with one crash.
• Byzantine: impossible with three, works with four, needs $3f+1$ processes and $f+1$ rounds.

Three reasons, three ways, one problem TOP 8/22

81 Bh · 80 Bh · 79 Bh · 78 Bh · 73 Shr · 72 Ch · 72 Ka · 70 Ch3+52+3+32+4+2

1. Performance enhancement. A copy placed close to the process that uses it cuts the time to reach the data. The everyday example is a web browser keeping a cached copy of a page it has already fetched, which removes the latency of going back to the server. The same idea scales up: a content delivery network is nothing but replication for performance.

2. Increased availability. Users want a service to be available whenever they need it, and replication gives redundancy, so the data is still reachable when a server fails. The arithmetic is worth quoting, because it shows how fast availability improves:

where each of the $n$ servers has an independent probability $p$ of being down. A 5 percent chance of failure gives 95 percent availability with one server, but $1-{0.05}^2=99.75$ percent with two independent servers. The word independent is doing the work: two servers in the same rack on the same power supply do not multiply like that.

3. Fault tolerance. Even when one server fails, the data on the others is still served to the users, so a server crash does not bring the whole system down until it can be rebooted. Availability is about reaching some answer; fault tolerance is about reaching a correct one, even while a replica is misbehaving.

• Explicit file replication: the programmer controls the entire process, writing to each server in turn. Maximum control, maximum work, and no transparency at all.
• Lazy replication: one copy is created on some server, and that server later makes replicas on the others automatically, without the programmer's knowledge. Cheap and fast, and the copies are briefly out of date.
• Group communication: every write is transmitted to all the servers at once, so the extra copies are made at the same moment as the original. Consistent, and it costs a multicast per write.

The problem replication creates, and it is the only one: inconsistency. If one copy is modified it no longer matches the rest, so to stay consistent every copy must be modified. Everything else in this chapter is a scheme for doing that at an acceptable cost.

Challenges and requirements, for the questions phrased that way:

• Replication transparency: the client must not know how many copies exist, or which one answered.
• Consistency: the copies must satisfy the consistency model the application needs, which is a choice, not a given.
• Update propagation: deciding what to send, the new value or the operation, and when, eagerly or lazily.
• Cost: storage, and network traffic proportional to the number of replicas.
• Placement: where to put the replicas so they are near the clients and independent in their failures.

Every replica does the work TOP 10/22

81 Ba · 80 Bh · 79 Bh · 78 Bh · 76 Ch · 75 Ch · 75 Ash · 74 Ash · 72 Ch · 69 Ch3+52+4+22+3+3

The five phases, filled in for active replication:

1. Request: the front end attaches a unique identifier and totally ordered reliable multicasts the request to the group of replica managers.
2. Coordination: the group communication system delivers the request to every replica manager in the same total order. This phase is where all the work happens.
3. Execution: every replica manager executes the request. Because they are deterministic state machines starting from the same state and receiving the same ordered input, they all reach the same new state.
4. Agreement: no agreement phase is needed, because the total ordering already guaranteed it.
5. Response: each replica manager sends its response to the front end, which takes the first, or compares them if it wants to tolerate wrong answers.

Benefits:

• Every server can respond to client queries with up to date data, so reads scale with the number of replicas.
• Immediate failover: a replica dying is invisible, because the others already have the answer and the front end simply uses one of theirs. There is no recovery pause.
• It can tolerate Byzantine failures, because the front end can collect several responses and take the majority, which passive replication cannot do.

Limitations:

• Waste of resources, since all replicas do exactly the same work, so $n$ machines deliver the throughput of one for writes.
• It propagates updates only, which requires determinism. Any operation whose result depends on the local clock, a random number or the order of local threads will make the replicas diverge.
• It depends on totally ordered multicast, which is expensive and is itself a consensus problem.

One primary does the work and tells the others TOP 10/22

81 Ba · 80 Bh · 80 Ba · 79 Bh · 78 Bh · 76 Ch · 75 Ash · 74 Ash · 70 Ch · 69 Ch3+52+4+22+3+3

The five phases, filled in for passive replication:

1. Request: the front end sends the request, carrying a unique identifier, to the primary replica manager only.
2. Coordination: the primary takes each request in the order it arrives, and checks the identifier in case it has already executed this request; if so it simply resends the old reply.
3. Execution: the primary executes the request and stores the response.
4. Agreement: if the request is an update, the primary sends the updated state, the response and the identifier to all the backups, and each backup acknowledges. This phase is where all the work happens.
5. Response: the primary responds to the front end, which hands the result to the client.

What happens when the primary crashes, analysed against the six steps of the figure, which is worth a mark or two on its own:

• Before step 2, before doing the work: no harm is done, and the backup simply redoes it.
• After the work but before the update: the work is done a second time by the backup.
• After step 4 and before step 6: the work may end up being done three times, once by the primary, once by the backup as a result of the update, and once after the backup becomes the primary.

Recovery from a primary failure may therefore be time consuming and complex, and the correct answer is that operations should be idempotent or identified so duplicates can be filtered, which is what the request identifier in phase 2 is for.

Three kinds of failover, a neat three point list:

• Cold failover: the backup restarts the applications that were running on the primary. Any work in progress is lost.
• Warm failover: applications periodically write checkpoint files to storage shared with the backup; the backup reads them and resumes from the last checkpoint.
• Hot failover: the backup runs in lockstep with the primary on the same inputs, so when it takes over it is already in the exact state the primary was in.

Choosing the new primary is an election, and the surviving replica managers must also agree on the set of operations the old primary had completed, which is why view synchronous group communication is used.

Gossip: the technique that makes a service highly available HOT 4/22

81 Bh · 75 Ash · 71 Shr · 69 Ch3+52+4

The difference from fault tolerance, and it is the first sentence of the answer. A fault tolerant service keeps giving correct answers, which needs the replicas to agree before replying, so a client waits. A highly available service gives an answer whenever the client asks, using whatever replicas are reachable, and accepts that the answer may be slightly stale. Availability is bought with consistency.

The two guarantees it makes:

• Each client obtains a consistent service over time, meaning it never sees data older than what it has already seen, even if it moves to a different replica manager.
• Relaxed consistency between replicas. All replica managers eventually receive all updates and apply them in an order that respects causality. This is eventual consistency.

How the vector timestamps do it. Each front end keeps a vector timestamp $\text{prev}$ reflecting the latest data it has seen, and every request carries it. A replica manager that has not yet received those updates holds the request back until gossip brings them, so the client can never go backwards in time. When clients communicate directly with each other they piggyback their vector timestamps, which are then merged, so causality is preserved even outside the service.

How a request is processed:

1. Request: the front end sends the request to a replica manager, normally the nearest or least loaded one. A query blocks; an update returns at once.
2. Update response: the replica manager replies to an update immediately, before it has been applied anywhere else, which is why the service feels fast.
3. Coordination: the replica manager holds the request until it can be applied in causal order, gossiping if necessary to collect the missing updates.
4. Execution: it executes the request against its own replica.
5. Query response: it replies to a query, with the new vector timestamp.
6. Agreement: the replica managers propagate the update lazily, by exchanging gossip messages whenever convenient. This is the phase that is deliberately delayed.

What a replica manager holds: the value, which is the application state; a value timestamp; an update log of updates not yet stable; a replica timestamp recording the updates accepted; and an executed operation table, which stops an update being applied twice when it arrives again by gossip.

How gossip answers active and passive replication, which is the phrasing 2081 Bhadra uses. Active replication makes every client wait for a totally ordered multicast, and passive replication makes every client wait for the one primary, so both are unavailable exactly when the network is partitioned. Gossip takes the update at any replica and returns immediately, so a partitioned or distant client still gets service; the cost is that other clients may not see the update for a while, which the vector timestamps keep from being incoherent.

Two case studies worth naming: Bayou, which lets any replica accept updates and resolves conflicts later by application supplied merge procedures, and Coda, a file system that lets a disconnected laptop keep working on cached files and reintegrates on reconnection.

Chapter 7 in one screen

• Three reasons: performance, increased availability ($1-p^n$), fault tolerance.
• Three ways to replicate: explicit, lazy, group communication.
• The one problem: inconsistency.
• System model: client, front end, replica managers. Five phases: request, coordination, execution, agreement, response.
• Active: totally ordered multicast, every replica executes, needs determinism, immediate failover, tolerates Byzantine faults, wastes resources.
• Passive: one primary executes and updates backups, needs no determinism, less traffic, needs an election and a slower recovery, cannot tolerate a lying primary.
• Failover: cold (restart), warm (checkpoints), hot (lockstep).
• Faults: transient, intermittent, permanent. Processor: fail silent or Byzantine.
• Redundancy: information, time, physical. TMR masks one fault per stage with three voters.
• k fault tolerant: $k+1$ processors for fail-stop, $2k+1$ for Byzantine.
• Consistency, strongest first: strict, sequential, causal, processor, PRAM; then weak, release, entry.
• Gossip: any replica manager answers, updates spread lazily, vector timestamps keep each client consistent over time. Eventual consistency.
• Transactions: one copy serializability; read one write all; available copies with local validation; quorums with $W>N/2$ and $R+W>N$.