Distributed System

Data-centric consistency models

Replication improves performance and availability but creates the problem of keeping copies consistent. A consistency model is a contract between the data store and the processes: if processes obey the rules, the store promises that the results of reads and writes will be as specified. A data-centric model describes the consistency view of the data store as a whole, as seen by all processes, regardless of which client issues the operation.

Types

1. Strict consistency: any read on a data item $x$ returns the value of the most recent write on $x$ in absolute global time. It is the strongest model but impossible to implement in a distributed system as it needs a global clock.
2. Linearizability: all operations appear in a single sequential order consistent with real-time timestamps from a global clock-like ordering.
3. Sequential consistency: the result of any execution is the same as if the operations of all processes were executed in some sequential order, and the operations of each process appear in the order specified by its program. All processes see the same interleaving.
4. Causal consistency: writes that are potentially causally related must be seen by all processes in the same order; concurrent writes may be seen in different order.
5. FIFO (PRAM) consistency: writes by a single process are seen by all others in the order issued, but writes by different processes may be seen in different orders.
6. Weak, release and entry consistency: use synchronization variables. Consistency is enforced only at synchronization points (acquire and release).
7. Eventual consistency: if no updates are made for a long time, all replicas gradually converge to the same value.

Data-centric consistency models specify the guarantees a replicated data store gives to all processes about the order in which reads and writes appear, independent of which client performs them. The main models are:

1. Strict consistency: a read of item $x$ returns the value of the most recent write, in absolute global time. It needs instantaneous propagation and a global clock, so it is not realisable in a distributed system.
2. Linearizability: operations appear to execute atomically in some sequential order that respects the real-time order of timestamps. It is stronger than sequential consistency.
3. Sequential consistency: the result is as if operations of all processes were executed in some single sequential order, with each process's operations in its program order. All processes see the same order, but it need not follow real time.
4. Causal consistency: writes that are causally related must be seen by all processes in the same order; concurrent writes can be seen in different orders by different processes.
5. FIFO (PRAM) consistency: writes of one process are seen in the order issued by that process; writes from different processes can be seen in different orders.
6. Weak consistency: consistency is enforced only after a synchronization operation.
7. Release consistency: uses acquire and release operations around critical sections; updates are propagated on release.
8. Entry consistency: each shared data item has its own synchronization variable, and consistency applies per item on acquire.
9. Eventual consistency: in the absence of updates, all replicas converge to the same value eventually.

The strongest models are the costliest in performance, so a model is chosen based on application needs.

Remote Procedure Call (RPC) is a communication mechanism in which a process on one machine (the client) calls a procedure that executes in another process, usually on another machine (the server), using the syntax of an ordinary local call. The programmer does not write any send/receive code; the network details are hidden, which gives access transparency.

RPC process (steps)

1. The client program calls the client stub as a normal local procedure.
2. The client stub marshals (packs) the procedure name and parameters into a message and passes it to the local operating system.
3. The client OS sends the message over the network to the server machine.
4. The server OS delivers the message to the server stub (skeleton).
5. The server stub unmarshals the parameters and calls the actual server procedure.
6. The server procedure executes and returns the result to the server stub.
7. The server stub marshals the result into a reply message and sends it back through the OS.
8. The client OS hands the reply to the client stub, which unmarshals it and returns the result to the caller, as if a local call had returned.

Parameter passing is by value (or copy-restore); pointers cannot be passed meaningfully because address spaces differ. Binding of client to server is done through a directory/name service, and failures (lost request or reply, server crash) are handled by timeouts and retransmission with at-least-once, at-most-once or exactly-once semantics.

A distributed system is a collection of autonomous computers that appears to its users as a single coherent system. Its main characteristics are:

1. Resource sharing: hardware (printers, storage), data and services can be shared by users across the network.
2. Openness: the system offers services through well-defined, published interfaces so that components can be added, replaced or extended and can interoperate.
3. Concurrency: many users and processes access shared resources at the same time, so synchronization is required to keep data consistent.
4. Scalability: the system keeps working effectively when the number of users, resources or geographic spread grows (size, geographical and administrative scalability).
5. Fault tolerance: a failure of one component does not bring down the whole system; this is achieved through redundancy, replication and recovery.
6. Transparency: the distribution is hidden from the user. Types include access, location, migration, relocation, replication, concurrency and failure transparency.
7. Heterogeneity: different hardware, operating systems, networks and programming languages work together, usually through middleware.
8. No global clock: each node has its own clock, so ordering of events needs logical clocks or clock synchronization.
9. Independent failures: components fail independently and partial failures are possible, which makes failure detection harder than in a single machine.
10. Security: since communication goes over a network, authentication, authorization and encryption are required.

Why clock synchronization is needed

Every computer in a distributed system has its own physical clock, and these clocks drift at slightly different rates (clock skew). Since there is no common global clock, synchronization is needed because:

• Events on different machines must be ordered correctly (for example, which transaction came first).
• Applications such as distributed databases, file timestamps (make), logging and debugging, and financial transactions depend on consistent time.
• Protocols such as mutual exclusion, replica consistency, authentication tokens (Kerberos ticket lifetimes) and event ordering need agreed time.

Network Time Protocol (NTP)

NTP synchronizes clients over the Internet to UTC using a hierarchy of servers organised in strata. Stratum 0 devices are atomic clocks or GPS receivers; stratum 1 servers are connected to them; stratum 2 servers sync with stratum 1, and so on.

A client sends a request to a server and records timestamps: $T_1$ (client sends), $T_2$ (server receives), $T_3$ (server replies), $T_4$ (client receives).

$\text{Offset } \theta = \frac{(T_2 - T_1) + (T_3 - T_4)}{2}$

$\text{Round-trip delay } \delta = (T_4 - T_1) - (T_3 - T_2)$

The client uses several servers, filters the offset estimates with the smallest delay, and adjusts its clock gradually (slewing) rather than setting it backwards, so time never runs backwards. NTP modes are multicast, procedure-call (client-server) and symmetric.

In a distributed system, an entity (a host, file, printer, user) is referred to by a name. Flat names are unstructured bit strings, whereas structured names are composed of several human-readable parts and are organised in a name space.

Name space

A name space is a labelled directed graph (usually a tree or DAG) with two node types:

• Leaf node: represents the named entity and stores its attributes or address.
• Directory node: has outgoing labelled edges to other nodes and stores a directory table of (edge label, node identifier) pairs.

An entity is identified by a path name, a sequence of edge labels, for example /home/steen/mbox or www.tu.edu.np. An absolute path name starts at the root node; a relative path name starts at the current working directory.

Aliases and mounting

• Hard link: a second path name leading to the same node.
• Symbolic link: a leaf node that stores a path name of another entity.
• Mounting: a directory node of one name space can refer to a node in a foreign name space, allowing different name spaces (for example NFS) to be merged.

Name resolution (closure mechanism)

Resolving a path name means following the edges from the starting node, looking up each label in the directory table until the entity is reached. The starting point (root) must be known, which is the closure mechanism. DNS is the classic example of a structured, hierarchical naming scheme.

Distributed systems are classified by their purpose into the following types.

1. Distributed computing systems

Used for high-performance computing.

• Cluster computing: a group of similar, tightly connected computers on a fast LAN, running the same OS and controlled by one master node (for example Beowulf clusters).
• Grid computing: a federation of heterogeneous resources from different administrative domains, combined to form a virtual organisation (for example SETI@home, scientific grids).
• Cloud computing may also be included, offering IaaS, PaaS and SaaS on demand.

2. Distributed information systems

Used to integrate networked applications.

• Transaction processing systems: support atomic, consistent, isolated and durable (ACID) transactions across servers, for example banking and airline reservation.
• Enterprise application integration (EAI): connects applications through RPC, RMI or message-oriented middleware.

3. Distributed pervasive (ubiquitous) systems

Small, mobile, battery-powered devices embedded in the environment, with unstable connections and context awareness.

• Ubiquitous computing systems such as smart homes.
• Mobile computing systems such as smartphones.
• Sensor networks that collect environmental data and process it in the network.

Process resilience means that a system continues to provide its service even when some processes fail. The main technique is process groups: several identical processes cooperate as one group, so if one member fails another can take over. A message sent to the group is delivered to all members, and the group appears as a single abstraction to the client.

Types of groups

• Flat group: all processes are equal and decisions are made collectively. There is no single point of failure, but decision making is more complex and slower.
• Hierarchical group: one process is the coordinator and the others are workers. It is simple and efficient, but the coordinator is a single point of failure and must be re-elected on failure.

Group membership is managed by a group server (centralised, with a single point of failure) or by distributed join and leave messages with failure detection.

Failure masking and k-fault tolerance

A group is k fault tolerant if it can survive faults in $k$ members and still work.

• With fail-silent (crash) failures, $k+1$ members are enough, since one correct member remains to give the answer.
• With Byzantine failures, members may send wrong or conflicting values, so $2k+1$ members are needed (and a majority vote is used); agreement requires $3k+1$ processes.

Replicating processes this way, together with agreement protocols and failure detection through heartbeat or ping messages, achieves resilience.

(a) Bully algorithm

The bully algorithm is an election algorithm that elects the alive process with the highest ID as coordinator. It assumes every process knows the IDs of all others.

1. When a process $P$ notices the coordinator has failed, it sends an ELECTION message to all processes with higher IDs.
2. If no one answers, $P$ wins, and sends a COORDINATOR message to all.
3. If a higher process replies with OK, $P$'s job is over; the higher process now holds its own election (it "bullies" the lower).
4. Eventually the highest alive process wins and announces itself. A recovered process with a higher ID than the current coordinator starts an election and takes over.

Worst case message cost is $O(n^2)$.

(b) Berkeley socket

The Berkeley socket interface is the standard API for transport-layer communication (TCP/UDP), introduced in BSD Unix. The primitives are:

• socket creates a communication end point.
• bind attaches a local address (IP and port) to the socket.
• listen makes the server ready to accept connections (sets queue length).
• accept blocks until a connection request arrives.
• connect actively establishes a connection (client).
• send/receive exchange data.
• close releases the connection.

Server order: socket, bind, listen, accept, read/write, close. Client order: socket, connect, write/read, close.

(c) Denial of Service (DoS)

A DoS attack makes a service unavailable to legitimate users by exhausting its resources (bandwidth, CPU, memory, connection tables). Examples are SYN flooding, ping flooding and request flooding. When launched from many compromised machines it is a Distributed DoS (DDoS). Countermeasures are firewalls and rate limiting, SYN cookies, intrusion detection, traffic filtering and over-provisioning with load balancers.

Virtualization

Virtualization is the technique of extending or replacing an existing interface (hardware or software) so that it mimics the behaviour of another system. It lets one physical machine run several isolated virtual machines (VMs), or lets programs written for one platform run on another. It is important in distributed systems because it gives isolation, portability, better hardware utilisation and easy migration of whole environments, which is the basis of cloud computing.

Types of virtualization

A computer offers four interfaces: hardware instructions (ISA), system calls, library calls (API) and privileged instructions. Virtualization is done at different levels.

1. Process virtual machine: a runtime system interprets or emulates a program's instructions at library or system-call level and runs it on a host. Example: the Java Virtual Machine runs bytecode on any OS; Wine runs Windows applications on Linux.
2. Native virtual machine monitor (hypervisor, type 1): a thin layer runs directly on hardware and provides a complete virtual hardware interface to guest operating systems. Examples: VMware ESXi, Xen, Hyper-V.
3. Hosted virtual machine monitor (type 2): the hypervisor runs as an application on a host OS and supports guest OSs. Examples: VirtualBox, VMware Workstation.
4. Container (OS-level) virtualization: one OS kernel is shared by isolated user-space instances. Example: Docker, LXC.

Role of middleware in a distributed system

Middleware is a software layer between the operating systems/applications and the network that gives a uniform programming model.

• It hides heterogeneity of hardware, OS and network, and provides distribution transparency.
• It supplies common services: communication (RPC, RMI, message queues), naming, security, transactions, replication and fault tolerance.
• It gives openness and interoperability through standard interfaces.
• It simplifies application development, since programmers use high-level abstractions rather than sockets.

Examples: CORBA, Java RMI, Microsoft .NET, message brokers.

The architecture of a distributed system describes how its components are organised and interact. The main architectural styles are:

1. Layered architecture

Components are organised in layers; a component at layer $L_i$ may call components at the layer below, and responses flow upward. Used in the network protocol stack and in the three-tier web application (presentation, application/logic, data). Advantages: separation of concerns and replaceability; the drawback is overhead across layers.

2. Object-based architecture

Each component is an object with an interface. Objects interact by remote method calls (RMI, CORBA) in a client-server style. It supports encapsulation and reuse, and suits modular applications.

3. Data-centred (shared data space) architecture

Processes communicate through a common repository, such as a shared file system, database or blackboard. Components are loosely coupled; examples are web-based shared data and distributed databases.

4. Event-based (publish-subscribe) architecture

Processes communicate by publishing and subscribing to events, usually through an event bus. They are decoupled in reference, since they need not know each other. Used in notification systems and Kafka-style brokers. Combined with shared data space, this is called a shared data event space.

5. Client-server (centralised) architecture

Servers offer services and clients request them over a network.

• Two-tier: client and server.
• Three-tier or multi-tier: client, application server and database server. It is simple to manage, but the server may become a bottleneck or single point of failure.

6. Peer-to-peer (decentralised) architecture

All nodes act as both clients and servers.

• Structured P2P: an overlay with a deterministic topology such as a DHT (Chord, Pastry).
• Unstructured P2P: random overlay, search by flooding or random walk (Gnutella).
• Hybrid P2P: supernodes or an index server plus peers (BitTorrent trackers). It is scalable and fault tolerant, but harder to secure and manage.

7. Hybrid architectures

Real systems combine styles, for example edge-server systems (CDN) and collaborative distributed systems.

Role of a coordinator

In many distributed algorithms one process must play a special role: the coordinator (leader). Its roles include:

• Acting as the central controller in mutual exclusion by granting access to a critical section.
• Acting as the transaction coordinator in distributed commit (2PC).
• Acting as the time server in Berkeley clock synchronization.
• Maintaining group membership, assigning work, and managing replicas (primary copy).
• Reducing complexity, since decisions are made in one place rather than by all.

As the coordinator may crash, a new one has to be chosen by an election algorithm. Every algorithm assumes each process has a unique ID, and that the process with the highest ID wins.

Approaches of election

1. Bully algorithm

Any process $P$ that detects coordinator failure sends ELECTION to all higher-numbered processes. If none responds, $P$ becomes coordinator and broadcasts COORDINATOR. If a higher process answers OK, it takes over the election. The highest-numbered alive process always wins ("bullies" the others). A restarted process with the highest ID starts an election and takes over.

2. Ring algorithm

Processes are arranged in a logical ring. A process noticing failure sends an ELECTION message containing its ID to its next alive successor. Each process adds its own ID and passes it on. When the message returns to the initiator, it holds the list of all alive IDs; the initiator picks the highest and circulates a COORDINATOR message so all know the new leader. Multiple simultaneous elections yield the same result.

3. Election in wireless and large-scale systems

In wireless ad hoc networks, a source node sends an election message through a spanning tree, and nodes report their best candidate (for example highest battery or resources) back up the tree. In large P2P systems, superpeers are elected so that they are well distributed and have enough resources.

Bully requires $O(n^2)$ messages in the worst case, and the ring algorithm requires about $2n$ messages.

Definition

A distributed system is a collection of independent (autonomous) computers, connected by a network and equipped with distributed-system software (middleware), that appears to its users as a single coherent system. Examples are the World Wide Web, online banking, and cloud services.

Characteristics

1. Resource sharing: hardware, data and services are shared across the network.
2. Concurrency: components execute in parallel and access shared resources simultaneously.
3. Scalability: the system can grow in users, resources and geographical size without loss of performance.
4. Openness: components use standard, published interfaces so that the system can be extended and is interoperable.
5. Transparency: the distribution of processes and resources is hidden (access, location, migration, replication, concurrency, failure).
6. Fault tolerance: the system keeps working despite failures of individual components, via replication and recovery.
7. Heterogeneity: different hardware, operating systems and networks cooperate through middleware.
8. No global clock: components coordinate only by passing messages, so event ordering needs logical clocks.
9. Independent (partial) failures: a part of the system can fail while the rest continues.
10. Security: authentication, authorisation and encryption are needed because communication is over a network.

The architecture of a distributed system describes how components are organised and how they communicate. The common architectural styles are:

1. Layered architecture: components are arranged in layers, where each layer uses services of the layer below and offers services to the layer above (for example presentation, application and data layers). It separates concerns and makes replacement easy.
2. Object-based architecture: components are objects with defined interfaces, which interact through remote method calls (RMI, CORBA), in a client-server style.
3. Data-centred architecture: processes communicate through a shared persistent repository, such as a shared database or file system or web-based data.
4. Event-based architecture (publish-subscribe): processes publish events and others subscribe to them; they are decoupled and need not know each other. Used in notification and messaging systems.
5. Client-server architecture: servers provide services and clients request them. It can be two-tier or multi-tier (client, application server, database server). It is easy to manage but the server can become a bottleneck.
6. Peer-to-peer architecture: every node acts as client and server. It can be structured (DHT, Chord), unstructured (Gnutella) or hybrid (BitTorrent with trackers). It is scalable and fault tolerant.
7. Hybrid architecture: combination of the above, for example edge-server systems and content delivery networks.

Attribute-based naming

In attribute-based naming, an entity is described by a collection of (attribute, value) pairs instead of a fixed, structured name. Users search for entities by giving the attributes they want, and the naming system returns all matching entities. It is also called directory service or descriptive naming. It is useful when the user does not know the exact name but knows the properties of the entity.

For example, a printer can be described as:

A query such as Type = Laser AND Location = Block B returns all printers matching it. Similarly, a person may be located by (Country = Nepal, Organisation = TU, Name = Ram).

Implementation

The most common implementation is LDAP (Lightweight Directory Access Protocol). Entries are stored in a Directory Information Base (DIB) and organised in a Directory Information Tree (DIT), where every entry has a relative distinguished name made of attributes, for example C=NP, O=TU, OU=CSIT, CN=Server. Searching a large directory is expensive, so the directory is partitioned and distributed across servers. Other examples are UDDI and the Active Directory.

Fault recovery is the process of bringing a failed system back to a correct state. The main methods are:

1. Backward recovery

The system is rolled back to a previously saved correct state (a checkpoint) and execution restarts from there.

• Checkpointing: the state of each process is saved periodically to stable storage. In a distributed system, a distributed snapshot gives a consistent recovery line. Checkpointing may be independent (processes checkpoint on their own, risking the domino effect of cascaded rollbacks) or coordinated (all processes checkpoint together, giving a consistent state with no domino effect).
• Message logging: the system takes a checkpoint and logs the messages received after it. After a crash, the process restarts from the checkpoint and replays the logged messages (sender-based, receiver-based, pessimistic or optimistic logging).

2. Forward recovery

The system moves to a new correct state without going back, by correcting the detected error. It uses error-correcting codes or specific knowledge of the errors, and so it is application specific. It is useful in real-time and replication-based systems, where redundancy hides the failure.

3. Recovery via replication (masking)

A failed component is replaced by a replica using a standby or primary-backup scheme, so recovery is almost immediate.

Backward recovery is general and widely used, but is costly (checkpoint overhead, lost work); forward recovery is cheaper at runtime but requires prior knowledge of possible errors.

(The question uses "threads" to mean security threats.)

Security threats

A threat is a potential violation of security. The four basic types are:

1. Interception: an unauthorised party gains access to data or services, for example eavesdropping on messages or illegally copying files.
2. Interruption: services or data become unavailable, unusable or destroyed, for example deleting a file or a denial of service.
3. Modification: an unauthorised party changes data or tampers with a service, for example altering a transmitted message or a database record.
4. Fabrication: generation of additional data or activity that would not normally exist, for example adding a record to a password file or replaying/injecting forged messages.

Common attacks

• Eavesdropping / sniffing: passive listening to network traffic (breaks confidentiality).
• Masquerading (spoofing): pretending to be another user or server.
• Man-in-the-middle: an attacker sits between two parties and reads or alters their messages.
• Replay attack: a captured valid message is resent to gain access.
• Denial of Service (DoS/DDoS): flooding a server with requests to make it unavailable.
• Malware, Trojans, viruses and worms: malicious code that damages or steals data.
• Password cracking and brute force.

Countermeasures are encryption, authentication, authorisation (access control), digital signatures, firewalls and auditing.

(a) Access control

Access control ensures that only authorised subjects (users, processes) can perform permitted operations on objects (files, services), after they have been authenticated. It is implemented by a reference monitor that checks each request.

• Access control matrix: rows are subjects, columns are objects, and each cell holds the rights (read, write, execute). It is huge and sparse so it is stored in either of two ways.
  • Access control lists (ACL): a list attached to each object, giving the subjects and their rights (used in Unix and Windows files).
  • Capabilities: a list attached to each subject, a protected token that gives rights to an object.
• Other models are role-based access control (RBAC), where rights belong to roles, and firewalls, which control access at the network level.

(b) Secure naming

Secure naming makes sure that a name resolves to the genuine entity and that name information has not been tampered with or forged. Threats include spoofing, such as DNS cache poisoning, where a false address is given for a name, causing users to connect to an attacker.

Security measures include:

• DNSSEC: DNS records are digitally signed by the zone's private key, and clients verify them with a chain of trust of public keys, giving authenticity and integrity.
• Self-certifying names: the name contains a hash of the owner's public key, so the name itself can be verified without a trusted third party.
• Authenticating name servers and protecting the name space with access control on updates.

Virtualization

Virtualization is the creation of a virtual (rather than physical) version of a resource, by extending or replacing an interface so that it imitates another system. A software layer (the hypervisor or virtual machine monitor) lets multiple isolated environments share one physical machine. Benefits are better resource utilisation, isolation, portability, easy migration and lower cost; it is the basis of cloud computing.

Types of virtualization

1. Hardware (full or system) virtualization: a hypervisor creates virtual machines, each running its own guest OS.
   • Type 1 (bare-metal) runs directly on the hardware, for example VMware ESXi, Xen, Hyper-V.
   • Type 2 (hosted) runs on a host OS, for example Oracle VirtualBox, VMware Workstation. Example: running Ubuntu and Windows side by side on a single laptop.
2. Process (application) virtualization: a runtime environment runs programs independent of the platform. Example: the Java Virtual Machine executes Java bytecode on any OS.
3. Operating-system-level (container) virtualization: several isolated user-space instances share one OS kernel. Example: Docker containers on Linux.
4. Emulation / compatibility layer: a program built for one system runs on another, for example Wine runs Windows applications on Linux, and Android emulators run on a PC.
5. Storage virtualization: physical storage devices are pooled to appear as one logical storage unit, for example a SAN or RAID.
6. Network virtualization: virtual networks over physical infrastructure, for example VLANs and VPNs.

Remote Procedure Call (RPC)

RPC is a communication mechanism in which a client calls a procedure that runs on a remote server with the same syntax as a local procedure call. The programmer does not handle sockets or message formats; the network details are hidden by stubs.

Operation

1. The client calls the client stub as a local procedure.
2. The client stub marshals the parameters into a message and asks the local OS to send it.
3. The message is transmitted over the network to the server machine.
4. The server OS passes it to the server stub, which unmarshals the parameters.
5. The server stub calls the actual procedure on the server.
6. The procedure runs and returns its result to the server stub.
7. The server stub marshals the result into a reply message and sends it back.
8. The client stub receives and unmarshals the reply, and returns the result to the client program.

Binding to the server is done via a name/directory service, and parameter passing is by value. Failure semantics are at least once, at most once or exactly once.

Advantages

• Simple, familiar procedure-call programming model, giving access transparency.
• Hides network communication and data representation (marshalling) differences between machines.
• Makes writing distributed applications easier and faster, and encourages modular design.
• Supports heterogeneous machines using an Interface Definition Language (IDL) with stub generation.
• Allows use of remote resources and processing power.

Disadvantages

• Slower than local calls, because of network delay and marshalling overhead.
• Partial failures (lost message, crashed server or client) make semantics complex; failure transparency is hard.
• Passing pointers and global variables is not possible since address spaces differ.
• Synchronous by default, the client blocks while waiting for the reply.
• Not very flexible; tight coupling between client and server, and the programmer must handle security and versioning.

Physical clock

A physical clock is a hardware clock (quartz crystal oscillator) that counts real time in seconds. Each computer has its own, and different clocks drift apart (clock skew). Time is standardised as UTC, and clocks must be synchronised with it. Physical clock synchronization is needed when the actual time of day matters.

Logical clock

A logical clock does not measure real time; it gives a consistent ordering of events based on the happened-before relation ($a \rightarrow b$). Lamport's logical clock gives each process a counter $C_i$ that is incremented before every event, and attaches it to messages; on receiving a message with timestamp $t$, the receiver sets $C_j = \max(C_j, t) + 1$. This guarantees that if $a \rightarrow b$ then $C(a) < C(b)$. Vector clocks additionally capture causality fully.

Network Time Protocol (NTP)

NTP synchronises clients with UTC using a hierarchy of time servers in strata (stratum 0 is the atomic clock or GPS). The client exchanges a request and response with the server and records $T_1$ (client send), $T_2$ (server receive), $T_3$ (server send), $T_4$ (client receive).

$\theta = \frac{(T_2 - T_1) + (T_3 - T_4)}{2}, \qquad \delta = (T_4 - T_1) - (T_3 - T_2)$

Here $\theta$ is the estimated offset and $\delta$ is the round-trip delay. The client picks the server samples with the lowest delay and adjusts the clock gradually, never setting time backwards.

Berkeley algorithm

This is an internal synchronization method used when no machine has an accurate UTC source. A time daemon (master) periodically polls all machines for their time, estimating the round trip, computes the average of all clock values (including its own, ignoring those that differ too much), and sends each machine the amount by which to adjust its clock (not the absolute time, to avoid message delay effects).

Example: master 3:00, A at 2:50, B at 3:25. Average $= (3{:}00 + 2{:}50 + 3{:}25)/3 = 3{:}05$. Adjustments: master $+5$ min, A $+15$ min, B $-20$ min.

Middleware

Middleware is a software layer placed between the operating system (and network) and the distributed applications. It hides the heterogeneity of hardware, operating systems and networks, and provides a uniform programming model with common services such as communication (RPC, RMI, message queues), naming, security, transactions and replication. It gives distribution transparency and openness. Examples are CORBA, Java RMI, and message brokers.

Architecture styles of distributed systems

1. Layered architecture: components are in layers, each using the layer below (for example presentation, application, data tiers).
2. Object-based architecture: components are objects that interact by remote method invocation in client-server style.
3. Data-centred architecture: processes communicate by a common shared repository such as a database or shared file system.
4. Event-based (publish-subscribe) architecture: processes publish and subscribe to events; they are decoupled and unaware of each other.
5. Client-server architecture: clients request services from servers; two-tier or multi-tier.
6. Peer-to-peer architecture: equal nodes act as both clients and servers; structured (DHT), unstructured or hybrid overlays.
7. Hybrid architecture: a combination of the above, for example edge-server systems and CDNs.

A server may or may not remember information about its clients between requests.

Stateless servers are preferred for simplicity and robustness, with state kept at the client (cookies) when needed.

The Berkeley algorithm is an internal clock synchronization algorithm for systems where no machine has access to an accurate UTC source. The goal is for all machines to agree on a common time, which need not be the real time. The server is active and polls the clients.

Steps

1. A time daemon (master) polls every machine, asking for its current time.
2. Each machine replies with its clock value. The master estimates the round-trip time and corrects each value for it.
3. The master computes the average of all clocks (including its own), ignoring values that deviate too far from the others.
4. The master tells each machine how much to adjust its clock (a positive or negative offset), not the absolute time, so that the transmission delay does not affect the result. A clock that is ahead is slowed down rather than set back.

Diagram (text)

 (a) Poll                (b) Reply                (c) Adjust
 Master 3:00  --"time?"-->  A: 2:50 (-10)         Master: +5
      |-----"time?"-->      B: 3:25 (+25)         A: +15
                            Master: 3:00 (0)      B: -20

Example

Master = 3:00, A = 2:50, B = 3:25. Differences relative to master: $0, -10, +25$.

$\text{Average} = \frac{0 - 10 + 25}{3} = +5 \text{ min}$

New agreed time $= 3{:}05$. Adjustments: master $+5$, A $+15$, B $-20$. If the master crashes, another machine is elected as master.

Distributed commit

Distributed commit is the problem of ensuring that an operation (usually a transaction) is performed by all processes in a group or by none of them (atomicity). A coordinator and several participants must agree on commit or abort. Typical protocols are one-phase commit, two-phase commit (2PC) and three-phase commit (3PC).

Two-phase commit (2PC)

Let the coordinator be $C$ and the participants be $P_1 \ldots P_n$.

Phase 1: voting (prepare)

1. $C$ writes prepare in its log and sends VOTE-REQUEST to all participants.
2. Each participant replies VOTE-COMMIT (if it is ready to commit; it logs the state and holds its locks) or VOTE-ABORT.

Phase 2: decision (commit) 3. $C$ collects the votes. If all voted commit, $C$ logs commit and sends GLOBAL-COMMIT; if any voted abort or timed out, it sends GLOBAL-ABORT. 4. Each participant commits or aborts according to the message, and replies ACK.

Diagram (text)

Coordinator                    Participants
  VOTE-REQUEST  ------------->   (all)
                <-------------   VOTE-COMMIT / VOTE-ABORT
  GLOBAL-COMMIT / ABORT ------>   (all)
                <-------------   ACK

State view: Coordinator: INIT, WAIT, COMMIT/ABORT. Participant: INIT, READY, COMMIT/ABORT.

Failures: if a participant in READY state times out, it asks other participants; if all are READY it must block until the coordinator recovers. This blocking is the main weakness of 2PC, and it is removed by three-phase commit.

Security management in a distributed system covers the mechanisms that keep the system's resources safe from unauthorised access, tampering and disclosure, even though components run on different machines and communicate over insecure networks. It has three main parts: key management, authorization management and secure group management.

1. Key management

Cryptography needs keys, and keys must be created, distributed, stored and replaced safely.

• Key establishment: a shared secret key can be set up with the Diffie-Hellman exchange. Both parties pick private values $a$ and $b$, exchange $g^a \bmod p$ and $g^b \bmod p$, and each computes the same key $g^{ab} \bmod p$.
• Key distribution: a trusted Key Distribution Center (KDC), as in Kerberos, hands out session keys. For public keys, a Certification Authority (CA) signs certificates that bind a public key to an identity.
• Key lifetime: session keys are short-lived. Long-term keys are replaced or revoked when compromised (for example through certificate revocation lists).

2. Authorization management

After authentication, the system must decide what each principal may do.

• Capabilities: an unforgeable token held by a process that grants specific rights on an object. They are protected by cryptographic signatures.
• Attribute certificates: a signed statement of the rights or roles of a user, separate from the identity certificate, so rights can be delegated without changing identity.
• Delegation: a user passes a subset of their rights to another process (for example a proxy or a job running on their behalf), usually through restricted, signed proxies with an expiry time.
• Access control: implemented using access control lists or capability lists, enforced by a reference monitor at each server.

3. Secure group management

Replicated servers and groups must communicate securely.

• Membership changes need new group keys so that a departed member cannot read later messages.
• Group keys can be shared secrets, or a public/private key pair for the group.
• Members must be authenticated before being admitted and secure multicast must be supported.

Overall goals: authentication, confidentiality, integrity, availability and non-repudiation, achieved by combining secure channels (TLS/IPSec), access control and good key handling.

(a) Sequential consistency

Sequential consistency is a data-centric consistency model defined by Lamport. A data store is sequentially consistent if the result of any execution is the same as if the read and write operations of all processes were executed in some single sequential order, and the operations of each individual process appear in this sequence in the order specified by its program.

• All processes see the same interleaving of operations; time does not matter, only the order.
• Example: P1 does W(x)a; P2 does W(x)b; P3 reads R(x)b then R(x)a; P4 reads R(x)b then R(x)a. This is valid because both readers see $b$ then $a$. If P3 saw $b,a$ and P4 saw $a,b$, it would violate sequential consistency.
• It is weaker than strict consistency (no global clock needed) but stronger than causal consistency. It is simple for programmers but costly to implement because every replica must agree on a global order.

(b) Access control matrix

An access control matrix is a model for protection in which rows represent subjects (users, processes, domains) and columns represent objects (files, devices, services). Each cell $M[s,o]$ lists the rights subject $s$ has on object $o$.

• Because the matrix is large and sparse, it is stored by columns as Access Control Lists (ACLs) (each object keeps a list of subjects and their rights) or by rows as capability lists (each subject holds the rights it has).
• A reference monitor checks each request against the matrix before allowing it.

(c) Message Passing Interface (MPI)

MPI is a standard library specification for message-passing communication in parallel and distributed applications, mostly used in high-performance computing on clusters.

• Processes are grouped into communicators, and each process has a rank.
• Point-to-point operations: MPI_Send, MPI_Recv (blocking) and MPI_Isend, MPI_Irecv (non-blocking).
• Collective operations: MPI_Bcast, MPI_Scatter, MPI_Gather, MPI_Reduce, MPI_Barrier.
• It supports both synchronous and asynchronous transient communication, and runs over TCP or high-speed interconnects. It is portable, efficient and supports C, C++ and Fortran.

Definition

A distributed system is a collection of independent computers (nodes) that appears to its users as a single coherent system. The nodes are connected by a network, have no shared memory or shared clock, and coordinate their actions only by passing messages. Examples are the World Wide Web, cloud platforms, online banking and distributed databases.

Characteristics

1. Resource sharing: hardware, software and data (printers, files, databases) can be used by many users over the network.
2. Concurrency: many components execute at the same time and may access shared resources.
3. Openness: the system is extensible through published, standard interfaces and protocols.
4. Scalability: it can grow in size (users, resources), geography and administration without a loss of performance.
5. Fault tolerance: failure of a component does not stop the whole system; this is obtained through replication and recovery.
6. Transparency: details such as location, replication, failure and concurrency are hidden from the user.
7. Heterogeneity: different hardware, operating systems, networks and languages work together, usually through middleware.
8. No global clock and independent failures: each node has its own clock and can fail independently.

Types of distributed systems

1. Distributed computing systems
   • Cluster computing: a group of similar, tightly connected machines on a LAN working as one high-performance computer, controlled by a single master node.
   • Grid computing: loosely coupled, heterogeneous resources from different organisations pooled together across wide areas for large computations.
   • Cloud computing: resources (infrastructure, platform, software) provided as an on-demand, pay-per-use service over the Internet.
2. Distributed information systems: integrate many networked applications and databases. Examples are transaction processing systems (banking) and enterprise application integration (EAI) using middleware.
3. Distributed pervasive (ubiquitous) systems: small, mobile, embedded devices that are part of the environment, such as home systems, electronic health care systems and sensor networks.

Election algorithm

Many distributed algorithms need one process to act as coordinator (for example, a mutual exclusion coordinator or time server). An election algorithm is a procedure to choose a single process as coordinator from a group of processes, usually the one with the highest identifier, and to make all processes agree on it. It is run at start-up or when the current coordinator fails. Each process is assumed to have a unique number and to know the numbers of the others.

1. Bully algorithm

When a process $P$ notices that the coordinator is not responding, it starts an election:

1. $P$ sends an ELECTION message to all processes with a higher number.
2. If no one responds, $P$ wins and sends a COORDINATOR message to all.
3. If a higher process responds with OK, $P$'s job is over and that process takes over the election.
4. The process with the highest number eventually wins; it "bullies" the others. A recovered process with a higher number starts a new election and takes over.

P1 P2 P3 P4 P5 P6 P7(crashed)
P4 detects failure
P4 --ELECTION--> P5, P6, P7
P5 --OK--> P4 ; P6 --OK--> P4   (P7 silent)
P5 --ELECTION--> P6, P7 ; P6 --ELECTION--> P7
P6 --OK--> P5
P6 gets no answer from P7 -> P6 wins
P6 --COORDINATOR--> P1..P5

2. Ring algorithm

The processes are arranged in a logical ring and each knows its successor.

1. A process that notices the failure builds an ELECTION message containing its own number and sends it to its successor, skipping crashed processes.
2. Each process receiving the message adds its own number and forwards it.
3. When the message returns to the initiator, it contains the numbers of all live processes. The initiator picks the highest number as coordinator.
4. It then circulates a COORDINATOR message around the ring to inform everyone, and the message is removed once it has gone round once.

   P1 -> P2 -> P3
   ^            |
   |            v
   P6 <- P5 <- P4
Message: [P3] -> [P3,P4] -> [P3,P4,P5] -> ... -> back to P3
Coordinator = highest in list

Comparison: Bully needs up to $O(n^2)$ messages in the worst case; the ring algorithm needs about $2n$ messages. Bully assumes reliable communication and known identifiers, while the ring algorithm works with a logical structure only.

Remote Procedure Call (RPC)

RPC lets a program call a procedure that runs on another machine as if it were a local procedure call. The programmer does not write any network code; the communication details are hidden by stubs. RPC provides access transparency and builds on the client-server model.

Working process

The client has a client stub and the server has a server stub. The steps are:

1. The client calls the client stub as an ordinary local procedure.
2. The client stub marshals (packs) the parameters into a message and calls the local OS to send it.
3. The client OS sends the message to the server machine.
4. The server OS passes the message to the server stub.
5. The server stub unmarshals the parameters and calls the actual server procedure.
6. The server procedure executes and returns the result to the server stub.
7. The server stub marshals the result into a message and hands it to the server OS.
8. The result message is sent back to the client OS, which gives it to the client stub.
9. The client stub unmarshals the result and returns it to the client.

 Client machine                         Server machine
+--------------+                      +----------------+
| Client       |                      | Server         |
|  call f(x)   |                      |  f(x) executes |
|     |   ^    |                      |     ^    |     |
|     v   |    |                      |     |    v     |
| Client stub  |                      | Server stub    |
|  (marshal)   |                      |  (unmarshal)   |
|     |   ^    |                      |     ^    |     |
|  Client OS --+---- request msg ---->+- Server OS     |
|     ^        |<--- reply msg -------+-- |            |
+--------------+                      +----------------+

Issues handled: parameter passing (call by value, representation differences solved by a standard format such as XDR), binding of client to server, and failure semantics (at-least-once, at-most-once).

Message-oriented communication

Where RPC is synchronous and requires the receiver to be running, message-oriented communication lets processes exchange messages without blocking, often through queues. It can be:

• Transient: the message is kept only while the sender and receiver are running (for example sockets, MPI).
• Persistent: the middleware stores the message until it is delivered, even if the receiver is not running. This is done by Message Queuing Systems (MQS).

In a message-queuing system, applications use put (append a message to a queue), get (block until a message is available), poll (check without blocking) and notify (install a handler). Queues are managed by queue managers.

Example: an online shop places an order message in the queue of the billing service. The order service continues without waiting. The billing service, even if down for some time, later reads the message and processes it. Products such as IBM MQ, RabbitMQ and Apache Kafka work this way.

Need for a distributed operating system

A distributed operating system (DOS) manages a collection of independent computers and makes them appear to users as a single computer. It is needed because:

• Resource sharing: processors, memory, files and devices on many machines can be used as one pool.
• Performance: a job can be split and run in parallel on several machines (load balancing), giving speed-up.
• Reliability and availability: if one machine fails, others can take over, because functions are replicated.
• Transparency: users do not need to know where files or processes are; the OS handles location, migration and replication.
• Scalability and economy: capacity can be increased by adding nodes, which is cheaper than a mainframe.
• Communication: it supports easy communication and collaboration among users at different places.

Network OS vs distributed OS

Virtualization creates a virtual version of a resource (hardware, OS, storage or network) on top of a real one, so that many isolated virtual machines (VMs) can share one physical machine. It contributes to distributed systems in several ways:

1. Portability and heterogeneity: an application plus its environment can be packaged as a VM image or container and run unchanged on any host, hiding differences in hardware and OS. This helps in code migration and in making diverse nodes look uniform.
2. Resource sharing and utilisation: one powerful server hosts many VMs, so CPU, memory and storage are used better. This is the basis of cloud computing (IaaS).
3. Isolation and security: each VM is isolated, so failure or compromise of one does not affect others, and untrusted code can be run safely.
4. Scalability and elasticity: new VMs can be started on demand and removed when not needed; load can be balanced by moving VMs between hosts (live migration).
5. Fault tolerance and recovery: VMs can be snapshotted, replicated and restarted on another host after a crash.
6. Cost reduction and easy management: fewer physical machines, simpler deployment, testing and backup.
7. Legacy support: old software can run on a VM emulating the required old platform.

The cost is some performance overhead from the virtualization layer (hypervisor).

Mutual exclusion

Mutual exclusion ensures that, when several processes need a shared resource (or a critical section), only one process uses it at a time. In a distributed system there is no shared memory, so semaphores and locks cannot be used directly; algorithms based on message passing are needed. A good algorithm guarantees safety (at most one process in the critical section), liveness (no deadlock or starvation) and fairness (requests served in order).

Methods

1. Centralized algorithm: one process is elected coordinator. A process sends a REQUEST to the coordinator; if the resource is free it replies GRANT, otherwise the request is queued. After use, the process sends RELEASE and the coordinator grants the next in the queue. It needs 3 messages per entry and is simple, but the coordinator is a single point of failure and a bottleneck.

2. Distributed algorithm (Ricart-Agrawala): a process wanting entry multicasts a REQUEST with its Lamport timestamp to all other processes. A receiver replies OK immediately if it is not interested, or if the requester's timestamp is lower; otherwise it defers the reply. The process enters when it has OK from all $n-1$ others. It needs $2(n-1)$ messages per entry and fails if any process crashes.

3. Token ring algorithm: processes form a logical ring and a token circulates. Only the holder of the token may enter the critical section; after use (or if not needed) it passes the token to its neighbour. It guarantees no starvation, but a lost token has to be detected and regenerated, and a crashed process breaks the ring.

Code migration

Code migration is the movement of programs (and sometimes their execution state) from one machine to another in a distributed system. It is done to improve performance (move computation to where the data is, or to a less loaded machine), to reduce network traffic, and for flexibility (clients download code on demand, as with Java applets and JavaScript).

A process has three segments: the code segment (the program instructions), the resource segment (references to external resources such as files and devices) and the execution segment (the current state: data, stack, program counter).

Migration models

1. Weak mobility: only the code segment (plus perhaps some initialization data) is transferred. The program always starts from its beginning at the destination. It is simple and portable, for example Java applets or scripts sent to a browser.
2. Strong mobility: the code and the execution segment are moved, so the process is stopped, moved and resumed from the point where it was stopped. It is more powerful but harder to implement.

Both can be initiated in two ways:

• Sender-initiated: the machine that holds the code starts the migration (for example uploading a program to a compute server, or sending a search program to a database).
• Receiver-initiated: the destination starts it (for example a client downloading an applet).

Also, the process can run in the target process (code is executed by the already running process, as in a browser) or a separate new process is created. A migration where the process is moved (not copied) is called process migration; strong mobility combined with a clone is called remote cloning. The resource segment may be bound by identifier, by value or by type, and this affects whether resources are moved, copied or re-bound.

Name, address and identifier

• Name: a string of bits or characters used to refer to an entity (a host, file, user, service), for example www.example.com or /home/user/a.txt. It can be human-friendly or machine-readable.
• Address: the name of an access point, the place where an entity can be accessed. For example, an IP address and port number identify the access point of a server. An entity may have several addresses and its address can change if it moves.
• Identifier: a name that uniquely identifies one entity, with these properties: it refers to at most one entity, each entity is referred to by at most one identifier, and it always refers to the same entity (never reused). Identifiers are usually location independent, for example a MAC address, a national ID number or a UUID.

Types of communication in a distributed system

Communication can be classified by persistence, synchronization and the form of data.

1. Persistent communication: the middleware stores the message until it is delivered; sender and receiver need not be running at the same time (e-mail, message queues).
2. Transient communication: the message is stored only while sender and receiver are executing; if delivery is impossible it is discarded (sockets, TCP/UDP).
3. Asynchronous communication: the sender continues immediately after sending the message.
4. Synchronous communication: the sender blocks until the message is received (or processed) by the receiver.
5. Remote Procedure Call (RPC): a call to a procedure on another machine appears local; it is synchronous and request-reply based.
6. Message-oriented communication: explicit send/receive of messages through sockets, MPI or message queues.
7. Stream-oriented communication: continuous media (audio, video) with timing constraints, where the relation between successive data units is important.
8. Multicast communication: a message is sent to a group of receivers, for example by application-level multicasting or gossip-based data dissemination.

Transparency means hiding the fact that the system is made of separate, distributed components so it looks like a single computer. The main forms of distribution transparency are:

Full transparency is often impossible or too costly (network latency cannot be hidden, and failure of a remote server cannot always be distinguished from slowness), so designers balance transparency against performance.

(a) Public key cryptography

Public key (asymmetric) cryptography uses a pair of mathematically related keys: a public key $K^{+}$, which is published, and a private key $K^{-}$, kept secret by the owner. What one key encrypts, only the other can decrypt.

• Confidentiality: the sender encrypts a message with the receiver's public key; only the receiver's private key can decrypt it: $C = E_{K_B^+}(M)$, $M = D_{K_B^-}(C)$.
• Authentication and digital signature: the sender signs with their own private key; anyone can verify with the public key.
• Examples: RSA (based on the difficulty of factoring a product of two large primes $n = pq$) and ElGamal/ECC.
• It removes the need to share a secret key beforehand, but is much slower than symmetric cryptography (such as AES), so in practice it is used to exchange a symmetric session key. Public keys are bound to identities by certificates issued by a CA.

(b) Security management

Security management deals with the practical administration of security in a distributed system. It has three parts:

• Key management: key establishment (Diffie-Hellman), distribution through a KDC or CA certificates, and key lifetime and revocation.
• Authorization management: capabilities, attribute certificates and delegation of access rights.
• Secure group management: admitting members, authenticating them and changing the group key when membership changes.

It makes sure that authentication, confidentiality, integrity and access control policies are applied consistently across all the nodes.

(c) RPC

Remote Procedure Call allows a client to call a procedure located on a remote server as if it were local. The client stub marshals the parameters into a message, the message is sent over the network to the server stub, which unmarshals it and invokes the real procedure. The result goes back the same way. RPC hides message passing and gives access transparency, but it is usually synchronous and the failure semantics (at-most-once, at-least-once) are more complex than for local calls. Examples: Sun RPC, gRPC, Java RMI.

Clock synchronization

Clock synchronization is the process of making the clocks of the different computers in a distributed system show the same (or nearly the same) time. Every computer has its own hardware clock (a quartz crystal), and the clocks drift apart because the oscillators run at slightly different rates.

Why it is needed

• Many applications depend on the order of events: for example in make, a source file edited at a later time must be recompiled, which fails if the machines disagree about times.
• Distributed databases and transactions need timestamps for ordering updates and for concurrency control.
• Mutual exclusion, deadlock detection and replicated data consistency need a common notion of ordering.
• Logging, auditing, security (Kerberos tickets), billing and real-time or banking systems need accurate time.
• There is no global clock, so it must be approximated.

If a clock has a maximum drift rate $\rho$, two clocks can differ by at most $2\rho\,\Delta t$ after time $\Delta t$. To keep them within $\delta$, they must be resynchronized at least every $\delta/(2\rho)$ seconds.

Physical clock synchronization algorithms

1. Cristian's algorithm (external, time server): A client $P$ requests the time from a time server $S$ with a UTC receiver.

• The client sends a request at its local time $T_0$; the server replies with its time $T_S$; the reply arrives at $T_1$.
• Round trip $= T_1 - T_0$, and assuming symmetric delay, the client sets its clock to $T_{new} = T_S + \frac{T_1 - T_0}{2}$
• Example: $T_0 = 10{:}00{:}00.000$, $T_1 = 10{:}00{:}00.100$, $T_S = 10{:}00{:}00.040$. Then $T_{new} = 40 + 50 = 90$ ms past 10:00:00, so the clock is set to 10:00:00.090.
• A clock must never run backwards; if it is ahead, it is slowed down gradually. A more accurate estimate can be made by averaging several rounds and discarding those with large delay.

2. Berkeley algorithm (internal, no UTC): A time daemon (master) polls all machines for their time, computes the average (ignoring clearly faulty values) and then tells each machine by how much to adjust its clock.

• Example: master at 3:00, A at 2:50, B at 3:25. Average $= (0 - 10 + 25)/3 = +5$ min, so the agreed time is 3:05. The master adjusts by +5, A by +15, B by $-20$.
• Sending the offset instead of the time avoids message delay errors.

3. Network Time Protocol (NTP): a hierarchy of time servers (strata) with stratum 0 as atomic/GPS clocks. Clients exchange timestamps with servers and estimate offset $\theta = \frac{(T_2 - T_1) + (T_3 - T_4)}{2}$ and delay $\delta = (T_4 - T_1) - (T_3 - T_2)$, giving accuracy of a few milliseconds over the Internet.

4. Averaging algorithms: decentralised: each machine broadcasts its time at fixed intervals, collects the others' values for a period and takes the average.

Types of failures

1. Crash failure: a server halts, but works correctly until it halts (fail-stop if it can be detected).
2. Omission failure: a server fails to respond to requests (receive omission) or fails to send replies (send omission).
3. Timing (performance) failure: the response comes outside the specified time interval, which matters in real-time systems.
4. Response failure: the server responds incorrectly, either with a wrong value (value failure) or by changing to a wrong state (state-transition failure).
5. Arbitrary (Byzantine) failure: the server may produce any response at any time, including malicious or contradictory ones. Failures can also be transient, intermittent or permanent.

Recovery from a crash

Recovery means returning the system to a correct state after the failure.

• Backward recovery: the system is rolled back to a previously saved consistent state (a checkpoint) and execution continues from there. Checkpoints are saved to stable storage; in a distributed system a consistent distributed snapshot (recovery line) is needed to avoid the domino effect. Message logging (log messages since the last checkpoint and replay them) reduces the lost work.
• Forward recovery: the system moves to a new correct state by correcting the erroneous state, using error-correcting codes or redundancy, without going back.
• Backward recovery is more general and is used more in practice, but it costs overhead and cannot undo some actions (for example sending cash).

One-phase commit

In a one-phase commit protocol, a coordinator tells all participants to commit (or abort) and keeps retrying until all acknowledge. The weakness: the coordinator does not know whether each participant is actually able to commit (for example, due to a constraint violation or a crash), so some may commit and others cannot, which breaks atomicity.

Two-phase commit (2PC)

It guarantees that all participants commit or all abort. There is a coordinator and the participants.

Phase 1: voting (prepare)

1. The coordinator writes begin-commit to its log and sends VOTE_REQUEST to all participants.
2. Each participant, if ready, writes its updates and ready to its log and replies VOTE_COMMIT; otherwise it replies VOTE_ABORT.

Phase 2: decision 3. If all participants vote commit, the coordinator logs commit and sends GLOBAL_COMMIT to all; if any vote abort (or there is a timeout), it logs abort and sends GLOBAL_ABORT. 4. Each participant carries out the decision, logs it and sends ACK.

Coordinator          Participants
 VOTE_REQUEST  --->
               <---  VOTE_COMMIT / VOTE_ABORT
 GLOBAL_COMMIT/ABORT --->
               <---  ACK

Failure handling: a participant waiting in the ready state for the decision that times out can ask other participants; if all are in ready, it must block until the coordinator recovers. This is the blocking problem of 2PC, which is addressed by three-phase commit. Recovering processes use their logs to decide: a participant that crashed before voting aborts; if in ready state, it asks the coordinator or other participants.

Replication

Replication is the keeping of copies of data or services at several machines. It is used for reliability (when one copy fails another is used, and corrupted copies can be detected) and performance (clients access a nearby copy and load is shared). The main problem is consistency: when one copy is updated, the others must be updated too.

Data-centric consistency models

These models describe what a data store guarantees to all processes about the order of reads and writes on shared data.

1. Strict consistency: any read on $x$ returns the value of the most recent write on $x$ in absolute global time. It is impossible to implement in a distributed system.
2. Linearizability: operations appear in some sequential order that is consistent with real-time order using timestamps from synchronized clocks.
3. Sequential consistency: the result is as if all operations were executed in some single sequential order, with each process's operations in program order; time is not important. Example: P1: W(x)a; P2: W(x)b; both readers see b then a. Valid. If readers see different orders, not valid.
4. Causal consistency: writes that are potentially causally related must be seen by all in the same order; concurrent writes may be seen in different orders. Example: P1 writes x=a; P2 reads x=a, then writes x=b. Since b depends on a, all processes must see a before b.
5. FIFO (PRAM) consistency: writes by a single process are seen in the order issued; writes from different processes may be seen in different orders.
6. Weak, release and entry consistency: use synchronization variables. Data is made consistent only when a synchronization operation (acquire, release) is done, which reduces the overhead for programs that update many values in a critical section.

Name resolution algorithms

Name resolution is the process of looking up a name to find the entity (or its address) it refers to, by following the name space graph.

1. Iterative resolution: the client sends the full name to the root name server, which returns the address of the next name server for the remaining part; the client then contacts that server, and so on, until the final address is found. The client does most of the work. It is simpler for servers and caching is done mainly at the client.
2. Recursive resolution: the client asks the first name server, which itself contacts the next server and so on, and finally returns the complete result to the client. It puts a higher demand on each server but allows effective caching in the servers and reduces the communication cost for the client.

Iterative:  client -> root -> client -> NS(.np) -> client -> NS(edu.np) -> address
Recursive:  client -> root -> NS(.np) -> NS(edu.np) -> address returned back along the chain

A distributed system is made of many autonomous computers, but it is built so that users and applications see it as one single, coherent system. The statement is justified by the following features, which are balanced by its challenges.

Features that create the single-system view

• Distribution transparency: access, location, migration, replication, concurrency and failure are hidden, so the user does not know where data lives or on which node a task runs.
• Resource sharing: files, printers, databases and computing power from many machines are accessed through uniform interfaces.
• Middleware: a layer between applications and the OS gives a uniform programming interface over heterogeneous machines.
• Openness and scalability: components interoperate through standard interfaces and the system can be extended without the user noticing.
• Fault tolerance: replication and recovery keep the service running, so the user sees continuous availability.
• Examples: Google Search or online banking appear as one service although thousands of servers are involved.

Challenges

• Heterogeneity: different hardware, OS, networks and languages must be made to work together.
• Transparency vs performance: hiding latency and failures completely is not possible.
• Scalability: the system must handle more users and bigger distances, avoiding central bottlenecks.
• Concurrency and consistency: keeping replicated data consistent while many users update it.
• Failure handling: partial failures occur, and a slow server cannot be distinguished from a dead one.
• Security: open networks expose data to attacks; authentication, authorization and encryption are needed.
• No global clock and no shared memory: ordering events and agreeing on global state is hard.

Overcoming these challenges is what keeps up the illusion of a single coherent system.

Communication can be classified by whether messages are stored (persistent or transient) and by how the sender and receiver synchronize. In transient synchronous communication, a message is kept by the communication system only while the sender and receiver are both running, and the sender is blocked until some acknowledgement is received. There are three points at which the sender can unblock:

1. Synchronization at request submission: the sender blocks only until the middleware (local OS) has accepted the message for transmission. It does not know whether the message has arrived.
2. Synchronization at request delivery: the sender blocks until the message has been delivered to the receiving machine (received by the receiver's middleware). The receiver may not yet have processed it. This is the common form in message passing.
3. Response-based synchronization: the sender blocks until the receiver has accepted and processed the request and returned a reply. This is the form used in RPC and RMI, and is the strongest form.

Sender         Network / Receiver
  | send request
  |---------------------------->  (a) unblock after request accepted by local middleware
  |                      deliver
  |<------ ack ---------------    (b) unblock after delivery at receiver machine
  |                      process
  |<------ reply -------------    (c) unblock after receiver processed request

Characteristics: the sender and receiver must both be active at the same time; the receiver is usually waiting for the message; the sender is blocked during the communication, which wastes time and fails if the receiver is down. Examples are sockets with blocking send, and RPC. Its advantage is simple semantics and tight coupling; the disadvantage is poor tolerance to failure and delay.

Interceptor

An interceptor is a software construct that breaks the usual flow of control and allows other (application-specific) code to be executed. It is used to adapt middleware to the needs of an application without changing the application itself or the middleware.

• Example: in remote object invocation, a request-level interceptor captures a call A.do(B). If object $B$ is replicated, the interceptor can transparently send the call to every replica; the application is unaware of it.
• A message-level interceptor works at the level of messages, for example to fragment a large message into parts.
• Interceptors are placed at the client side in the proxy or stub, or at the server; they are used for logging, load balancing, monitoring, encryption, caching and replication.
• Their strength is making a system adaptable and non-intrusive; they are usually implemented in a way that depends on the middleware (for example CORBA portable interceptors, Java servlet filters).

Wrapper (adapter)

A wrapper is a component that offers an interface acceptable to a client application, and whose functions are transformed into those available at the component being wrapped. It solves the problem of incompatible interfaces when integrating legacy or third-party components in a distributed system.

• The client sees only the wrapper's interface; the wrapper converts calls and data into the form required by the existing system (for example a CORBA wrapper around a legacy COBOL application, or a proxy that exposes a web service over a database).
• With $N$ applications, direct integration needs up to $N(N-1)$ translators; with a broker and wrappers only $2N$ wrappers are needed, because each application is wrapped once to the broker's common interface.
• Wrappers enable integration of existing applications (EAI) without changing them, but they add overhead.

Difference: a wrapper changes an interface to make components compatible; an interceptor intercepts the control flow to add behaviour.

Distributed commit

Distributed commit is the problem of making an operation performed by every member of a process group either happen at all of them or at none of them (atomicity). It is used in distributed transactions, where several databases have to commit one transaction together. A coordinator drives the protocol and the other processes are participants.

Two-phase commit (2PC)

Phase 1: voting

• The coordinator writes begin-commit in its log and sends VOTE_REQUEST to all participants.
• Each participant replies VOTE_COMMIT if it can commit (after writing its changes and ready to a log), or VOTE_ABORT if it cannot.

Phase 2: decision

• If every participant voted commit, the coordinator records commit and sends GLOBAL_COMMIT to all. If at least one voted abort, or a vote timed out, it sends GLOBAL_ABORT.
• Participants carry out the decision, record it in their logs and acknowledge.

Coordinator:  INIT -> WAIT -> COMMIT / ABORT
Participant:  INIT -> READY -> COMMIT / ABORT

Failures: a participant in INIT that times out waiting for a VOTE_REQUEST can safely abort. The coordinator in WAIT that times out aborts. A participant in READY that times out cannot decide alone: it asks other participants (if any is in COMMIT/ABORT it follows; if all are READY it blocks until the coordinator recovers). Logs are used for recovery.

Three-phase commit (3PC)

To remove blocking, a PRECOMMIT state is added between READY and COMMIT. The coordinator sends PREPARE_COMMIT after all vote commit and global commit only after all acknowledge. This ensures no participant is in a state from which both commit and abort are possible, so after a timeout the survivors can decide. It needs more messages and is rarely used in practice.

Attacks on distributed systems and their mitigation

General measures: a layered defence combining cryptography, authentication, access control, firewalls and intrusion detection, key management, replication for availability, regular updates, and security policy and user training.

(a) DNS query types

The Domain Name System translates domain names into IP addresses. A resolver uses these query types:

• Recursive query: the client asks a DNS server to return the final answer or an error. The server contacts other servers as needed on the client's behalf. It is normally used between a host and its local resolver.
• Iterative query: the server returns the best answer it has, which may be a referral to another name server; the client then queries that server itself, until it reaches the authoritative server. It is used between name servers.
• Non-recursive (cached) query: the server answers from its cache or its own authoritative data without contacting other servers.
• Inverse query / reverse lookup: finds the domain name for a given IP address (PTR records). Record types asked include A, AAAA, MX, NS, CNAME and PTR.

(b) Checkpointing

Checkpointing is a recovery technique in which the state of a process or the whole distributed system is periodically saved to stable storage, so that after a failure the system can be rolled back to the saved state (backward error recovery).

• In a distributed system, the set of checkpoints of all processes must form a consistent global state (a recovery line): no message recorded as received that is not recorded as sent.
• Independent checkpointing: each process checkpoints on its own; this is simple but may cause the domino effect, where rollback cascades to the initial state.
• Coordinated checkpointing: processes synchronize (using a two-phase protocol) to take a consistent snapshot together, avoiding the domino effect at a cost of coordination delay.
• Message logging is combined with checkpoints to reduce the amount of work to redo.

(c) Digital signature

A digital signature is an electronic equivalent of a handwritten signature that proves the origin and integrity of a message and provides non-repudiation.

• Signing: the sender computes a hash (digest) $h = H(M)$ of the message and encrypts it with their private key: $S = E_{K_A^-}(h)$. The message and $S$ are sent.
• Verification: the receiver decrypts $S$ with the sender's public key to get $h$, computes the hash of the received message, and checks that both are equal.
• If they match, the message is authentic (only the owner of the private key could have produced $S$) and unaltered. Examples: RSA-based and DSA signatures, used in certificates, software signing and secure e-mail.

Logical clock

In a distributed system there is no global physical clock, and for many problems only the order of events matters, not the absolute time. A logical clock is a counter-based mechanism that assigns a number to each event so that events can be ordered consistently with the happens-before relation, without relating to real time.

Happens-before relation ($\rightarrow$) (Lamport)

1. If $a$ and $b$ are events in the same process and $a$ occurs before $b$, then $a \rightarrow b$.
2. If $a$ is the sending of a message and $b$ is the receipt of the same message, then $a \rightarrow b$.
3. It is transitive: if $a \rightarrow b$ and $b \rightarrow c$ then $a \rightarrow c$. Events with neither $a \rightarrow b$ nor $b \rightarrow a$ are concurrent.

Lamport's logical clock

Each process $P_i$ keeps a counter $C_i$, initially 0. The rules are:

1. Internal event: before each event, $P_i$ increments its clock: $C_i = C_i + 1$.
2. Sending: $P_i$ increments $C_i$, and sends the message with timestamp $t = C_i$.
3. Receiving: on receiving a message with timestamp $t$, $P_j$ sets $C_j = \max(C_j, t) + 1$ and then delivers the message.

This guarantees the clock condition: if $a \rightarrow b$ then $C(a) < C(b)$. The reverse is not true: $C(a) < C(b)$ does not mean $a \rightarrow b$.

Example

P1:  a(1) ---send m1(2)---------------- e(6)
                    \                    ^
P2:        b(1) ---- c(3,recv m1) --- d(4,send m2)
                                         \
P3:                  f(1) ----------------- g(5,recv m2)

Let $P_1$ have event $a$ ($C=1$) then send $m_1$ ($C=2$). $P_2$ has clock 1 at its own event $b$; on receiving $m_1$ with $t=2$: $C = \max(1,2)+1 = 3$. $P_2$ then sends $m_2$ at $C=4$. $P_3$ is at 1, and on receiving $m_2$: $C = \max(1,4)+1 = 5$.

Total ordering: ties between equal timestamps are broken by process number: $(C_i, i) < (C_j, j)$ if $C_i < C_j$, or $C_i = C_j$ and $i < j$. This is used in totally ordered multicast, replicated databases and distributed mutual exclusion (Ricart-Agrawala).

Limitation: Lamport clocks cannot detect concurrency; vector clocks solve this by keeping a vector of counters, one per process.

Replication as a scaling technique

When many clients access one server, the server becomes a bottleneck and a scalability problem arises. Scaling techniques are: hiding communication latencies, distribution (partitioning data and computation) and replication.

Replication makes copies of a resource (data, service) available on several machines, which supports scaling because:

• Requests are spread across many replicas, so load is balanced and the load on a single server falls.
• Copies can be placed close to clients (caching, CDNs), reducing latency and wide-area traffic.
• It improves availability and reliability, as the system works when a replica fails.
• Caching is a special case where the copy is decided by the client. The price is consistency: an update must reach all copies, and keeping them synchronized costs bandwidth and may itself limit scalability, so weaker consistency is often accepted.

Consistency (replica management) protocols

These protocols implement a consistency model by deciding how updates are propagated to the replicas.

1. Primary-based protocols: each data item has a primary server responsible for coordinating writes.

• Remote-write protocol (primary-backup): all writes go to the single fixed primary. The primary updates its copy, forwards the update to the backups, waits for acknowledgements, then replies to the client. Reads can be local. Gives sequential consistency, with a blocking write.

Client --write--> Primary --update--> Backup1
                     |      --update--> Backup2
Client <--ack--  Primary <--acks--------

• Local-write protocol: the primary role moves to the process wanting to write (the item is migrated to it), so successive writes by one process are local. Useful for mobile computing and offline work.

2. Replicated-write protocols: writes can be carried out at multiple replicas.

• Active replication: each replica has a process that performs the update; operations must be applied in the same order everywhere, which needs totally ordered multicast (for example Lamport timestamps) or a sequencer.
• Quorum-based protocols: a read must collect a read quorum $N_R$ and a write a write quorum $N_W$ of the $N$ replicas, with $N_R + N_W > N$ (so read and write sets overlap) and $N_W > N/2$ (so two writes conflict). Example: $N=12$, $N_R=3$, $N_W=10$ is valid; reading from 3 replicas always includes one holding the latest version, identified by version number.

Quorum: N = 5, N_W = 3, N_R = 3  ->  3 + 3 > 5, 3 > 2.5

3. Client-centric protocols (for eventual consistency): ensure each client sees consistent data when it moves between replicas (monotonic reads, monotonic writes, read-your-writes, writes-follow-reads).

Update propagation can be by state or by operations, push-based (server-initiated) or pull-based (client-initiated), and by unicast or multicast.

Virtualization

Virtualization is the technique of extending or replacing an existing interface to mimic the behaviour of another system, so that a single physical resource appears as multiple logical ones. A software layer (the hypervisor or virtual machine monitor) creates isolated virtual machines that each behave as a separate computer, sharing the underlying hardware. It improves hardware use, isolation, portability and flexibility, and is a basis of cloud computing.

Types of virtualization

1. Hardware (server) virtualization: a hypervisor divides a physical server into multiple VMs, each with its own OS.
   • Type 1 (bare-metal) hypervisor runs directly on hardware, for example VMware ESXi, Xen, Hyper-V.
   • Type 2 (hosted) hypervisor runs on a host OS, for example VirtualBox, VMware Workstation.
2. Operating-system-level virtualization (containers): the kernel is shared, and isolated user-space instances run as containers, for example Docker and LXC. They are lightweight and start quickly.
3. Process virtual machine / application virtualization: a runtime gives programs a platform-independent environment, for example the Java Virtual Machine, .NET CLR.
4. Storage virtualization: physical storage devices are pooled and presented as one logical storage, for example SAN, RAID, LVM.
5. Network virtualization: physical network resources are combined into virtual networks, for example VLAN, VPN, software-defined networking.
6. Desktop virtualization: a user's desktop runs on a central server and is accessed remotely, for example VDI, Citrix.
7. Memory and data virtualization: virtual memory, distributed shared memory, or an abstract data access layer.

Middleware in a distributed system

Middleware is a software layer placed between the applications and the operating systems/network of the individual nodes. It hides heterogeneity and provides a uniform programming model so that the distributed system appears as one system.

+------------------------------------------+
|  Application A | Application B | App C   |
+------------------------------------------+
|              MIDDLEWARE                  |
| (RPC/RMI, messaging, naming, security,   |
|  transactions, replication)              |
+--------------+---------------+-----------+
|  OS + HW     |   OS + HW     | OS + HW   |
|   Node 1     |    Node 2     |  Node 3   |
+--------------+---------------+-----------+
        Network

Functions of middleware:

• Communication: RPC, remote method invocation, message queues, publish-subscribe.
• Naming and directory services to locate resources.
• Transparency: hides location, access, replication and failure.
• Security: authentication, authorization and secure channels.
• Transaction and concurrency control and distributed commit.
• Replication, fault tolerance and persistence.
• Interoperability: provides common interfaces and data formats for different platforms. Examples: CORBA, Java RMI, DCOM, web services, Apache Kafka.

The World Wide Web is a large-scale distributed system organised on the client-server model: clients request resources and servers hold and deliver them.

Components

• Client (web browser): The user gives a URL; the browser resolves the host name through DNS, opens a TCP (or TLS) connection, sends an HTTP request, then parses and renders the HTML, CSS, images and scripts it receives.
• Web server: A process such as Apache or Nginx that listens on port 80/443, maps the URL to a static file or hands it to an application server (PHP, Java, Node.js) that may query a database, and returns an HTTP response with a status code and content.
• Protocol: HTTP is a request-reply protocol. It is stateless, so each request is independent; cookies, sessions and tokens add state on top.
• Naming and addressing: URLs identify resources and DNS maps host names to IP addresses.

Working

1. Browser sends GET /index.html HTTP/1.1 to the server.
2. Server processes it and replies 200 OK with the page (or 404, 500, etc.).
3. The browser makes further requests for embedded resources.

As a distributed system

• Servers are spread across the world, yet users see one uniform space of documents (access and location transparency).
• Scalability is achieved by replication, load balancers, caching in browsers and proxies, and Content Delivery Networks.
• Multi-tier design (browser, web server, application server, database) separates concerns and improves fault tolerance.
• Weakness: a single server is a bottleneck and single point of failure unless replicated.

Remote Procedure Call (RPC) is middleware that lets a program call a procedure located on another machine as if it were a local call, hiding sockets, message formats and network details.

How it works

1. The client calls a local procedure, the client stub, with ordinary parameters.
2. The stub marshals (packs) the parameters into a message and asks the local OS to send it.
3. The client's OS transmits the message to the server machine.
4. The server OS passes it to the server stub (skeleton), which unmarshals the parameters.
5. The server stub calls the actual procedure on the server.
6. The result is marshalled and sent back, the client stub unmarshals it, and the original call returns the result to the caller.

The stubs are generated from an interface definition (IDL). Marshalling also handles differences such as byte order and data representation. Binding finds the server through a name or directory service.

Example

A client calls sum = add(5, 3). The client stub builds a message {procedure: add, args: 5, 3}, sends it to the server, the server stub calls the real add(5, 3), gets 8, and returns it. The client code sees only a normal function call that yielded 8.

Issues: failures (lost request or reply, server crash) need timeouts and retries with at-least-once or at-most-once semantics; parameters passed by reference are difficult because address spaces differ.

A unique identifier (UID or ID) is a name that refers to exactly one entity (a process, file, object, lock, connection) and is never reused for another entity. It is location-independent, so it keeps its meaning wherever the entity moves.

Uses in resource management when processes share resources

• Unambiguous reference: Processes on different machines name the same file, printer or database record by the same ID, so they cannot confuse two different resources.
• Access control and ownership: Resource tables record which process ID holds which resource, so permissions can be checked and capabilities issued against identifiers.
• Locking and mutual exclusion: A lock is recorded with the ID of its holder. Only that holder can release it, and a lock held by a crashed process can be detected and reclaimed.
• Ordering and duplicate detection: Request IDs (with timestamps or sequence numbers) let servers recognise retransmitted requests, preventing a request being executed twice.
• Location and migration: A resource can move or be replicated; a name service maps its ID to the current address, so clients do not break.
• Tracking and cleanup: Using IDs, the system can trace resource usage per process, detect deadlocks and release resources when a process terminates.

Generating IDs without central coordination: use large random numbers, UUIDs, or combinations such as node address plus local counter plus timestamp, so collisions are practically impossible.

The Global Name Service (GNS), developed at DEC, is a name service designed for very large, widely distributed systems. It keeps a hierarchical name space and maps names to attributes such as addresses.

Architecture

• Directory tree: Names form a hierarchy such as /org/dept/user. Each node is a directory with a unique directory identifier (DI); a full name is a path of directory names ending in a value tree of attributes.
• Directories are replicated: Each directory is stored on several name servers. One is the primary copy; updates are applied and propagated to the others, so reads can be served by any replica. Consistency is eventual, using timestamped updates and a sweep to reconcile replicas.
• Root and mounting: The root is high up and replicated widely. When organisations merge, trees can be combined by adding a new root above the old ones, using the unique DIs so existing names remain valid.
• Clients: A client library asks a local server; the server resolves the name, navigating via a cache of directory locations to the servers holding the target directory.
• Caching: Results are cached, with updates being rare so caching works well.

Role in a distributed system

• Provides location transparency: names are decoupled from network addresses.
• Supports scalability with replication and hierarchy.
• Gives fault tolerance and good availability, since any replica can answer.
• Allows evolution of the name space, because of the way trees are restructured without invalidating old names.

Gossip-based coordination is a decentralised way of spreading information: each node periodically picks one or a few random peers and exchanges its state with them, so information spreads through the whole system like an epidemic or rumour, without a central coordinator.

Main features

• Each round a node selects a random peer and pushes its updates, pulls the peer's updates, or does both (push-pull).
• The number of informed nodes grows roughly exponentially, so an update reaches all $N$ nodes in about $O(\log N)$ rounds.
• It is scalable, robust to node failure and message loss, and needs no global knowledge or fixed topology.

Use in distributed event matching (publish-subscribe)

• In content-based publish-subscribe, events must be matched against subscriptions held on many nodes. Central matching would be a bottleneck.
• Gossiping lets nodes exchange subscription information and build or repair a partial view of who is interested in what, and forward events along random or semantic neighbours.
• Subscriptions and events spread probabilistically, so brokers need not know the whole network; churn (nodes joining and leaving) is handled automatically.
• Result: good scalability and fault tolerance, with the trade-off that delivery is probabilistic and may involve some redundant messages and delay.

Process resilience is the ability of a distributed system to continue providing its service correctly even when some processes fail. The aim is to mask process failures from the clients.

Methods used to achieve it

1. Process groups (replication): Several identical processes form a group and a message sent to the group is received by all members. If one member fails, the others continue. Groups may be:
   • Flat groups: all members equal, decisions collective, no single point of failure but more complex voting.
   • Hierarchical groups: a coordinator makes decisions and workers execute them; simple but the coordinator is a single point of failure.
2. Redundancy and masking: A k-fault-tolerant group tolerates $k$ failures. With crash (fail-silent) failures, $k+1$ members suffice. With arbitrary (Byzantine) failures, $2k+1$ members are needed (with majority voting), and agreement needs $3k+1$.
3. Agreement protocols: Consensus (e.g. Paxos, Raft, Byzantine agreement) lets non-faulty members agree on a value or order despite failures.
4. Failure detection: Heartbeats and timeouts detect failed members, and membership is updated by group membership services.
5. Checkpointing and recovery: Process state is saved periodically and on failure the process is restarted from the last checkpoint, with message logging to replay messages.
6. Reliable communication: Retransmission, acknowledgements and atomic multicast ensure all members see the same messages in the same order.

A security policy states what actions each subject may perform on each resource. Enforcing it across a large-scale distributed system is difficult for the following reasons.

• Scale and heterogeneity: Thousands of nodes of different hardware, operating systems and middleware must apply one policy consistently; each may have different security mechanisms.
• No central control and multiple administrative domains: Organisations with different policies and trust levels must interoperate, so agreeing on and translating policies is hard.
• Trust and authentication: Users, services and machines must authenticate each other across domains, often without prior relationship. Key distribution and certificate management (PKI, revocation) at large scale is costly.
• Policy consistency and propagation: Updates to policy or revoked rights must reach all replicas promptly; delays leave windows of vulnerability.
• Insecure network: Messages can be intercepted, modified or replayed, so encryption and integrity checks are needed, adding performance overhead and latency.
• Partial failure and attacks: Compromised nodes, denial of service, and insider threats cannot be fully excluded; one weak node may expose the whole system.
• Performance versus security: Checking access rights, encrypting and auditing on every request reduces throughput and scalability.
• Complexity and usability: Fine-grained policies, delegation, and mobile code or users joining and leaving make policies hard to specify, verify and audit; mistakes lead to loopholes.
• Privacy and legal rules: Data spread across countries is subject to different regulations.

(a) Distributed file system

A distributed file system (DFS) allows files stored on several networked machines to be accessed and shared as though they were in one local file system. Clients use the same file operations, while the system handles location, replication and consistency. Examples: NFS, AFS, Google File System, HDFS.

(b) Forms of transparency

• Access transparency: Local and remote resources are accessed with identical operations; differences in data representation are hidden.
• Location transparency: Users cannot tell where a resource is physically located; names do not contain location.
• Migration transparency: A resource can move to another place without changing how it is accessed.
• Relocation transparency: A resource can be moved even while it is in use.
• Replication transparency: Multiple copies exist but users see one resource.
• Concurrency transparency: Many users share a resource without interfering with each other.
• Failure transparency: Faults and recovery are hidden from users.
• Persistence transparency: Whether a resource is in memory or on disk is hidden.

(c) Design issues of a distributed system

• Transparency: Achieving the above degrees without too much cost.
• Scalability: The system should handle growth in users, resources and geography, avoiding centralised services and using caching, replication and partitioning.
• Openness: Standard interfaces and protocols allow interoperability and extension.
• Fault tolerance and reliability: Detect, mask and recover from failures using replication and redundancy.
• Concurrency and consistency: Synchronising access and keeping replicas consistent.
• Security: Authentication, authorisation, encryption over an untrusted network.
• Performance: Communication delay, bandwidth and load balancing.
• Heterogeneity: Different hardware, OS, languages and networks need middleware.
• Naming and resource management: Locating and allocating resources, and time synchronisation.

Virtualization in distributed systems is the creation of a virtual (abstract) version of a resource, such as a machine, operating system, storage or network, that is mapped onto the physical resources underneath. It lets many isolated environments share the same hardware, helps resource sharing, portability and management, and is the basis of cloud computing.

Hardware virtualization

A hypervisor (VMM) emulates complete hardware, and each virtual machine (VM) runs its own guest OS. A Type 1 hypervisor (Xen, VMware ESXi, KVM) runs directly on hardware; a Type 2 runs on a host OS (VirtualBox).

OS-level virtualization

The host kernel is shared and it creates multiple isolated user-space instances (containers) using namespaces and cgroups (Docker, LXC). There are no guest kernels.

Comparison

Use cases

• Hardware virtualization: server consolidation, running different operating systems, strong multi-tenant isolation in public clouds (IaaS), legacy applications, disaster recovery by VM migration.
• OS-level virtualization: microservices, DevOps and CI/CD, PaaS, quickly scaling web applications, dense hosting of many identical services.

In practice they are combined: containers running inside VMs give both isolation and efficiency.

In a replicated banking system, each account is stored on several replicas, and a customer may use a phone, laptop and ATM, each possibly served by a different replica.

Sequential consistency

The result of any execution is the same as if all operations of all processes were executed in some single sequential order, with each process's operations in its program order. All replicas apply the writes in that same order, but the order need not match real time.

Effects on the customer:

• All devices see deposits and withdrawals in the same global order, so the balance never goes "backwards" or shows an overdraft because two replicas applied operations in different orders.
• Example: balance Rs 1,000; the customer deposits Rs 500 from the phone and then withdraws Rs 800 from the ATM. Every replica applies them in one agreed order, so all converge to Rs 700.
• A device may, however, read a stale value for a while: the ATM could still show Rs 1,000 after the phone's deposit, as the order is guaranteed but not the recency. Operations may be delayed, so it is slower (coordination cost, e.g. total order broadcast).

Read-your-writes consistency (client-centric)

A client's read always reflects the writes the same client has made earlier, even if it reads from a different replica.

Effects on the customer:

• After depositing Rs 500 on the phone, the customer's next balance check (even on the laptop connected to another replica) shows the deposit, so there is no confusion and no repeated transactions.
• It is implemented by session guarantees: the client carries a version or timestamp of its last write, and a replica serves the read only if it has caught up, otherwise it fetches the missing updates or redirects.
• It says nothing about other customers' writes or about a global order. Two joint-account holders could see different orders of their transactions, unless stronger consistency is also used.

Summary

Sequential consistency gives a single order of all transactions, which is important for correct balances and for concurrent updates, at a cost in latency. Read-your-writes gives the customer a coherent personal view across devices cheaply, but does not prevent conflicts between concurrent updates. Banks typically use strong consistency for transfers and withdrawals and weaker session guarantees for read-only views.