Security, Fault Tolerance, Clocks, and Consensus in Distributed Systems
Fundamentals of Distributed Systems and Fault Tolerance
In a distributed environment, system components consist of independent nodes communicating across unreliable, heterogeneous networks. These systems are continuously exposed to emergent risks, including network cuts, service crashes, unbounded latencies, message interception, and resource exhaustion. As the scale of nodes and operations grows, the probability of at least one component failing approaches certainty.
Lamport's Axiom summarizes this reality:
"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."
To build resilient systems, a strict taxonomy is used to differentiate between the origin, internal manifestation, and user-visible outcome of system anomalies.
Foundational Taxonomy and the Causal Chain
- Fault: The underlying cause, defect, or hardware flaw within a system component (e.g., disk crash, network cut, RAM bit flip, memory leak).
- Error: An internal incorrect system state resulting directly from a fault (e.g., corrupted memory contents, invalid variable state).
- Failure: The event where the system fails to deliver its specified service to the user or external client according to its specification (e.g., total application outage, timeout).
The system progression follows a strict causal chain:
The objective of fault tolerance is to prevent internal errors from escalating into user-visible failures.

Detailed Cause-and-Effect Layers
- Physical Layer (Cause - Hardware Fault): A hardware defect introduces a fault, such as a DRAM bit flip caused by cosmic radiation, hardware wear, or electrical noise, causing hardware to return incorrect data.
- Data Layer (Error - System Memory Corruption): An incorrect bit is written to system memory, corrupting data structures or variable states.
- Application Layer (Fault Propagation): The application reads the corrupted data, causing an invalid internal state or logic error, leading to unexpected behavior.
- Runtime Layer (Failure Trigger - Unhandled Exception): The fault triggers an unhandled exception in the runtime, causing the application to terminate or thread to crash.
- Business Impact (Failure - Service Unavailable): The service stops responding to requests, health check probes fail, and end-users experience system downtime.
System Models and Failure Classification
System models define theoretical frameworks that specify explicit assumptions regarding processes, communication links, and timing characteristics.
Network Link Models
- Fair-Loss Links: Messages may be lost or duplicated, but if a sender continuously retransmits a message, it will eventually arrive at the destination.
- Reliable Links: Messages are delivered exactly once in order, without loss or duplication (typically instantiated via protocols like TCP over Fair-Loss links).
- Authenticated Reliable Links: Reliable links extended with cryptographic identity verification, allowing the receiver to confirm the sender's identity (e.g., TLS over TCP).
Process Failure Models
- Crash-Stop: A process executes correctly according to its algorithm until it fails by crashing, after which it halts indefinitely and never recovers.
- Crash-Recovery: A process can crash at any point, lose its volatile memory state, and restart later using persistent storage.
- Arbitrary-Fault (Byzantine): A process can deviate arbitrarily from its specification due to software bugs, memory corruption, or malicious compromise.
Operational Failure Modes
- Omission Faults: Occur when a server or network link fails to perform an action it was mandated to execute.
- Send Omission: A process fails to output a message to the network.
- Receive Omission: A message is dropped in transit or fails to enter the receiving process's kernel buffer.
- Timing Failures: Occur when a response or computation arrives outside the expected temporal window.
- Implication: In an asynchronous network model where transmission delays are unbounded, a slow process is completely indistinguishable from a crashed process.
- Response Failures: Occur when a server returns an incorrect execution output or invalid value.
- Value Failure: The calculated output falls outside allowable physical/logical bounds or fails syntactical correctness checks.
The Byzantine Failure Model and Consensus
In the Byzantine failure model, faulty nodes can exhibit arbitrary, contradictory, or malicious behavior. Examples of Byzantine behavior include:
- Sending contradictory messages to different peer nodes.
- Forging or altering transaction payloads in transit.
- Refusing to execute mandated operational logic.
- Behaving correctly to a subset of nodes while lying to others.
This model is critical in safety-critical systems (e.g., flight control systems, nuclear reactor monitoring) and open, untrusted peer-to-peer networks (e.g., blockchain, multi-agent systems).
Theoretical Bounds for Byzantine Consensus
In a fully connected, synchronous network containing Byzantine faulty processes, reaching consensus requires a total process count satisfying:
where:
- = total number of processes in the system.
- = maximum number of Byzantine faulty processes.

Scenarios in the Byzantine Generals Problem
- 3-Process System (): Consensus is impossible.
- If General C is a traitor and sends conflicting messages (
ATTACKto General A,RETREATto General B), Generals A and B receive mismatched information. - Neither A nor B can distinguish whether the other loyal general is lying or if C is the traitor. Thus, A decides
ATTACKwhile B decidesRETREAT, breaking consensus.
- If General C is a traitor and sends conflicting messages (
- 4-Process System (): Consensus is achievable.
- If Process D is a traitor sending conflicting messages, the remaining 3 loyal processes (A, B, and C) cross-exchange messages and detect inconsistencies.
- The loyal majority ( out of ) outvotes the single traitor (), agreeing on
ATTACKand preserving system consensus.
System Availability, Partial Failures, and Resilience Patterns
Centralized applications typically operate in a binary state: either completely UP or completely DOWN. In distributed systems, partial failures occur when individual components fail while remaining services continue operating normally.
Failure Independence and Availability Calculations
Redundancy improves overall availability only when redundant components exhibit failure independence—meaning they do not share common points of failure.
Common failure dependencies include:
- Shared server racks or power distribution units (PDUs).
- Shared database clusters or top-of-rack network switches.
- Co-location in the same cloud availability zone.
Availability is defined mathematically as:
Standard Service Level SLA Metrics ("Nines"):
- Three Nines (): Allows a maximum downtime of per day (or per year).
- Four Nines (): Allows a maximum downtime of per day (or per year).
Fault Tolerance Resilience Patterns
Timeouts
Unbounded network calls cause worker threads and connection sockets to block indefinitely if a remote dependency drops packets or hangs. Applying a strict timeout enforces a maximum execution duration. If no response arrives before the threshold, the operation fails fast and releases system resources.
- Setting Durations: Setting timeouts too short causes false-positive errors during temporary network jitter; setting them too long backs up thread pools, triggering cascading downstream failures.
Retries, Exponential Backoff, and Jitter
When transient faults occur, retrying failed operations automatically restores availability. However, unconstrained retries cause a Retry Storm, where thousands of clients synchronously retry requests against a struggling server, overwhelming it completely.

- Linear Retries: Retries occur at fixed time intervals (e.g., every ). This causes synchronized traffic spikes that overload downstream services.
- Exponential Backoff: Multiplies the delay duration exponentially after each attempt (e.g., ).
- Jitter: Adds pseudo-random delay variations to the exponential backoff calculation. Jitter breaks client synchronization, smoothing out traffic spikes across the network timeline.
- Example Configuration: Base delay = , Multiplier = , Max Retries = , Jitter = .
Idempotency
An operation is idempotent if executing it multiple times produces the exact same system state as executing it a single time.
- Naturally idempotent HTTP methods:
GET,PUT,DELETE. - Non-idempotent HTTP methods:
POST(e.g., retrying a timed-outPOST /checkoutrequest risks executing duplicate payments). - Idempotency Keys: Clients generate a unique UUID per transaction and attach it to the request header (e.g.,
Idempotency-Key: <UUID>). The server logs executed keys; if a duplicate request arrives, the server returns the cached response without re-executing business logic.
Circuit Breakers
Circuit breakers monitor remote downstream service calls to protect system resources during persistent outages. They operate via a three-state machine:
- Closed (Normal): Requests pass through to the downstream service. The breaker monitors error rates.
- Open (Tripped): Triggered when the failure rate exceeds a specified threshold (e.g., error rate). Calls fail immediately with fallback logic without executing network requests.
- Half-Open (Trial): After a defined cooldown period, a limited number of probe requests are allowed through. If they succeed, the breaker resets to Closed; if they fail, it trips back to Open.
Bulkheads and Shuffle Sharding
- Bulkhead Pattern: Named after isolated watertight compartments in ship hulls. System resource pools (such as thread pools, CPU allocations, or database connection pools) are partitioned so that total exhaustion in one domain does not drain resources from other domains.
- Shuffle Sharding: Users are assigned to overlapping virtual sub-clusters (shards) of service instances rather than a global worker pool, reducing the blast radius of a single bad request ("poison pill") to a tiny fraction of total clients.
Upstream Resiliency Techniques
- Load Shedding: When CPU or memory utilization reaches saturation thresholds, the server proactively drops incoming lower-priority traffic (returning
HTTP 503 Service Unavailable) to preserve resources for processing active in-flight requests. - Load Leveling: Ingests high-volume bursts of requests into an asynchronous message queue (e.g., Apache Kafka), allowing downstream worker processes to consume tasks at a stable, controlled rate.
- Rate-Limiting (Throttling): Limits request rates per user, API key, or IP address (returning
HTTP 429 Too Many Requests) to guard against denial-of-service abuse. - Constant Work Pattern: Systems that alter execution modes under heavy load introduce unpredictable bugs and performance degradation. The constant work pattern ensures systems perform the same baseline work under high load as under normal conditions (e.g., continuously writing full snapshot configurations to disk at fixed intervals rather than computing dynamic delta updates under load spikes).
Security in Distributed Systems
Security ensures that system operations, identity data, and distributed state remain protected across untrusted communication media.
Fundamental Security Goals (CIA & AAA)
- Confidentiality: Guarantees sensitive data is shielded from unauthorized inspection.
- Integrity: Ensures data cannot be maliciously modified, deleted, or inserted during transit or storage.
- Availability: Guarantees authorized users maintain uninterrupted access to system services.
- Authentication: Verifies the claimed identity of a user, process, or node ("Who are you?").
- Authorization: Controls access rights to specific system resources based on authenticated identity ("What are you permitted to do?").
- Security Policy vs. Mechanism: Security policies define what operations are allowed; security mechanisms enforce those defined policies.
Primary Network Threats
- Eavesdropping (Interception): Unencrypted data packets sent over public networks are intercepted and read by adversaries.
- Masquerading (Impersonation): An attacker assumes the identity of a legitimate user or trusted system node.
- Message Tampering: Intercepting and altering packet contents in transit prior to forwarding them to the destination.
- Replay Attacks: Capturing valid encrypted packets and retransmitting them later to force duplicate operations (e.g., repeating a financial withdrawal).
- Denial of Service (DoS/DDoS): Overwhelming target nodes with artificial request traffic to exhaust bandwidth, CPU, or memory.
Cryptographic Hash Functions and Message Integrity
A cryptographic hash function maps input data of arbitrary length to a fixed-size output digest :
Key Hash Properties:
- Collision Resistance: It is computationally infeasible to locate two distinct inputs such that .
- Pre-image Resistance (Data Hiding): Given , it is computationally infeasible to recover the original input .
- Puzzle Friendliness: Output bit patterns are uniformly distributed and unpredictable.
HMAC (Hash-based Message Authentication Code) combines a secret key with the message payload, providing both data integrity and origin authentication.

SHA-256 and the Avalanche Effect
SHA-256 produces a fixed-size () output digest. A core property of cryptographic hashes is the Avalanche Effect, where changing a single bit in the input string yields a completely different, uncorrelated digest value. This makes SHA-256 reliable for detecting data tampering.
- Input 1 (44 bytes): "The quick brown fox jumps over the lazy dog"
- SHA-256 Digest:
d7a8fbb307d7809469ca9abcb0082e4f8d56ff1e6b5125e46d3cdb762b02d0bf
- SHA-256 Digest:
- Input 2 (44 bytes - 1 bit modified): "The qoick brown fox jumps over the lazy dog"
- SHA-256 Digest:
3b7f8a2c57136e9d4f7c2d6a3b5e7f91c9a4e2d1f8b6a9c0e3d7b4a1f2c5e6d8
- SHA-256 Digest:
Encryption Mechanisms
- Symmetric Key Encryption: Uses a single shared key for both encryption and decryption. Fast and computationally efficient, but requires a secure out-of-band channel for initial key exchange.
- Asymmetric (Public-Key) Encryption: Employs a mathematically linked key pair—a public key (shared openly) and a private key (kept secret). Computationally expensive; primarily used for digital signatures and key distribution.
- Hybrid Cryptography: Combines both approaches (e.g., TLS). Asymmetric cryptography authenticates parties and negotiates a transient symmetric session key during initial setup; symmetric encryption handles subsequent data transfer.
Digital Signatures and Nonces
- Digital Signatures: Created by hashing a message payload and encrypting the resulting hash using the sender's private key. Anyone with the sender's public key can verify the signature, providing Authentication, Integrity, and Non-Repudiation (the sender cannot deny creating the message).
- Nonces (Number Used Once): Random, high-entropy values combined with message payloads to prevent replay attacks. Receiver nodes log received nonces within a time window and reject duplicate values.
Transport Layer Security (TLS) Handshake Protocol
TLS operates above TCP to create an encrypted, authenticated, and integrity-protected transport channel.
- Client Hello: Client transmits supported TLS versions, symmetric cipher suites, and a client random nonce.
- Server Hello & Certificate: Server responds with chosen cipher options, a server random nonce, and its X.509 Digital Certificate. The client validates the certificate against trusted Certificate Authorities (CAs).
- Key Exchange: The client and server execute an asymmetric key exchange (e.g., Diffie-Hellman) to establish a shared pre-master secret. Both sides derive matching symmetric session keys.
- Encrypted Channel Established: Both endpoints send
Change Cipher SpecandFinishedmessages. All subsequent application traffic is symmetrically encrypted. - Mutual TLS (mTLS): Requires both the client and server to present certificate identities, securing service-to-service communication in microservice architectures.
Token Authentication and Authorization
- JSON Web Token (JWT): A URL-safe standard used to pass cryptographically signed claims between distributed services.
- Header: Specifies token type and signature algorithm (e.g.,
HS256,RS256). - Payload: Contains claims data (e.g.,
userId,roles,expirationTime). - Signature: Generated by signing
Header + Payloadusing a secret key or private key. - Stateless Advantage: Services validate signatures locally using public keys without querying a centralized session store.
- Header: Specifies token type and signature algorithm (e.g.,
- OAuth 2.0: An open authorization framework that enables users to grant third-party applications limited access to HTTP resources without exposing user credentials. Defines four core roles: Resource Owner, Client, Authorization Server, and Resource Server.
Observability, Health Checks, and Monitoring
Observability provides visibility into internal distributed state based on external outputs.
Health Check Probes
- Liveness Probe: Verifies whether the process is alive. If this probe fails, the orchestrator (e.g., Kubernetes) restarts the container.
- Readiness Probe: Verifies whether the application is ready to accept user network traffic (e.g., database connection pools are initialized). If it fails, traffic routing to the instance is paused.
- Startup Probe: Disables liveness and readiness checks during slow application startup sequences to prevent premature container restarts.
Structured Logging and Correlation IDs
Unstructured string logs are difficult to parse across distributed microservice traces. Structured Logging formats log entries as machine-readable JSON key-value pairs.
When a single client request spans multiple downstream microservice calls, tracking execution flows requires a Correlation ID—a unique UUID injected into the request HTTP header at the API Gateway. Each downstream service logs this ID, allowing centralized log aggregators (e.g., Elasticsearch, OpenSearch) to stitch disjointed log events into a single timeline.
Observability Pillars and Reliability Metrics
- Three Pillars of Observability: Metrics, Logs, and Traces.
- Service Level Indicators (SLIs): Specific, measurable quantitative metrics measuring operational service performance (e.g., HTTP request latency, error rate).
- Service Level Objectives (SLOs): Target reliability goals set for an SLI over a temporal window (e.g., " of HTTP requests must complete in under ").
- Error Budget: The allowable room for failure calculated as:
If the error budget is exhausted within a tracking window, new feature deployments are suspended to prioritize reliability engineering.
Time, Physical Clocks, and Synchronization
Distributed systems lack a global shared physical clock. Each physical node maintains an independent clock driven by a vibrating quartz crystal oscillator. Due to physical limitations, quartz clocks drift over time.

Physical Clock Properties
- Clock Drift: The rate at which a local clock gains or loses time relative to an absolute reference clock. Typical quartz crystal oscillators drift at , accumulating of drift every .
- Clock Skew: The instantaneous time difference between readings on two distinct physical clocks at the same moment.
- Coordinated Universal Time (UTC): The international time standard derived from high-precision cesium-133 atomic clocks (which exhibit drift rates of ), periodically adjusted with leap seconds.
Physical Clock Synchronization Algorithms
Cristian's Algorithm (External Synchronization)
Designed for client nodes synchronizing with a central UTC-synchronized time server .
- A client dispatches a time request at local time .
- The server receives the request, attaches its UTC clock time , and returns a response.
- The client receives the response at local time .
- Assuming symmetric network transit times, total Round-Trip Time () is calculated as:
- The client sets its local clock using the formula:
- Synchronization accuracy error bound (given minimum one-way network latency ):
- Limitation: The central time server is a single point of failure and network bottleneck.
Berkeley Algorithm (Internal Synchronization)
Designed for environments without access to an external UTC reference; aims to make all participating nodes agree on a common time.
- A master server actively polls connected slave sites for their current local time readings.
- Slaves respond with their local clock values.
- The master estimates each slave's physical time, eliminating statistical outliers (faulty clocks exhibiting excessive skew).
- The master calculates the system-wide average time :
- The master calculates a specific drift adjustment value for each slave node :
- Slaves adjust their local clock rates (slewing) by to converge smoothly without stepping time backward.
Network Time Protocol (NTP)
NTP provides hierarchical time distribution across internet scales, structured in logical layers called Strata:
- Stratum 0: High-precision reference physical devices (e.g., cesium atomic clocks, GPS receivers).
- Stratum 1: Primary time servers directly attached to Stratum 0 physical devices.
- Stratum 2: Secondary servers polling Stratum 1 nodes across network connections.
- Stratum 3: End-user client machines synchronizing with Stratum 2 servers.
NTP Symmetric Mode Pair Exchange Calculations:
Given timestamps for request dispatch (), request arrival (), response dispatch (), and response arrival ():
Monotonic Clocks vs. Wall-Clock Time
- Wall-Clock Time: Represents calendar time-of-day. Susceptible to backward NTP step adjustments when adjusting for skew, making it unsuitable for measuring elapsed time.
- Monotonic Clocks: Monotonically increasing timers derived from CPU tick counters since boot. Guaranteed never to move backward. Required for computing durations, latencies, and timeouts.
Logical Clocks and Causal Event Ordering
Because physical clocks cannot guarantee absolute synchronization, distributed processes rely on logical clocks to order execution events.
Events and the Happened-Before Relation
An event represents an atomic execution step within a process (e.g., local calculation, variable write, message send, message receive).
Leslie Lamport defined the Happened-Before Relation () using three rules:
- Process Order: If events and occur sequentially within the same process, then .
- Message Passing: If event is the sending of a message by one process, and event is the receipt of message by another process, then (i.e., ).
- Transitivity: If and , then :
Concurrent Events
Two events and are concurrent () if neither event happened before the other:
Note: Concurrency does not imply physical simultaneity; it means there is no causal relationship between the events.
Lamport Logical Clocks
A Lamport Logical Clock is a monotonically increasing scalar counter maintained by process ().
Update Rules
- Rule IR1 (Local/Send Event): Prior to executing an internal event or sending a message, process increments its local counter:
- Rule IR2 (Message Timestamping): When sending message , process attaches timestamp to the message payload.
- Rule IR3 (Message Receipt): Upon receiving message with timestamp , process updates its logical counter before delivering the message:
Clock Consistency Condition
Total Ordering
Lamport clocks generate a partial order. To create a strict total order (), ties between identical timestamps are broken using unique process identifiers ():
a < b \iff (C(a) < C(b)) \lor (C(a) = C(b) \land P_i < P_j)
Limitation of Lamport Clocks
Lamport clocks are non-reversible: . Observing does not prove that ; events and could be concurrent (). Scalar Lamport timestamps cannot detect causal independence.
Vector Clocks
Vector Clocks (developed by Mattern and Fidge) capture complete causal dependency and detect concurrency. In a system of processes, each process maintains a vector array :
- : Logical time at process .
- (where ): 's best estimate of process 's logical time.
Vector Update Rules
- Rule VR1 (Local Event): Prior to an internal or send event, process increments its own entry:
- Rule VR2 (Message Transmission): When sending message , process updates via VR1 and attaches vector to m$.\n- **Rule VR3 (Message Receipt)**: Upon receiving message mV_mP_j computes the element-wise maximum across all vector entries and increments its own position:\n\n\forall k \in [1..N], \quad V_j[k] = \max(V_j[k], V_m[k])\n\nV_j[j] = V_j[j] + 1\n\n### Vector Comparison and Concurrency Detection\n\n- **Causal Precedence**: Event aba \rightarrow b) if and only if:\n\nV(a) < V(b) \iff (\forall k, V(a)[k] \le V(b)[k]) \land (\exists k, V(a)[k] < V(b)[k])\n\n- **Concurrency**: Vectors V(a)V(b)V(a) \le V(b)V(b) \le V(a)a \parallel b.\n\n# Leader Election Algorithms\n\nLeader election algorithms elect a single active process from a group of identical nodes to serve as system coordinator (e.g., primary replica, task scheduler). Leader election requires **symmetry breaking**, achieved by assigning each process a unique Process Identifier (PID).\n\n## The Bully Algorithm\n\nAssumes a fully connected network model where processes know all peer PIDs, operating under a crash-stop model with reliable timeouts.\n\n1. **Initiation**: When process P_iP_j > P_i).\n2. **Response (`OK`)**: If a higher process P_jP_iP_i).\n3. **Victory**: If P_i receives no `OK` replies within a timeout window, it declares itself coordinator and broadcasts a `COORDINATOR` message to all processes.\n- **Message Complexity**: Worst-case O(N^2) message transmissions (when the lowest PID process detects the failure first).\n\n## Ring-Based Election Algorithms\n\nAssumes nodes are arranged in a logical ring topology where each node knows its immediate successor.\n\n### "All The Way Up" Algorithm\n\nInitiators pass an `ELECTION` message containing their PID around the ring. Each node appends or updates the tracking list. The message circulates fully (NO(N^2) worst-case message complexity.\n\n### Chang & Roberts Algorithm ("As Far As An ID Can Go")\n\n- A process P_iP_kP_kP_k > P_i.\n- If P_k < P_iP_i discards (swallows) the message.\n- If P_k = P_iP_iP_i becomes coordinator and transmits an `ANNOUNCEMENT` message.\n- **Message Complexity**: Best-case O(N \log(N))O(N^2).\n\n## Hirschberg & Sinclair Algorithm\n\nAn optimized bidirectional ring algorithm operating in phases (k = 0, 1, 2, \dots):\n\n1. In phase kP_i2^k hops.\n2. If a probe encounters a node with a higher PID, the higher-node swallows the probe.\n3. If probes travel distance 2^kP_i.\n4. Upon receiving both replies, P_ik+12^{k+1}).\n- **Message Complexity**: Worst-case O(N \log(N)) messages.\n- **Time Complexity**: O(N) time steps.\n\n# Distributed Mutual Exclusion\n\nDistributed Mutual Exclusion algorithms serialize access to shared Critical Sections (CS) across independent processes without shared memory.\n\n## Correctness Criteria\n\n1. **Safety**: At most one process can execute inside the Critical Section at any time.\n2. **Liveness (Deadlock/Starvation Freedom)**: Requests to enter the CS are eventually granted.\n3. **Fairness**: Requests enter the CS in logical timestamp (happened-before) order.\n\n## Non-Token Assertion-Based Algorithms\n\n### Centralized Coordinator Solution\n\nA master coordinator manages a FIFO request queue. Requires 3 messages per CS execution (`REQUEST`, `GRANT`, `RELEASE`).\n- *Limitation*: The coordinator is a single point of failure and bottleneck.\n\n### Lamport's Distributed Mutual Exclusion Algorithm\n\n1. Requesting site S_i(t_i, i) to all processes and pushes it onto its own local FIFO queue.\n2. Peer processes reply with a timestamped `REPLY` message.\n3. Process S_i enters the CS when:\n - Its request (t_i, i) is at the head of its local request queue.\n - It has received timestamped messages (or replies) with timestamps strictly greater than (t_i, i) from all other processes.\n4. Upon exiting the CS, S_i removes its request and broadcasts a timestamped `RELEASE` message.\n- **Message Cost**: 3(N - 1) messages per CS entry.\n\n### Ricart-Agrawala Algorithm\n\nAn optimization that eliminates explicit `RELEASE` messages by merging them with deferred `REPLY` responses.\n\n- If process S_j(t_i, i)S_iS_jS_j(t_j, j) < (t_i, i).\n- Otherwise, S_jS_i$.
- Process enters the CS as soon as it collects
REPLYmessages from all peer processes. - Message Cost: messages per CS entry.
Maekawa's Quorum-Based Algorithm
Processes request permission from a subset of processes called a Quorum ().
- Quorum Intersection Property: Quorums are structured such that any two quorums overlap by at least one process:
- The overlapping processes act as arbitrators, granting permission to only one request at a time.
- Optimal Quorum Size: .
- Message Cost: to messages per CS entry.
- Note: Prone to deadlocks if requests arrive out of order across common sites; resolved using
INQUIRE,YIELD, andFAILEDmessages.
Token-Based Algorithms
Access to the Critical Section is controlled by a single unique Token. Whichever process holds the token has exclusive right to enter the CS.
Suzuki-Kasami Broadcast Algorithm
- A process requesting the CS broadcasts a
REQUESTmessage , where is a sequence counter. - The token contains a queue of waiting requests and an array tracking sequence numbers of completed CS accesses.
- Upon exiting the CS, the token holder updates , appends newly received requests where to , and passes the token directly to the process at the head of Q$.\n- **Message Cost**: N - 10 messages if the process already holds the token).\n\n### Raymond's Tree-Based Algorithm\n\n- Nodes are arranged in a directed tree topology where edges point toward the current token holder.\n- Each node maintains a local variable `HOLDER` pointing to the neighbor closest to the token.\n- CS requests travel up directed tree edges toward the root.\n- **Message Cost**: O(\log(N))$$ average messages per CS entry.