DEV Community: Binary Dose

More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement

Binary Dose — Fri, 13 Nov 2026 20:40:36 +0000

More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement

Intuition suggests that allocating more physical memory (RAM frames) to a process must either decrease the number of page faults or, in the worst case, keep them unchanged.

Yet in 1969, computer scientist László Bélády proved a startling paradox: under First-In, First-Out (FIFO) page replacement, increasing the number of page frames can actually increase the total page faults.

This phenomenon is known as Bélády's Anomaly.

1. The Mathematical Counterexample

Consider the following reference string of page requests:

σ = 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Trace A: 3 Page Frames

Tracing FIFO replacement through the 12 memory accesses results in 9 Page Faults.

Trace B: 4 Page Frames

Expanding physical allocation to 4 frames results in 10 Page Faults!

Adding a 4th physical frame increases total page faults by 11%.

2. Why FIFO Suffers: The Lack of Locality

FIFO replacement selects the page that has been in memory the longest time.

Crucially, the age of a page has no correlation with its future utility. When a 4th frame is added, the timing of page evictions shifts. A frequently accessed page that happened to survive under 3 frames is prematurely evicted under 4 frames, triggering an avalanche of subsequent faults.

3. Why LRU Is Immune: The Stack Inclusion Property

Why does Least Recently Used (LRU) never exhibit Bélády's Anomaly?

LRU belongs to a mathematical class known as Stack Algorithms.
A page replacement algorithm is a stack algorithm if it satisfies the Inclusion Property:

B(M, t) ⊆ B(M+1, t)

Where B(M, t) represents the set of pages present in memory of size M at time t.

In LRU, the top M most recently used pages are always a strict subset of the top M+1 most recently used pages. Therefore:

Any memory hit under M frames is guaranteed to be a hit under M+1 frames.
Adding RAM can never increase page faults under LRU or Optimal replacement!

Explore interactive page replacement simulations at Binary Dose.

Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes

Binary Dose — Thu, 12 Nov 2026 21:10:29 +0000

Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes

In relational database systems running under Two-Phase Locking (2PL), deadlock is an inevitable side effect of concurrent lock acquisition.

Traditionally, databases employ Deadlock Detection: the engine builds a Wait-For Graph in memory, runs cycle-detection algorithms (e.g., Tarjan's or DFS), and selects a victim to abort when a cycle forms.

However, in ultra-high-throughput systems, constantly searching for cycles introduces significant locking overhead.

Instead, database engines can employ Timestamp-Based Deadlock Prevention: Wait-Die and Wound-Wait.

1. The Timestamp Precedence Rule

Every transaction T_i is assigned a monotonically increasing timestamp TS(T_i) when it begins.

If TS(T_i) < TS(T_j), T_i is older (senior).
If TS(T_i) > TS(T_j), T_i is younger (junior).

A deadlock requires a cyclic dependency chain:

T₁ → T₂ → ... → T_n → T₁

By enforcing strict directional rules based on age, cyclic dependencies become mathematically impossible.

2. The Wait-Die Scheme (Non-Preemptive)

Suppose transaction T_i requests a lock currently held by T_j:

If T_i is older than T_j (extTS(T_i) < extTS(T_j)):
- T_i is allowed to WAIT until T_j releases the lock.
If T_i is younger than T_j (extTS(T_i) > extTS(T_j)):
- T_i DIES (aborts, rolls back its mutations, and restarts).

Intuition:

Only older transactions may wait for younger transactions. A younger transaction can never wait for an older one, making cycles impossible.

3. The Wound-Wait Scheme (Preemptive)

Suppose transaction T_i requests a lock currently held by T_j:

If T_i is older than T_j (extTS(T_i) < extTS(T_j)):
- T_i WOUNDS T_j. The engine immediately preempts and aborts T_j, granting the lock to T_i.
If T_i is younger than T_j (extTS(T_i) > extTS(T_j)):
- T_i is allowed to WAIT for T_j.

4. Preventing Starvation

In both schemes, when an aborted transaction restarts, it retains its original timestamp.

As time progresses, an aborted transaction becomes progressively older relative to newly arriving transactions. Eventually, it becomes the oldest transaction in the system, guaranteeing it will never be aborted again.

Explore full database concurrency control architectures at Binary Dose.

Behind Routing Tables: CIDR and the Longest Prefix Match Rule

Binary Dose — Thu, 12 Nov 2026 12:45:00 +0000

Behind Routing Tables: CIDR and the Longest Prefix Match Rule

The global Internet routing table currently exceeds 1,000,000 routes.

Yet a backbone router must inspect the destination IP address of an incoming packet, find the correct outgoing interface, and forward the packet in under 10 nanoseconds to sustain 100 Gbps line-rate throughput.

The scalability of the entire Internet rests on Classless Inter-Domain Routing (CIDR) and the Longest Prefix Match (LPM) algorithm.

1. CIDR and Route Aggregation (Supernetting)

Before 1993, IP addresses were bound to rigid classes:

Class A: /8 (16 million hosts)
Class B: /16 (65,536 hosts)
Class C: /24 (256 hosts)

Organizations needing 2,000 IPs were forced to request an entire Class B block, wasting 63,000 addresses. Furthermore, every network required its own routing table entry.

CIDR introduced variable-length subnet masks (/n). Upstream Internet Service Providers (ISPs) aggregate contiguous subnets into a single supernet route:

Instead of advertising sixteen separate /24 subnets, an ISP announces a single /20 prefix to the global BGP routing table.

2. The Overlapping Route Dilemma

Route aggregation inevitably creates overlapping routing entries:

Network Destination	Subnet Mask	Next Hop Interface
`192.168.0.0`	`/16`	`eth0`
`192.168.1.0`	`/24`	`eth1`
`0.0.0.0`	`/0` (Default)	`eth2`

Suppose a packet arrives with destination IP 192.168.1.55:

Bitwise AND with /16 yields 192.168.0.0 implies Matches eth0.
Bitwise AND with /24 yields 192.168.1.0 implies Matches eth1.
Bitwise AND with /0 yields 0.0.0.0 implies Matches eth2.

3. The Longest Prefix Match Rule

When a packet destination matches multiple routes, the router forwards the packet out the interface associated with the longest prefix length (the most specific route).

In our example, /24 has 24 matching network bits, compared to 16 bits for /16. The router selects eth1.

Hardware Implementation:

Software linear search across 1,000,000 routes is too slow. Modern core routers use:

Patricia Tries / Radix Trees: Hierarchical prefix trees traversed bit by bit.
Ternary Content Addressable Memory (TCAM): Specialized associative hardware that searches all 1,000,000 prefixes in parallel in a single clock cycle (<5ns).

Explore full IP networking architectures and subnetting calculators at Binary Dose.

The Cost of Virtual Memory: TLBs and Effective Memory Access Time

Binary Dose — Wed, 11 Nov 2026 11:53:53 +0000

The Cost of Virtual Memory: TLBs and Effective Memory Access Time

Virtual memory provides every user process with a private, uniform address space protected from neighboring applications.

However, address translation incurs an inherent architectural penalty: every memory reference requires translating a virtual address into a physical address.

1. The Two-Access Penalty

Because the Page Table is itself a data structure stored in main memory (RAM):

Access 1: The MMU reads the Page Table entry in RAM to translate the Virtual Page Number (VPN) into a Physical Frame Number (PFN).
Access 2: The CPU accesses the actual data byte at the physical address.

Without hardware acceleration, virtual memory doubles the latency of every instruction! In 64-bit systems with 4-level paging, a naive lookup requires 5 sequential memory accesses per operation.

2. The Translation Lookaside Buffer (TLB)

To eliminate this bottleneck, the Memory Management Unit (MMU) incorporates a small, high-speed associative hardware cache: the Translation Lookaside Buffer (TLB).

Associative Search: All TLB entries are compared simultaneously in parallel, resolving in sub-nanosecond time (c).
TLB Hit: The VPN is cached in the TLB. The physical frame number is returned immediately, requiring only 1 main memory access.
TLB Miss: The translation is absent. The MMU must walk the Page Table in RAM, requiring 2 main memory accesses (or k+1 for k-level paging).

3. Effective Memory Access Time (EMAT) Formula

Let:

h = TLB Hit Ratio
c = TLB Lookup Time
m = Main Memory Access Time

EMAT = h · (c + m) + (1 - h) · (c + 2m)

Worked Example:

Assume main memory access time m = 100ns, TLB lookup time c = 10ns, and hit ratio h = 98\%:

EMAT = 0.98 · (10 + 100) + 0.02 · (10 + 200)

EMAT = 0.98 · 110 + 0.02 · 210 = 107.8 + 4.2 = 112ns

Despite paging overhead, the Effective Memory Access Time is only 12ns higher than raw physical RAM!

Explore interactive virtual address translation rails at Binary Dose.

Why OS Virtual Memory Paging Saved LLM Inference: The vLLM Breakthrough

Binary Dose — Tue, 10 Nov 2026 20:38:13 +0000

Why OS Virtual Memory Paging Saved LLM Inference: The vLLM Breakthrough

In high-throughput Large Language Model (LLM) serving, the primary hardware bottleneck is rarely raw compute (FLOPs)—it is GPU High-Bandwidth Memory (VRAM).

Specifically, the auto-regressive generation of tokens requires saving the Key and Value attention matrices for every preceding token: the KV Cache.

Until the introduction of PagedAttention (vLLM) in 2023, standard serving systems (like HuggingFace and v1 inference engines) wasted between 60% and 80% of all GPU memory.

The solution didn't come from new AI algorithms; it came from a 50-year-old operating systems concept: Virtual Memory Paging.

1. The Contiguous Allocation Problem

In standard self-attention, the key and value vectors of a sequence must be stored in contiguous physical memory so that CUDA matrix kernels can execute efficiently.

Because the system cannot predict how many tokens an LLM will generate before emitting the <EOS> stop token, traditional engines pre-allocated contiguous memory slots for the maximum request length (e.g., 2,048 or 4,096 tokens).

Two Forms of Memory Waste:

Internal Fragmentation: If a request pre-allocates 2,048 tokens but stops after 150 tokens, the remaining 1,898 slots sit reserved and completely idle.
External Fragmentation: Because requests start and finish dynamically, allocating contiguous variable-sized memory blocks creates fragmented holes in GPU VRAM, preventing new batches from scheduling.

2. The PagedAttention Architecture

PagedAttention resolves this by relaxing the requirement that KV vectors be stored in contiguous physical memory.

KV Blocks: The KV cache is divided into fixed-size physical blocks (e.g., 16 tokens per block).
Block Table: Identical to an Operating System's Page Table, the engine maintains a mapping between logical token positions and physical GPU memory blocks.
On-Demand Allocation: Physical blocks are allocated one by one only as new tokens are generated.

When computing attention for a newly generated token, the custom CUDA kernel looks up the physical block addresses in the block table, fetching key-value vectors on the fly from non-contiguous memory locations.

3. Copy-on-Write for Prompt Sharing

PagedAttention also implements Copy-on-Write (COW):

In parallel sampling (generating multiple answers for the same prompt) or beam search, all branches share the exact same physical prompt KV blocks.
Only when a specific branch generates a new token does it allocate its own private block.

Memory waste plummets from 80% to under 4%, enabling servers to double or quadruple active batch sizes.

Read the full deep-dive with interactive architectural schematics at Binary Dose.

Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing

Binary Dose — Tue, 10 Nov 2026 12:40:42 +0000

Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing

When indexing relational databases (such as MySQL's InnoDB or PostgreSQL's standard btree index), the underlying data structure is almost universally a B+ Tree, rather than a standard B-Tree.

To understand why, we must analyze how physical storage hardware and operating system page caches interact with tree fan-out.

1. The Fan-Out Problem in Standard B-Trees

In a standard B-Tree, every node (both internal and leaf) stores:

Search Keys
Child Pointers
Record / Tuple Pointers (Data Pointers)

Because physical storage is organized into fixed-size blocks (typically 16 KB in InnoDB), the inclusion of bulky data pointers significantly reduces the number of keys that can fit into a single page.

The Math:

If each entry is 128 bytes (key + data pointer), a 16 KB page holds ≈ 125 keys.
If internal nodes store only 16-byte routing entries (8-byte key + 8-byte child pointer), a 16 KB page holds 1,000 keys!

Higher fan-out directly reduces tree height h. In a database indexing 1 billion rows:

Lower fan-out B-Tree: Height = 5–6 (5–6 disk seeks).
Higher fan-out B+ Tree: Height = 3 (3 disk seeks).

Because the root and level-1 nodes reside permanently in the database RAM buffer pool, nearly all point lookups execute in just 1 physical disk seek!

2. Linked Leaf Nodes for Sequential Range Queries

Relational database queries frequently retrieve ranges of records:

SELECT * FROM orders WHERE order_date BETWEEN '2026-01-01' AND '2026-01-31';

In a B-Tree:

Records matching the range are scattered across internal nodes and leaf nodes. The engine must perform an expensive, recursive in-order tree traversal, repeatedly navigating up and down parent pointers.

In a B+ Tree:

All data records reside exclusively in leaf pages.
Every leaf page contains a pointer to the next and previous leaf page (forming a doubly-linked list).
The engine performs a single point lookup to find the start key (2026-01-01), and then simply scans horizontally across the leaf linked list in O(K) time!

Explore full database storage engine architectures at Binary Dose.

The Math of Collisions: Pure ALOHA vs Slotted ALOHA Efficiency

Binary Dose — Mon, 09 Nov 2026 23:11:49 +0000

The Math of Collisions: Pure ALOHA vs Slotted ALOHA Efficiency

In shared medium networks, multiple autonomous stations compete for access to a single communication channel without a central scheduler.

Developed at the University of Hawaii in 1970, Pure ALOHA and Slotted ALOHA are the foundational random access protocols that established the mathematical framework for modern Ethernet and Wi-Fi.

1. Pure ALOHA: `S = G · e^-2G`

In Pure ALOHA, stations transmit frames whenever data is generated. If a frame collides with another transmission—even by a single bit—the entire frame is destroyed.

The Vulnerability Period (`2 · T_f`):

Let T_f be the frame transmission time. Suppose station A starts transmitting at time t₀:

If station B began transmitting between t₀ - T_f and t₀, its end overlaps with A's start.
If station C begins transmitting between t₀ and t₀ + T_f, its start overlaps with A's end.

The Vulnerability Window is 2 · T_f.

Assuming frame generation follows a Poisson distribution with attempt rate G frames per slot time:

P(k frames in 2T_f) = frac(2G)^k · e^-2Gk!

The probability of a successful transmission (k = 0 collisions) is e^-2G.
Throughput S is:

S = G · e^-2G

Differentiating (dS / dG) = e^-2G(1 - 2G) = 0 implies G = 0.5.

S_max = (1 / 2e) ≈ 18.4\%

2. Slotted ALOHA: `S = G · e^-G`

Slotted ALOHA introduces a centralized clock dividing time into discrete slots of length T_f. Stations can only begin transmission at the beginning of a slot boundary.

Halving the Vulnerability Window:

Because all transmissions start simultaneously:

A frame either collides completely or passes completely.
The vulnerability period shrinks from 2 · T_f down to T_f.

P(0 frames in T_f) = e^-G

S = G · e^-G

Differentiating (dS / dG) = 0 implies G = 1.0.

S_max = (1 / e) ≈ 36.8\%

Synchronizing transmissions doubles the channel capacity from 18.4\% to 36.8\%.

Explore complete protocol derivations and framing simulations at Binary Dose.

Mutex vs Spinlock: When Should a Thread Sleep or Spin?

Binary Dose — Mon, 09 Nov 2026 12:54:30 +0000

Mutex vs Spinlock: When Should a Thread Sleep or Spin?

In multi-threaded software engineering, managing shared mutable state requires synchronization primitives to enforce Mutual Exclusion.

Yet choosing between a Mutex, a Spinlock, and a Semaphore is not a matter of syntax—it is a hardware-level trade-off between CPU Context Switching Latency and CPU Cycle Waste.

1. Mutex: Sleep-Waiting with Strict Ownership

A Mutex is a binary synchronization primitive with ownership semantics: only the thread that locks a mutex is legally permitted to unlock it.

Mechanics:

When thread T₁ attempts to acquire a contested mutex:

The kernel transitions T₁ from RUNNING to BLOCKED.
T₁'s register state is saved, and the CPU schedules another thread.
When the lock is released, the kernel moves T₁ back to the READY queue.

The Overhead Cost:

A mutex operation incurs two full context switches (descheduling + rescheduling). On modern x86/ARM hardware, this represents roughly 1µs - 5µs of latency, accompanied by L1/L2 cache pollution.

2. Spinlock: Busy-Waiting with Atomic Hardware

A Spinlock does not surrender the CPU core. Instead, it loops in place executing atomic instructions (such as lock cmpxchg or test_and_set).

// Conceptually:
while (__atomic_test_and_set(&lock, __ATOMIC_ACQUIRE)) {
    #if defined(__x86_64__)
    __builtin_ia32_pause(); // Emits PAUSE instruction to prevent pipeline stalls
    #endif
}

Advantages & Disadvantages:

Advantage: Zero context-switch cost. Acquisition latency is measured in nanoseconds.
Disadvantage: Burns 100% of an entire CPU core while spinning. If the thread holding the lock is preempted, the spinning thread starves the system.
Rule: Mandatory in Interrupt Service Routines (ISRs) because hardware interrupt handlers cannot sleep.

3. The Mathematical Rule of Thumb

Let T_ctx be the time required for a context switch, and T_hold be the average time a thread holds the critical section:

If T_hold < 2 · T_ctx implies Use a Spinlock

If T_hold > 2 · T_ctx implies Use a Mutex

Explore interactive concurrency state machines at Binary Dose.

Graphing Database Conflicts: How Precedence Graphs Prove Serializability

Binary Dose — Sun, 08 Nov 2026 11:18:51 +0000

Graphing Database Conflicts: How Precedence Graphs Prove Serializability

In high-throughput relational databases, executing transactions serially (one after another) wastes massive CPU and I/O parallelism. Instead, storage engines execute multiple transactions concurrently with interleaved operations.

However, arbitrary interleaving can trigger lost updates, dirty reads, and inconsistency.

To prove that an interleaved schedule S is mathematically safe, database theory relies on Conflict Serializability.

1. What Makes Two Operations Conflict?

Two operations I_i and I_j in a schedule conflict if and only if they satisfy three conditions:

They belong to different transactions (T_i ≠ T_j).
They access the same data item (Q).
At least one of them is a write operation (W(Q)).

The Conflict Matrix:

Read-Read (R_i(Q), R_j(Q)): No conflict. Order does not alter data.
Read-Write (R_i(Q), W_j(Q)): Conflict. Swapping changes whether T_i reads the old or new value.
Write-Read (W_i(Q), R_j(Q)): Conflict. Swapping alters T_j's observation.
Write-Write (W_i(Q), W_j(Q)): Conflict. Swapping alters the final value surviving in storage.

2. Constructing the Precedence Graph

A Precedence Graph (or Serialization Graph) is a directed graph G = (V, E) constructed as follows:

Vertices (V): Every transaction participating in the schedule.
Edges (E): A directed edge T_i → T_j is drawn if T_i executes a conflicting operation before T_j.

3. The Serializability Theorem

A concurrent schedule S is conflict serializable if and only if its precedence graph contains no directed cycles.

If Acyclic: The schedule can be serialized. The equivalent serial execution order is obtained via Topological Sorting of the DAG.
If a Cycle Exists: (e.g., T₁ → T₂ → T₁), it implies T₁ must precede T₂, but T₂ must also precede T₁—a physical impossibility. The schedule is rejected or aborted.

Explore interactive conflict precedence graph analyzers at Binary Dose.

Sliding Window Sizing: Why Go-Back-N and Selective Repeat Limit Window Sizes

Binary Dose — Sat, 07 Nov 2026 18:21:54 +0000

Sliding Window Sizing: Why Go-Back-N and Selective Repeat Limit Window Sizes

Sliding window protocols allow transmitters to pipeline multiple unacknowledged frames, saturating links governed by the Bandwidth-Delay Product.

However, sequence numbers cannot grow indefinitely; they are encoded in an m-bit header field, providing a finite sequence space of 2^m unique IDs (modulo 2^m).

A fundamental question arises: Why can't we size the sender window W_s to match the full sequence space 2^m?

1. Go-Back-N ARQ: `W_s ≤ 2^m - 1`

In Go-Back-N, the receiver maintains a window of size W_r = 1. It accepts only the exact next in-order frame and discards any out-of-order packets.

The Ambiguity Proof (Why `W_s = 2^m` Fails):

Assume m = 2, giving sequence numbers \0, 1, 2, 3\. Suppose we set W_s = 4:

Sender transmits frames 0, 1, 2, 3.
The receiver successfully receives all four frames, slides its expected sequence counter from 0 → 1 → 2 → 3 → 0, and sends acknowledgments.
Disaster Scenario: Every ACK is lost in transit.
The sender's retransmission timer fires for frame $0$ and retransmits it.
The receiver is currently expecting sequence number $0$ (from the next cycle). It accepts the duplicate frame $0$ as fresh data!

To eliminate this ambiguity, the window size must leave at least one sequence number unallocated:

W_s ≤ 2^m - 1

2. Selective Repeat ARQ: `W_s + W_r ≤ 2^m`

In Selective Repeat, the receiver independently acknowledges frames and buffers out-of-order packets. To maximize symmetrical pipelining, W_s = W_r.

The Ambiguity Constraint:

When all ACKs are lost, the sender retransmits its oldest unacknowledged window. For the receiver to distinguish between a retransmitted old packet and a legitimate new packet across the modular boundary:

W_s + W_r ≤ 2^m

Since W_s = W_r:

2 · W_s ≤ 2^m implies W_s ≤ 2^m-1

The maximum sender window size in Selective Repeat is half the total sequence number space.

Explore interactive space-time protocol ladders at Binary Dose.

Behind ACID: How Databases Actually Implement the 4 Guarantees

Binary Dose — Fri, 06 Nov 2026 20:07:22 +0000

Behind ACID: How Databases Actually Implement the 4 Guarantees

Every software engineer learns the ACID acronym during introductory database coursework. Yet in production engineering interviews and high-concurrency systems design, theoretical definitions are insufficient.

To design resilient architectures, you must understand the concrete low-level engines responsible for enforcing each guarantee.

1. Atomicity: The Undo Log

Atomicity ensures that a transaction executes as a single, indivisible unit of work: either all operations succeed, or none do.

Implementation:

The database storage engine maintains an append-only Undo Log in memory and disk:

Before mutating any data page in the buffer pool, the engine writes an undo record containing the pre-image (original values).
If an unhandled exception occurs or the client issues ROLLBACK, the recovery manager traverses the undo log backward, writing the original values back into data pages.
If the server loses power mid-transaction, startup recovery parses the undo log to clean up incomplete transactions.

2. Consistency: Declarative Constraints

Consistency ensures the database transitions exclusively between legally valid states that satisfy all integrity rules.

Implementation:

Enforced by relational constraints:

Primary Key / Unique Indexes: Prevents duplicate identity.
Foreign Key Constraints: Prevents orphaned relational records.
CHECK Constraints: Enforces domain boundaries (e.g., balance >= 0).

3. Isolation: Concurrency Control (2PL vs MVCC)

Isolation guarantees that concurrent execution yields the exact same state as if transactions ran sequentially.

Implementation:

Two-Phase Locking (2PL): Locks data items during execution (Growing phase) and releases them only at termination (Shrinking phase).
Multi-Version Concurrency Control (MVCC): Storage engines (PostgreSQL, InnoDB) tag tuples with transaction IDs (xmin/xmax). Readers read snapshot versions without blocking concurrent writers.

4. Durability: Write-Ahead Logging (WAL)

Durability guarantees that once a transaction receives a successful COMMIT response, its updates will survive subsequent hardware crashes or power cuts.

Implementation:

Writing 16KB dirty data pages randomly across a disk array is slow. Instead, modern engines enforce the WAL Protocol:

Changes are written sequentially to a fast, append-only Redo Log.
When COMMIT is executed, the engine forces an fsync() of the log buffer to non-volatile storage.
On reboot after a crash, the ARIES Redo Phase replays logged changes to rebuild physical state.

Explore interactive database transaction blueprints on Binary Dose.

Why 10Gbps Links Feel Slow: Stop-and-Wait ARQ Efficiency Formula Explained

Binary Dose — Thu, 05 Nov 2026 20:51:20 +0000

Why 10Gbps Links Feel Slow: Stop-and-Wait ARQ Efficiency Formula Explained

When deploying high-speed fiber links across continents, engineers often discover a paradoxical reality: upgrading bandwidth from 1 Gbps to 10 Gbps yields almost zero throughput improvement for single-packet protocols.

The culprit is the fundamental physics governing Stop-and-Wait ARQ Link Efficiency.

1. Transmission Delay vs Propagation Delay

Every network exchange is governed by two distinct physical metrics:

Transmission Delay (T_t): The time required to inject all L bits of a frame into the transmission medium at bandwidth B:

T_t = (L / B)

Propagation Delay (T_p): The time taken by a single electromagnetic bit to travel across physical distance d at propagation speed v (approx. 2 × 10⁸ m/s in glass):

T_p = (d / v)

In Stop-and-Wait ARQ, the sender transmits one frame and then completely halts until receiving an acknowledgment (ACK). Assuming ACK transmission time is negligible, the total roundtrip cycle time is:

Total Cycle Time = T_t + 2 · T_p

2. Deriving the Efficiency Formula: `U = (1 / 1 + 2a)`

Channel utilization (U) represents the fraction of total cycle time spent doing useful work (transmitting data):

U = (T_t / T_t + 2 · T_p) = (1 / 1 + 2 · left(fracT_p)T_tright)

Defining the dimensionless ratio a = (T_p / T_t):

U = (1 / 1 + 2a)

The Implications of `a`:

When a ll 1 (Local Area Networks): Propagation distance is short, T_p is tiny compared to T_t. Utilization approaches 100\%.
When a gg 1 (Wide Area & Satellite Links): Physical distance is large, so T_p dominates. Utilization collapses towards 0\%.

3. The Bandwidth-Delay Product (BDP)

Upgrading bandwidth B reduces T_t, which actually increases a. The pipe can hold vast amounts of data in transit, but Stop-and-Wait leaves the entire link starved.

To saturate high-latency links, modern transport layers use Sliding Window Protocols (Go-Back-N, Selective Repeat, and TCP) to pipeline multiple frames continuously.

Explore our interactive space-time protocol ladder with live packet flights at Binary Dose.

DEV Community: Binary Dose

More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement

More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement

1. The Mathematical Counterexample

Trace A: 3 Page Frames

Trace B: 4 Page Frames

2. Why FIFO Suffers: The Lack of Locality

3. Why LRU Is Immune: The Stack Inclusion Property

Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes

Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes

1. The Timestamp Precedence Rule

2. The Wait-Die Scheme (Non-Preemptive)

Intuition:

3. The Wound-Wait Scheme (Preemptive)

4. Preventing Starvation

Behind Routing Tables: CIDR and the Longest Prefix Match Rule

Behind Routing Tables: CIDR and the Longest Prefix Match Rule

1. CIDR and Route Aggregation (Supernetting)

2. The Overlapping Route Dilemma

3. The Longest Prefix Match Rule

Hardware Implementation:

The Cost of Virtual Memory: TLBs and Effective Memory Access Time

The Cost of Virtual Memory: TLBs and Effective Memory Access Time

1. The Two-Access Penalty

2. The Translation Lookaside Buffer (TLB)

3. Effective Memory Access Time (EMAT) Formula

Worked Example:

Why OS Virtual Memory Paging Saved LLM Inference: The vLLM Breakthrough

Why OS Virtual Memory Paging Saved LLM Inference: The vLLM Breakthrough

1. The Contiguous Allocation Problem

Two Forms of Memory Waste:

2. The PagedAttention Architecture

3. Copy-on-Write for Prompt Sharing

Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing

Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing

1. The Fan-Out Problem in Standard B-Trees

The Math:

2. Linked Leaf Nodes for Sequential Range Queries

In a B-Tree:

In a B+ Tree:

The Math of Collisions: Pure ALOHA vs Slotted ALOHA Efficiency

The Math of Collisions: Pure ALOHA vs Slotted ALOHA Efficiency

1. Pure ALOHA: S = G · e^-2G

The Vulnerability Period (2 · T_f):

2. Slotted ALOHA: S = G · e^-G

Halving the Vulnerability Window:

Mutex vs Spinlock: When Should a Thread Sleep or Spin?

Mutex vs Spinlock: When Should a Thread Sleep or Spin?

1. Mutex: Sleep-Waiting with Strict Ownership

Mechanics:

The Overhead Cost:

2. Spinlock: Busy-Waiting with Atomic Hardware

Advantages & Disadvantages:

3. The Mathematical Rule of Thumb

Graphing Database Conflicts: How Precedence Graphs Prove Serializability

Graphing Database Conflicts: How Precedence Graphs Prove Serializability

1. What Makes Two Operations Conflict?

The Conflict Matrix:

2. Constructing the Precedence Graph

3. The Serializability Theorem

Sliding Window Sizing: Why Go-Back-N and Selective Repeat Limit Window Sizes

Sliding Window Sizing: Why Go-Back-N and Selective Repeat Limit Window Sizes

1. Go-Back-N ARQ: W_s ≤ 2^m - 1

The Ambiguity Proof (Why W_s = 2^m Fails):

2. Selective Repeat ARQ: W_s + W_r ≤ 2^m

The Ambiguity Constraint:

Behind ACID: How Databases Actually Implement the 4 Guarantees

Behind ACID: How Databases Actually Implement the 4 Guarantees

1. Atomicity: The Undo Log

Implementation:

2. Consistency: Declarative Constraints

Implementation:

3. Isolation: Concurrency Control (2PL vs MVCC)

Implementation:

4. Durability: Write-Ahead Logging (WAL)

Implementation:

Why 10Gbps Links Feel Slow: Stop-and-Wait ARQ Efficiency Formula Explained

Why 10Gbps Links Feel Slow: Stop-and-Wait ARQ Efficiency Formula Explained

1. Transmission Delay vs Propagation Delay

2. Deriving the Efficiency Formula: U = (1 / 1 + 2a)

1. Pure ALOHA: `S = G · e^-2G`

The Vulnerability Period (`2 · T_f`):

2. Slotted ALOHA: `S = G · e^-G`

1. Go-Back-N ARQ: `W_s ≤ 2^m - 1`

The Ambiguity Proof (Why `W_s = 2^m` Fails):

2. Selective Repeat ARQ: `W_s + W_r ≤ 2^m`

2. Deriving the Efficiency Formula: `U = (1 / 1 + 2a)`

The Implications of `a`: