Appendix

Diagram Key & Glossary

How to read the pictures on this site, and every term the subject uses in one alphabetical list. Each kind of diagram is drawn once here with every symbol labelled, so that when you meet one in a Part you already know its language.

A.1

How the Diagrams Are Drawn

Distributed systems is a subject about machines that cooperate by sending messages. Almost every picture in it answers one of a handful of questions. Where do the processes live, and what network joins them? In what order do the messages travel, and what happens when one goes missing? Which layer of software does what? What is inside a message? The diagrams on this site use one consistent drawing style for each of those questions, and this section shows each style once.

Hosts, processes and the network

A host is one computer. It is drawn as a dashed rounded box, because it is a boundary rather than a thing that does work. Inside it sit processes, the running programs, drawn as solid boxes. The network between hosts is drawn as a teal dashed region. A solid arrow is a message that starts an interaction (a request); a dashed arrow with an open head is a message that answers one (a reply).

The basic picture. Dashed outlines are hosts; solid boxes are processes; the teal region is the network. A process is identified on the network by its host's address plus a port. Colours mark roles and stay the same within a figure: here blue is the client and red is the server.

Message sequences: time flows down

When the order of messages matters, each process gets a vertical lifeline and time runs down the page. A horizontal arrow is a message; the thin white bar on a lifeline (an activation) shows when that process is busy handling something. A red cross marks a message the network lost, and a clock marks a timeout. This is the style used for request-reply, RMI, Kerberos and TLS.

Read top to bottom. Messages are numbered in the order they are sent. The same request id (2) on messages 3 and 4 is what lets the server recognise a retransmission as a duplicate rather than a new request.

Time-space diagrams: time flows right

When the point is how long things take, or in what order events happen at different processes, each process gets a horizontal timeline with time running left to right. A dot is an event (sending, receiving or a local step), and a message is a slanted arrow, because it arrives later than it was sent. The slant is the delay. This is the style used for the interaction model, clocks and multicast ordering.

Slant equals delay. m3 was sent before m2 but arrives after it, so p3 sees the messages in a different order from the order in which they were sent. Pictures like this are how the subject shows why message ordering and timeouts are hard.

Layers and protocol stacks

Software in a distributed system is built in layers, each using the one below and serving the one above. A layer diagram stacks them as bands. When two hosts communicate, data goes down the sender's stack, across the physical network, and up the receiver's stack; each layer talks logically to its peer on the other side.

Each colour is one layer, and the same colour means the same layer on both hosts. Middleware (violet) is the layer this subject cares most about: it hides the network so that a remote call can look like a local one.

Inside a message

A message is a sequence of bytes with a fixed layout. A message layout draws its fields as a row of boxes, each with the field's name and its type. This one is the request-reply message from Part VI.

Shaded fields are header, white is payload. The header is what the protocol uses to deliver and match messages; the payload is the application's data, flattened into bytes (marshalled).

Threads inside a server

A thread is one sequence of execution inside a process. Diagrams of multithreaded servers show requests arriving, waiting in a queue, and being handed to threads, drawn as role-coloured boxes inside the server's process boundary.

Boxes inside the dashed boundary are threads of one process, so they share its memory (the shared data on the right). That shared memory is why threads need synchronisation, which Part IV explains.

Security: principals, keys and encrypted messages

Security protocols are told as stories about people. Alice and Bob want to communicate; Eve eavesdrops and Mallory actively attacks. A key is drawn as a key icon, and a message encrypted with key K is written {M}K.

Who holds which key is the whole story. Alice and Bob each hold K_AB (green), so only they can read the message. Eve (red) sees the bytes on the channel but cannot decrypt them.

Notation	Meaning
K_A, K_B	Alice's and Bob's secret keys (each shared only with a trusted server)
K_AB	A secret key shared by Alice and Bob
K_Apriv, K_Apub	Alice's private key (kept secret) and public key (published)
{M}K	Message M encrypted with key K
[M]K	Message M signed with key K
H(M) or Digest(M)	A secure hash (digest) of M: a short fixed-length fingerprint

Trees: name spaces and hierarchies

Names in a distributed system are usually organised as a tree. Each node is one label; a full name is the path from the root. For DNS the name is read right to left, so www.unimelb.edu.au is the path root → au → edu → unimelb → www.

The highlighted path is one name. Reading the labels from the leaf up to the root gives www.unimelb.edu.au. Each subtree can be run by a different organisation, which is what makes the name space scale.

In short

Dashed outline = a host; solid box = a process; teal region = the network.
Solid arrow = a request or one-way message; dashed arrow with an open head = a reply. A red cross is a lost message, and a clock is a timeout.
Time runs down in sequence diagrams and right in time-space diagrams, where a slanted arrow shows delay.
Colours mark roles consistently within a figure, and the caption says what each colour means.

A.2

Glossary

Every key term in the subject, alphabetically, with a one-line definition and a link to the Part that explains it in full.

Term	Meaning	Part
A
Access control list (ACL)	A list stored with a resource saying which domains may perform which operations on it.	X
Access transparency	Local and remote resources are accessed using identical operations.	I, VIII
Address	A value that identifies where an object is rather than the object itself; efficient, but it breaks when the object moves.	IX
Address space	A range of virtual memory with its own access rights; a process cannot touch memory outside it.	V
Alias	A name defined to denote the same information as another name, such as a DNS CNAME record.	IX
Aliasing problem	The same virtual address means different data in different address spaces, so TLBs and virtually addressed caches must be flushed on a process switch.	IV
Architectural model	A description of a system's components, their placement on machines and their relationships, such as client-server or peer-to-peer.	II
Asynchronous communication	Message passing in which send returns once the message is copied to a local buffer; receive may block or not.	III
Asynchronous system	A system with no bounds on process speed, message delay or clock drift; it models the Internet.	II
At-least-once semantics	Retransmission without duplicate filtering: a result means the procedure ran one or more times; safe only for idempotent operations (Sun RPC).	VI
At-most-once semantics	Retransmission, duplicate filtering and a reply history: a result means exactly once, an exception means once or not at all (Java RMI, CORBA).	VI
Authenticator	In Kerberos, {C, t}K_CS: built by the client to prove its identity and freshness, used only once.	X
Authoritative data	DNS data from a zone's own primary or secondary servers, as opposed to cached copies elsewhere.	IX
Automounter	A client service that mounts a remote directory on first reference, from the first listed server to respond.	VIII
Availability	The proportion of time a system is available for use.	I
B
Best-effort delivery	IP's service: packets may be lost, duplicated, delayed or reordered, with no guarantee.	III
Binary OS emulation	Offering another OS's system-call interface on a microkernel so that existing compiled programs run unchanged (e.g. UNIX on Mach).	V
Binding	The association between a name and an object's attributes, held by a name service.	IX
Bio-daemon	A block I/O daemon that does read-ahead and delayed write so NFS clients do not block on the network.	VIII
Broadcast storm	Unbounded re-forwarding of a broadcast around a cycle in the network, causing duplicate deliveries and flooding.	XI
Byzantine failure	An arbitrary failure: a process or channel may do anything, including sending wrong values; the most severe failure class.	II
C
Cache	A store of recently used data objects that is closer to its clients than the objects themselves, used if the copy is up to date.	II
Callback	A remote object exported by a client and registered with a server, which invokes it to notify the client of events instead of being polled.	VI
Callback promise	In AFS, the server's promise to notify a client holding a file if another client updates it.	VIII
Capability	An unforgeable token issued when access is checked, which the holder presents with later requests.	VIII, X
Causal ordering	If m1 happened-before m2, every member delivers m1 first; implemented with vector timestamps; implies FIFO.	VII
Certificate	A statement signed by an authority, typically binding a name to a public key.	X
Certificate chain	A sequence of certificates, each signed by the one above, ending at a self-signed root key obtained out of band.	X
Challenge–response	Proving knowledge of a secret without sending it, by answering a fresh challenge that only the secret's holder can answer.	X
Check-then-act race	A race in which two threads both pass a check before either acts on it, such as two enrolments taking the last seat.	IV, XI
Cipher block chaining (CBC)	A block-cipher mode in which each plaintext block is XORed with the previous ciphertext block before encryption.	X
Client module	The per-client component that offers a UNIX-like API, resolves pathnames iteratively, keeps offsets and caches blocks.	VIII
Client stub	A generated procedure that looks local to the client, marshals the procedure id and arguments, and unmarshals the result.	VI
Client-server	Architecture in which clients access shared resources managed by servers; client and server are roles, so a server can also be a client.	II
Clock drift rate	The rate at which a clock deviates from a perfect reference clock (about 10^-6 s per second for quartz).	II
Clock skew	The difference between the readings of two clocks at the same instant.	II
Closed / open group	In a closed group only members may multicast to it; in an open group outsiders may send to it too.	VII
Coffman conditions	The four necessary conditions for deadlock: mutual exclusion, hold and wait, no preemption and circular wait.	IV
Commit (NFS v3)	Server caching policy that keeps writes in the cache until the client sends commit, usually on close.	VIII
Competing consumers	Several consumers taking messages from one queue, each message going to one of them, which balances load.	VII
Computer network	The medium that moves messages between explicitly addressed, visible computers using protocols; a distributed system is built on top of one.	I
Concurrency transparency	The property that clients sharing a resource concurrently each get correct results as if they were alone.	V
Confidentiality	Protection of information against disclosure to unauthorised individuals.	I
Content-based subscription	Subscribing with predicates over event attributes, such as temperature > 30; most expressive and hardest to route.	VII
Context switch	Saving one thread's processor registers and loading another's; switching processes also needs a domain transition (a change of address space).	IV
Copy-on-write	A fork optimisation in which parent and child share write-protected page frames and a page is copied only when one of them writes to it.	IV
CORBA CDR	CORBA's binary external data representation: no type information, sender's byte order plus a flag, aligned fields, code generated from IDL.	III
Critical section	Code that accesses shared data and must be executed by at most one thread at a time.	IV
D
Daemon thread	A background thread that does not keep the JVM alive; the JVM exits when only daemon threads remain.	IV
Datagram	A self-contained, fully addressed message sent independently over UDP.	III
Deadlock	A state in which each thread in a set waits for ever for a lock held by another thread in the set.	IV
Denial of service	Flooding a channel or resource so that others are denied access to it.	X
Digital signature	A digest of a message encrypted with the signer's private key, giving authentication, integrity and non-repudiation.	X
Directory identifier (DI)	In GNS, the unique identifier of a directory, used to keep old names working when trees are merged or moved.	IX
Directory service	The component that maps text names to UFIDs; it stores directories as files in the flat file service.	VIII, IX
Discovery service	A directory service for spontaneous networks that updates automatically as devices join and leave, and is found by multicast.	IX
Dispatcher	The server component that uses the procedure or operation id in a request to select the right server stub or skeleton method.	VI
Distributed file system (DFS)	A service that lets programs on different computers store and access remote files exactly as they do local files.	VIII
Distributed garbage collection	Reclaiming a remote object once no local or remote references remain; Java uses reference counting (addRef, removeRef) with leases.	VI
Distributed operating system	An OS that presents a whole network as a single system image and places processes transparently; none is in general use.	IV
Distributed shared memory (DSM)	An abstraction that lets processes on computers without shared physical memory read and write a logical shared address space.	VII
Distributed system	A system whose components on networked computers communicate and coordinate their actions only by passing messages (CDK); to its users it appears as a single computer (Tanenbaum).	I
DNS	The Domain Name System: the Internet's partitioned, replicated and heavily cached name service, mainly mapping host names to IP addresses.	IX
Domain transition	A crossing from one protection domain (address space) into another, such as from user space into the kernel.	V
Duplicate filtering	The server recognising a repeated (client, requestId) and not treating the retransmitted request as new.	VI
Duplicate suppression	Giving each message a unique ID and forwarding or delivering it only the first time a server sees that ID.	XI
Duplicate-request cache	A server record of recent requests and replies, so a retransmitted non-idempotent request gets the original reply.	VIII
E
Emulation	Reproducing in software the interface of a system that is not actually present, either an OS's system calls or another instruction set.	V
Encapsulation	Each layer of the protocol stack wraps the data in its own header on the way down and strips it on the way up.	III
Encapsulation (of a resource)	Offering a useful service interface to a resource while hiding implementation details such as memory and device management.	V
End-to-end argument	Some communication functions can be implemented completely and reliably only with the help of the application at the end points.	II
Execution environment	The unit of resource management and protection domain of a process: its address space, synchronisation and communication resources, and higher-level resources such as open files.	IV
External data representation	An agreed standard for the representation of data structures and primitive values in messages.	III
External pager	A user-level server, as in Mach, to which the kernel passes page faults so that it can supply the missing pages.	V
F
Factory method	A remote method that creates a new remote object in the server and returns its reference, since interfaces have no constructors.	VI
Fail-stop failure	A process halts and stays halted, and other processes can detect this with certainty (needs a synchronous system).	II
Failure	The service no longer meets its specification: it is unavailable or too slow.	I
False sharing	Unrelated variables on the same page make the page ping-pong between writers that share no data.	VII
Fault	The cause of a failure, such as a component crash.	I
Fault tolerance	No failure despite faults: faults are handled and hidden from users.	I
FIFO ordering	Messages from the same sender are delivered in the order sent; implemented with per-sender sequence numbers.	VII
File descriptor	A small integer returned by open that a UNIX process uses to refer to an open file.	VIII
File group	A collection of files on one server that can move between servers; each UFID contains its group ID.	VIII
Filtering-based routing	Brokers propagate subscriptions towards publishers and forward events only along paths that lead to matching subscribers.	VII
Flat file service	The component of the file service architecture that operates on file contents and attributes, naming files only by UFID.	VIII
Flow control	TCP's mechanism (a window carried in acks) that stops a fast sender overrunning a slow receiver.	III
Framing	Marking where each message ends in a byte stream such as TCP, by a delimiter (e.g. a newline) or a length prefix.	XI
Freshness interval (t)	In NFS client caching, how long a cache entry is trusted without asking the server.	VIII
Fundamental models	The interaction, failure and security models: formal statements of properties common to all architectures.	II
G
Glue record	An A record in a parent zone giving the IP address of a name server for a delegated subdomain.	IX
Group communication	A message sent to a group is delivered to all its current members, with membership, failure detection, reliability and ordering added to multicast.	VII
Group membership service	Manages joins and leaves, detects failures, notifies members of view changes and expands group addresses.	VII
H
Hard mount	An NFS mount in which a process blocks and the client retries until the server responds.	VIII
Heterogeneity	Variety in networks, hardware, operating systems, programming languages and implementations that must nevertheless interoperate.	I
Hold-back queue	Where a group member keeps a received message until delivering it would not break the required ordering.	VII
HTTP	The Web's request-reply protocol between browsers and servers, with GET and POST, MIME content types and one resource per request.	I
Hurdle	A minimum mark you must reach in one component regardless of your total; here 30/60 on the exam itself.	XI
Hybrid kernel	A kernel that keeps substantial functionality in kernel space for performance but organises it as modules with clean interfaces (e.g. Windows NT).	V
Hybrid protocol	A protocol that uses public keys to authenticate and exchange a session key, then symmetric encryption for the data.	X
Hypercall	A call from a paravirtualized guest OS to the hypervisor, replacing a privileged instruction.	V
Hypervisor (VMM)	A thin software layer on the hardware that provides several virtual machines, each running its own OS.	V
I
Idempotent operation	An operation that can be performed repeatedly with the same effect as if it had been performed exactly once.	VI
Identifier	A name interpreted only by programs, chosen to be efficient to store and look up, such as an NFS file handle or a remote object reference.	IX
Independent failures	One component can fail while the others keep running, unaware at first; a failed network can't be told from a slow one.	I
Indirect communication	Communication through an intermediary, with no direct coupling between the sender and the receiver(s).	VII
Integrity	Protection of information against alteration or corruption.	I, III
Interface Definition Language (IDL)	A language-neutral notation for interfaces, with typed in, out and inout parameters, compiled into stubs for each language (e.g. Sun XDR, CORBA IDL).	VI
Interprocess communication (IPC)	How processes on different computers exchange data by sending messages, since they share no memory.	III
Intrinsic lock	The lock every Java object has, used by synchronized; it is reentrant and released automatically when the synchronized code exits.	IV
Invocation mechanism	Any means of accessing an encapsulated resource, such as a system call to a kernel or an RMI to a server object.	V
Invocation semantics	What a caller can assume about how many times a remote procedure was executed: maybe, at-least-once or at-most-once.	VI
IP multicast	Sending one UDP datagram to a class D group address (224.0.0.0 to 239.255.255.255) so every group member receives it; unreliable and unordered.	III
Iterative navigation	Navigation in which the client itself contacts one name server after another, following referrals.	IX
J
Java object serialization	Java's binary flattening of an object graph, carrying class name, version and field types, with handles for shared objects.	III
JavaSpaces	Sun's Jini-based object space whose entries are written with leases and matched by templates with null wildcards.	VII
JGroups	Java toolkit for reliable process-group communication built from channels, building blocks and a composable protocol stack.	VII
Jitter	The variation in the time taken to deliver a series of messages.	II
JMS	The Java Messaging Service specification, unifying pub-sub (Topic) and message queues (Queue) behind one API.	VII
K
Kerberos	An authentication and key-distribution system for one domain, based on Needham–Schroeder with timestamps, using tickets and authenticators.	X
Kernel	The program that stays loaded from system start and runs with complete access privileges to the physical resources.	V
L
Latency	The delay between the start of a message's transmission and the beginning of its receipt.	II
Layered kernel	A kernel organised as a hierarchy in which each layer uses only the interface of the layer below, all in kernel mode (e.g. THE, VAX/VMS).	V
Lease	Permission granted for a limited period that must be renewed, so a crashed client's claim on a resource simply expires.	VI
Lightweight RPC (LRPC)	An RPC optimisation for calls within one computer that shares an argument stack and lets the client's thread run the procedure in the server's domain.	V
Listening socket	A TCP server socket that accepts connection requests; each accept creates a new socket for that client on the same port.	III
Location transparency	Resources are accessed without knowledge of their physical or network location.	I
Lock granularity	How much data one lock protects; finer locks allow more concurrency but more risk of deadlock.	IV, XI
Lock ordering	Acquiring several locks in one global order (e.g. ascending subject code) so that circular wait, and hence deadlock, cannot occur.	XI
M
MAC	A message authentication code: a hash of the message with a shared key; gives integrity and authentication but not non-repudiation.	X
Man-in-the-middle	An attack that intercepts the first key exchange, substitutes the attacker's keys, then decrypts, re-encrypts and forwards every message.	X
Marshalling	Assembling data items into an external data representation suitable for transmission; unmarshalling rebuilds them on arrival.	III
Masquerading	Sending or receiving messages using another principal's identity without authority.	X
Maybe semantics	No retransmission: the procedure ran once or not at all, and without a result the caller cannot tell which.	VI
Mechanism vs policy	The design rule that the kernel provides fixed basic mechanisms while varying policies are implemented by dynamically loaded servers.	V
Message framing	Marking where each message ends in a TCP byte stream, by a delimiter, a length prefix or fixed-size messages.	III
Message queue	A point-to-point, persistent indirect service in which each message is removed by exactly one consumer.	VII
Message selector	A JMS filter written in a subset of SQL over a message's header and properties, never its body.	VII
Microkernel	A minimal kernel providing only address spaces, threads and local IPC, with all other services run as user-level servers (e.g. Mach, L4).	V
Middleware	A software layer that provides a programming abstraction and masks the heterogeneity of networks, hardware, OSs and languages (e.g. CORBA, Java RMI).	I, II, IV
Mobile agent	A running program, code plus data, that travels between computers performing a task on someone's behalf and returns with the results.	II
Mobile code	Code sent from one computer to run on another, such as applets or JavaScript; made portable by the virtual machine approach.	I, II
Mobility transparency	Resources and clients can move within the system without affecting users or programs.	I, VIII
Model	An abstract, simplified but consistent description of one aspect of a system's design.	II
Monitor	An object whose synchronized code can be executed by at most one thread at a time, enforced by its intrinsic lock.	IV
Monolithic kernel	A kernel in which almost all OS services run in kernel mode in one address space and call each other by procedure calls (e.g. UNIX, Linux).	V
Mount service	The user-level NFS server process that exports file systems listed in /etc/exports and returns a directory's file handle.	VIII
MPI	Message Passing Interface: a standard for message passing in high-performance computing with blocking and non-blocking sends.	III
Multicast navigation	Navigation in which the client multicasts the name to a group of servers and only the holder replies.	IX
N
Name	A human-readable value, usually a string, that is resolved to an identifier or an address.	IX
Name service	A service that stores naming contexts (sets of name-to-attribute bindings) and whose main operation is to resolve names.	IX
Name space	The collection of all syntactically valid names recognised by a service; a valid name may still be unbound.	IX
Naming context	A set of bindings between names and attributes, within which a simple name is looked up.	IX
Naming domain	A name space with a single administrative authority for assigning names, which may delegate subdomains.	IX
Navigation	Locating naming data from more than one name server in order to resolve one name.	IX
Network operating system	An OS in which each node runs its own OS image and manages its own processes; the user chooses where programs run.	IV
Network transparency	Access and location transparency together.	I
NFS file handle	NFS's opaque file identifier: filesystem identifier, i-node number and i-node generation number.	VIII
No global clock	Clocks in a distributed system can be synchronised only to limited precision, because message delays vary.	I
Non-pure name	A name that contains information about the object, typically its location, such as tawfiq@128.250.1.25.	IX
Non-repudiation	Proof of sending or receiving, so a party can't later deny it; given by a digital signature.	I, X
Nonce	A value used only once, included in a message to prove that the message is fresh.	X
Null RPC	An RPC with no arguments that runs an empty procedure and returns nothing, used to measure invocation latency (about 0.1 ms on a LAN).	V
O
Omission failure	A message is dropped (e.g. checksum error or full buffer) and never delivered; UDP and IP multicast suffer them.	III, VI
One-copy update semantics	Every process sees the file contents it would see if only a single copy of the file existed.	VIII
Openness	Whether a system can be extended and re-implemented; requires published key interfaces.	I
Overlay network	A virtual network of nodes and virtual links built on top of an underlying network such as IP.	III
P
Paravirtualization	Virtualization in which the hypervisor offers a modified interface and the guest OS is ported to it, as in Xen.	V
Peer-to-peer	Architecture in which all processes play similar roles, so resources grow with the number of users; objects are replicated across peers.	II
Physical model	A representation of a distributed system's hardware (nodes and links) that abstracts away from specific computer and networking technologies.	II
Platform	The lowest hardware and software layers (OS plus hardware), implemented independently in each computer.	II, IV, V
Popek & Goldberg condition	An architecture is virtualizable if all sensitive instructions are privileged, so they trap to the hypervisor.	V
Port	A 16-bit number identifying the process on a host that should receive incoming data; one receiver, many senders.	III
Port mapper	Sun RPC's binder: a service on a well-known port where servers register (program, version, port) and clients ask for a server's port.	VI
Preemptive scheduling	Scheduling in which a thread can be suspended at any point, so shared data must be synchronised but multiprocessors can be used.	IV
Principal	The authority, a user or a process, on whose behalf an invocation is made or a result issued.	II, X
Process group vs object group	Process groups deliver byte arrays to processes (like sockets); object groups multicast marshalled invocations via a proxy (like RMI).	VII
Producer–consumer problem	Coordinating threads that add to and remove from a bounded buffer: producers wait while it is full, consumers while it is empty.	IV
Promise	A placeholder returned at once by an asynchronous invocation, from which the caller claims the result later.	V
Protection ring	An x86 privilege level; normally the kernel runs in ring 0 and applications in ring 3.	V
Protocol	An agreed set of rules fixing the sequence of messages exchanged and the format of the data in them.	III
Proxy	The client-side local stand-in for a remote object (one per remote object) that implements its remote interface and forwards each call as a request.	VI
Proxy server	An intermediary that acts on behalf of clients; a web proxy provides a shared cache and can give access through a firewall.	II
Public-key cryptography	Encryption with a key pair: what the public key encrypts only the private key can decrypt; 100–1000 times slower than secret-key.	X
Publish-subscribe	Publishers publish events to an event service, which matches them against subscribers' filters and notifies the matches.	VII
Pure name	An uninterpreted bit pattern that holds no information about the object, so it must always be looked up before use.	IX
Q
Quality of service	A system's non-functional properties (reliability, security, performance as timeliness guarantees) plus adaptability.	I
R
Race condition	A bug where the outcome depends on the unpredictable interleaving of threads accessing shared data.	IV
Read-write pointer	The current position in an open UNIX file, kept by the kernel and advanced by each read or write.	VIII
Read–write lock	A lock that allows either many concurrent readers or one exclusive writer, such as Java's ReentrantReadWriteLock.	IV
Recursive navigation	Server-controlled navigation in which each server forwards the request to the next and the result returns along the chain.	IX
Reference count	The number of names (links) a file has; the file is deleted when it reaches zero.	VIII
Reliable communication	Communication with validity (every outgoing message is eventually delivered) and integrity (identical to what was sent, no duplicates).	II
Reliable multicast	Multicast with integrity (unchanged, at most once), validity (eventually delivered) and agreement (one member gets it, all do).	VII
Remote interface	The interface specifying which methods of an object can be invoked from other processes; in Java it extends Remote.	VI
Remote invocation	One complete client-server interaction, from the client sending a request to it receiving the reply.	I, VI
Remote object reference	An identifier for a remote object valid throughout a distributed system (address, port, time, object number, interface), unique in space and time.	III, VI
Remote reference module	The RMI component that keeps the remote object table and translates between local references and remote object references, creating proxies.	VI
Rendezvous routing	Subscriptions are stored at SN(s) and events sent to EN(e), which must intersect whenever e matches s.	VII
Replay attack	Storing intercepted messages and sending them again later; it works even on encrypted messages.	X
Replication transparency	Multiple instances of a resource are used without users or programmers knowing of the replicas.	I
Reply history	A server's record of replies already sent, as (requestId, reply, client id), so a duplicate can be answered without re-executing the operation.	VI
Request-reply protocol	The message pattern underlying RPC and RMI: the client sends a request (doOperation, which blocks) and the server answers with a reply (getRequest, sendReply).	VI
requestId	An increasing per-sender integer, copied into the reply, that lets a client match replies to requests and a server spot duplicate requests.	VI
Resolution	Translating a name into data (attributes) about the named object, often in order to act on it.	IX
Resolver	Client name-resolution software, a library or a separate process, that carries out navigation for clients.	IX
Resource	Anything that can usefully be shared, hardware (printers, disks) or software (files, databases, objects).	I
Resource record	A typed DNS data item, such as A, AAAA, NS, CNAME, SOA, PTR, HINFO, MX or TXT.	IX
RMI	Remote method invocation: RPC extended to objects, where a method of a specific remote object is invoked and object references can be passed.	VI
RMIregistry	Java RMI's binder, running on each server host (default port 1099), mapping names like //host:port/name to remote object references.	VI
RPC	Remote procedure call: calling a procedure in a server process as if it were local, with marshalling, messaging and call semantics hidden.	VI
RRA protocol	Request-reply-acknowledge: the client acknowledges each reply with a cumulative Ack(requestId) so the server can delete history entries.	VI
RSA	A public-key algorithm whose security rests on the difficulty of factoring the product of two large primes.	X
Runnable (Java)	An interface with one method, run(), describing a task that a Thread object can execute.	IV
S
Scalability	The ability of a system to remain effective when the number of resources and users increases significantly.	I
Scheduler activation	An upcall from the kernel to a process's user-level scheduler reporting a scheduling event such as a virtual processor allocated, blocked, unblocked or preempted.	IV
Secure channel	A channel built with encryption and authentication that gives known principals, privacy and integrity, and timestamps against replay.	II
Secure digest (hash)	A one-way, collision-resistant function giving a short fixed-length fingerprint of a message.	X
Security mechanism	The technique that enforces a security policy, such as authentication or an ACL check.	X
Security policy	A statement of what is allowed: who may access which resources, independent of technology.	X
Servant	An instance of a class that provides the body of a remote object and handles the requests passed to it.	VI
Server	A running process that accepts requests from programs on other computers to perform a service, and responds to them.	I
Service	A distinct part of a system that manages related resources and presents their functionality only through a set of exported operations.	I
Session key	A fresh secret key created for one conversation and then discarded.	X
Skeleton	The server-side component (one per class) that unmarshals arguments, invokes the servant and marshals the result or exception.	VI
Socket	An endpoint of a two-way communication link between two programs, bound to a local port and IP address and using UDP or TCP.	III
Soft mount	An NFS mount in which an error is returned to the program after a few retries.	VIII
Space uncoupling	Indirect communication in which the sender need not know who the receivers are.	II, VII
Spanning tree	A subset of the links that connects every node but contains no cycle, so flooding over it reaches each node exactly once.	XI
Stateless server	A server that keeps no per-client state between requests, so it can restart after a crash with nothing to rebuild.	VIII
Supervisor (kernel) mode	The privileged processor mode in which the kernel runs, allowing privileged instructions and access to all memory and hardware.	V
Symmetric (secret-key) cryptography	Encryption where one shared key both encrypts and decrypts; fast, but the key is hard to distribute.	X
Synchronization uncoupling	Another name for asynchronous communication: send does not block; distinct from time uncoupling.	VII
Synchronous communication	Message passing in which both send and receive block, so the processes synchronise on every message.	III
Synchronous system	A system with known bounds on process step time, message delivery time and clock drift rate.	II
System call trap	An exception deliberately raised by a TRAP instruction that switches to supervisor mode and forces execution to a kernel-supplied handler.	V
System of systems	A complex system whose subsystems are systems in their own right, combined to perform a task (e.g. flood prediction).	II
System-call interface	The fixed set of operations a program can request from the OS, offering abstractions such as files and sockets instead of raw hardware.	V
T
TCP	Connection-oriented transport protocol giving a reliable, ordered, flow-controlled two-way byte stream with no message boundaries.	III
Template	A pattern of field values and types used by read and take to select a matching tuple.	VII
Thin client	A software layer giving a local window-based UI while the applications run on a remote compute server.	II
Thread	An activity within a process that owns only its stack, registers, priority and state, sharing everything else with its sibling threads.	IV
Thread-per-connection	Server design in which the main thread accepts connections and hands each client socket to its own new thread.	III, IV
Thread-per-object	A server architecture with one worker thread and one request queue per remote object.	IV
Thread-per-request	A server architecture in which a new worker thread is created for each request and destroyed after replying.	IV
Threat	A potential way a security policy could be violated; an attack is its actual execution.	X
Three-way handshake	TCP connection set-up: SYN, SYN-ACK, ACK, after which both ends hold connection state (a TCB).	III
Throughput	The number of requests a server processes per second.	IV
Ticket	An encrypted item from an authentication server holding a principal's identity and a session key, sealed with the target server's key.	X
Tiering	Placing an application's presentation, application and data logic onto appropriate servers; horizontal, unlike layering.	II
Time budget (3 minutes per mark)	180 minutes of writing divided by 60 marks, so a 5-mark question gets about 15 minutes and the 10-mark coding question about 30.	XI
Time uncoupling	Indirect communication in which sender and receiver need not exist at the same time.	II, VII
Timing failure	Exceeding a stated time bound (clock or performance); exists only in synchronous systems.	II
TLS	Transport Layer Security: a hybrid protocol giving secure channels over TCP via a record protocol and a handshake.	X
Topic-based subscription	Subscribing by an explicit, possibly hierarchical, topic field of the event, such as weather/melbourne.	VII
Total ordering	All members deliver all messages in the same order; implemented with a sequencer; implies neither FIFO nor causal.	VII
Transparency	Concealing from users and programmers the separation of components, so the system is perceived as a whole.	I
Transport address	The pair (IP address, port) that identifies a communication endpoint.	III
Trap-door function	A one-way function whose inverse is easy only for someone who knows a secret; the basis of public-key cryptography.	X
TTL (DNS)	Time-to-live: how long a cached DNS record may be served before it must be fetched again; it bounds staleness.	IX
Tuple space	A shared store of typed tuples that processes write, read (copy) or take (remove) by matching templates on content.	VII
Type-safe language	A language in which references cannot be forged, so a module can use another only through references it was given (e.g. Modula-3, Sing#).	V
U
UDP	Connectionless transport protocol sending independent datagrams (up to 64 KB) with no reliability, ordering or flow control.	III
UFID	Unique file identifier: a long bit sequence, unique among all files in the distributed system, created by Create.	VIII
UnicastRemoteObject	The Java class a servant usually extends; its constructor exports the object so it can receive remote calls.	VI
URI	Uniform Resource Identifier: one general syntax, with extensible schemes, for identifying any kind of resource.	IX
URL	Uniform Resource Locator: a URI holding the resource's location and access method; it dangles if the resource moves.	IX
URN	Uniform Resource Name: a URI used as a pure name (urn:nameSpace:specificName), which needs a resolution service.	IX
User mode	The unprivileged processor mode in which ordinary processes run, restricted to their own address space and barred from privileged instructions.	V
User-level threads	Threads scheduled by a library inside a process without the kernel's knowledge: cheap, but a blocking call blocks the whole process.	IV
V
V-node	The VFS record for an open file, referring to an i-node if local or to an NFS file handle if remote.	VIII
Validity	Reliability property: messages are delivered despite a reasonable number of dropped or lost packets.	III
Venus and Vice	The AFS client process (Venus) and server process (Vice).	VIII
Virtual file system (VFS)	The kernel layer that integrates local and remote file systems into one name space and routes each call, giving NFS access transparency.	VIII
W
wait / notify	Object methods for condition synchronisation: wait() releases the lock and blocks until notified; notify() or notifyAll() wakes waiting threads.	IV
Worked answer	An answer written for the study guide to a practice-exam question; staff released no official solutions, so it is one good answer, not the only one.	XI
Worker pool	A server architecture with a fixed set of worker threads, created at start-up, that take requests from a shared queue filled by an I/O thread.	IV
Write-invalidate	DSM protocol in which a write fault invalidates all other copies of the page before the writer maps it read-write.	VII
Write-through	Server caching policy that writes data to disk before replying, so the reply guarantees persistence.	VIII
X
X.509	The standard certificate format, part of X.500 and used in TLS.	X
Z
Zone	The unit of DNS data held by a server: a domain's names minus delegated subdomains, plus NS and glue records and SOA parameters.	IX
Zone transfer	A secondary DNS server downloading the whole zone from the primary server.	IX