DEV Community: 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.

Why Do Page Faults Happen? The Demand Paging Lifecycle

Binary Dose — Thu, 05 Nov 2026 12:23:25 +0000

Why Do Page Faults Happen? The Demand Paging Lifecycle

When an operating system launches a 2GB application, it does not copy 2GB of machine code from your SSD into physical RAM.

Instead, modern kernels practice Demand Paging—pages of memory are loaded lazily, only when the CPU actually attempts to read or execute an address in that page.

⚡ The 6-Step Page Fault Sequence

[ CPU ] ──(Virtual Address)──► [ MMU ]
                                   │ (Valid Bit = 0)
                                   ▼
                            [ TRAP #14 ]
                                   │
                                   ▼
                 [ OS Kernel: Page Fault Handler ]
                                   │
         ┌─────────────────────────┴─────────────────────────┐
         ▼                                                   ▼
[ Free Frame Allocation ]                         [ Disk DMA Read (4KB) ]
         │                                                   │
         └─────────────────────────┬─────────────────────────┘
                                   ▼
                     [ Page Table: Valid = 1 ]
                                   │
                                   ▼
                      [ Restart Instruction ]

1. MMU Translation Failure

When the CPU references an address whose Page Table Entry (PTE) has Valid = 0, the Memory Management Unit (MMU) halts address translation.

2. Hardware Trap #14

The CPU triggers Hardware Exception Trap #14 (Page Fault Exception), elevating privileges from User Mode (Ring 3) to Kernel Mode (Ring 0).

3. Frame Allocation & Disk DMA

The kernel allocates a free physical frame (or evicts one via LRU/Clock algorithms). It then initiates an asynchronous DMA transfer to copy the missing 4KB page from disk into physical RAM.

4. Page Table Update & Restart

The kernel marks Valid = 1, stores the new physical frame address in the PTE, and restarts the faulting instruction. The user program never knows the page was missing!

🔍 Major vs Minor Page Faults

In production systems, not all page faults touch physical disk:

Minor Page Fault: The page is already in physical memory (e.g., shared library like libc already mapped by another process, or an unallocated zero-fill page). No disk I/O is required!
Major Page Fault: The page must be physically fetched from storage via disk DMA. Stalls the thread for milliseconds (100,000× slower than RAM access).

🚀 Simulate Virtual Memory & Page Faults Interactively

Want to step through the MMU translation process, trigger Trap #14, and inspect page table residency live?

👉 Test the interactive Virtual Memory and Demand Paging simulator on Binary Dose.

Discrete Mathematics for Computer Science: The 10-Module Zero-Fluff Roadmap

Binary Dose — Thu, 05 Nov 2026 10:47:18 +0000

Discrete Mathematics is often taught as an abstract chore—pages of Greek symbols, detached lemma statements, and dry textbook proofs.

Yet underneath the notation, Discrete Mathematics is the invisible engine that powers modern computer systems:

Relational Databases (SQL) are formal implementations of Codd's Relational Model built directly on Cartesian products, binary relations, and relational algebra.
Compiler Type Checkers model subtyping and inheritance hierarchies as partially ordered sets (Posets) and type lattices (LUB / GLB).
Public-Key Cryptography (RSA, Diffie-Hellman, ECC) relies on cyclic groups, modular arithmetic, and Lagrange's Theorem.
Garbage Collectors & Distributed Networks execute graph connectivity algorithms, cycle detection, and spanning tree protocols.

Today, we are thrilled to launch the complete Discrete Mathematics (DM) course on Binary Dose—featuring 10 modules, 31 topics, zero fluff, and rigorous mathematical intuition.

The 10-Module Curriculum Overview

Phase 1: Set Theory, Relations & Functions

Module 01: Set Theory & Cardinality — Roster vs set-builder notation, the nested number hierarchy (mathbbN ⊂ mathbbZ ⊂ mathbbQ ⊂ mathbbR ⊂ mathbbC), Cantor's diagonal argument, countable vs uncountable infinities, and power set cardinality |mathcalP(A)| = 2ⁿ.
Module 02: Binary Relations, Closures & Equivalence Classes — Cartesian products, reflexive, symmetric, transitive, and antisymmetric properties, matrix representation, Warshall's transitive closure algorithm, and equivalence partitions.
Module 03: Functions, Bijections & the Pigeonhole Principle — Injective, surjective, and bijective mappings, function composition, inverse functions, and Dirichlet's generalized Pigeonhole Principle.

Phase 2: Order Theory & Algebraic Structures

Module 04: Partially Ordered Sets (Posets) & Lattice Theory — Partial orders, Hasse diagram construction, maximal/minimal vs greatest/least elements, upper and lower bounds (LUB / GLB), bounded, distributive, complemented, and Boolean lattices.
Module 05: Group Theory & Algebraic Structures — Algebraic hierarchy (Semigroups → Monoids → Groups → Abelian Groups), permutation groups, cyclic groups and generators, subgroups, cosets, and Lagrange's Theorem (|H| divides |G|).

Phase 3: Formal Logic & Inference Engines

Module 06: Propositional Logic & Inference Rules — Truth tables, logical connectives, tautologies, conditional implications (Converse, Inverse, Contrapositive), CNF/DNF normal forms, Modus Ponens, and Resolution refutation.
Module 07: First-Order Predicate Logic & Quantifiers — Universal (∀) and existential (∃) quantifiers, domain of discourse, De Morgan quantifier negation laws, nested quantifier order-dependence, and Prenex Normal Form.

Phase 4: Combinatorics & Recurrence Relations

Module 08: Combinatorics, Recurrences & Generating Functions — Rule of Sum/Product, permutations, combinations, Stars & Bars, solving linear recurrence relations via characteristic roots, and ordinary generating functions.

Phase 5: Graph Theory Foundations & Advanced Topologies

Module 09: Graph Theory Foundations, Paths & Connectivity — Handshaking Lemma (sum deg(v) = 2|E|), adjacency/incidence matrices, subgraphs, graph isomorphisms, walks, paths, cycles, cut-vertices, and bridges.
Module 10: Advanced Graph Theory: Trees, Planarity & Coloring — Tree properties, Cayley's formula (nⁿ-2 spanning trees), Eulerian paths (Euler's Theorem) vs Hamiltonian cycles, Planar graphs and Euler's Polyhedral Formula (V - E + R = 2), Kuratowski's non-planar minors (K₅, K₃,3), and chromatic numbers.

Access the Course for Free

The entire curriculum is free and available with no paywalls or sign-ups required.

👉 Start reading today: binarydose.in/coredose/discrete-math

Atomic Hardware Instructions: Test-and-Set (TSL) vs Compare-and-Swap (CAS)

Binary Dose — Wed, 04 Nov 2026 20:34:56 +0000

Atomic Hardware Instructions: Test-and-Set (TSL) vs Compare-and-Swap (CAS)

Every beginner systems programmer eventually attempts to build a mutual exclusion lock using a simple global boolean flag:

volatile int lock = 0;

void acquire() {
    while (lock == 1); // 1. Spin until lock is free
    lock = 1;          // 2. Set the lock
}

void release() {
    lock = 0;
}

On paper, this looks intuitive. In production silicon, it fails catastrophically.

⚡ The Disastrous Race Condition

The fundamental flaw is that testing the lock and setting the lock are two separate, interruptible assembly instructions:

[ Core 1: Thread A ]                       [ Core 2: Thread B ]
         │                                          │
         ├─ 1. Reads lock (0: Free)                 │
         │  (Preempted / Interrupted!)              │
         │                                          ├─ 2. Reads lock (0: Free)
         │                                          ├─ 3. Writes lock = 1
         │                                          ├─ 4. Enters Critical Section!
         ├─ 5. Resumes! Writes lock = 1             │
         ├─ 6. Enters Critical Section! (💥 DUPLICATE ENTRY)

Both threads enter the critical section concurrently, corrupting shared memory.

🛡️ Atomic Hardware Instructions

To solve this, CPU chip designers introduced hardware-level instructions that perform read-modify-write operations atomically in a single indivisible bus transaction:

1. Test-and-Set Lock (TSL)

On x86 architectures (via BTS or XCHG with the LOCK prefix):

TSL Register, LockVar

In a single clock cycle, the CPU:

Locks the shared memory bus (or asserts cache line exclusivity via MESI protocol).
Copies the current value of LockVar into the CPU register.
Overwrites LockVar with 1.
Releases the bus.

Because no other CPU core can access the memory address between the read and the write, mutual exclusion is physically guaranteed!

2. Compare-and-Swap (CAS)

Represented by CMPXCHG on x86, CAS is the universal primitive behind all modern lock-free programming:

bool CAS(int *addr, int expected, int new_value) {
    if (*addr == expected) {
        *addr = new_value;
        return true;
    }
    return false;
}

If another core modified the variable in the background, CAS fails safely without locking, allowing the caller to retry in a lock-free loop.

Trace atomic memory bus locks on Binary Dose.

Why Ethernet Mandates a 64-Byte Minimum Packet: CSMA/CD Explained

Binary Dose — Wed, 04 Nov 2026 12:10:25 +0000

Why Ethernet Mandates a 64-Byte Minimum Packet: CSMA/CD Explained

Have you ever wondered why Ethernet (IEEE 802.3) forbids packets smaller than 64 bytes?

If you try to transmit a 20-byte payload, your network interface card (NIC) forcibly injects padding bytes to reach that exact 64-byte threshold.

This is not arbitrary protocol overhead—it is a physical law required by CSMA/CD (Carrier Sense Multiple Access with Collision Detection).

⚡ The Worst-Case Collision Dilemma

Over a shared copper cable, electromagnetic signals travel at a finite propagation speed: roughly 2 × 10⁸ m/s (about two-thirds the speed of light).

Let the propagation time between the two farthest hosts (A and B) be Tₚ:

Time t = 0:          [ Host A ] ────(Signal in Transit ➔)─────── [ Host B ]
Time t = Tp - ε:     [ Host A ] ──────────────────────(⚡ Collision!) [ Host B ]
Time t = 2 * Tp:     [ Host A ] ◄──(Collision Wave Returns)───── [ Host B ]

t = 0: Host A senses the cable is idle and begins transmitting.
t = Tₚ - ε: A fraction of a microsecond before A's signal reaches Host B, Host B checks the cable. Because A's signal hasn't arrived yet, B senses an idle line and starts transmitting!
Collision: Signals collide near Host B.
Collision Echo: The resulting abnormal voltage spike propagates backward across the cable toward Host A.
t = 2 × Tₚ: The collision echo finally reaches Host A.

THE GOLDEN INVARIANT:
Host A can only detect a collision if it is still actively transmitting bits when the collision echo returns! If A finished sending early, it cleared its transmit buffer and assumed total success.

📐 Deriving the 64-Byte Requirement

To guarantee that transmission time Tₜ is long enough to detect the worst-case collision echo:

Transmission Time (Tt) >= Round-Trip Time (2 * Tp)

Since Tt = Frame_Length (L) / Bandwidth (B):
L / B >= 2 * Tp  ==>  L_min = 2 * Tp * B

In standard 10 Mbps Ethernet:

Round-Trip Time (2 × Tₚ) over a maximum 2.5 km network = 51.2 μs.
L_min = 51.2 μs × 10,000,000 bits/s = 512 bits = 64 bytes!

🛠️ Truncated Binary Exponential Backoff

When a collision occurs, both hosts jam the wire and back off using:

# After n collisions (up to 10):
k = random.randint(0, 2**min(n, 10) - 1)
wait_time = k * 51.2  # microseconds (slot time)

Doubling the slot range on every collision prevents immediate re-collisions.

🚀 Experience the Live Space-Time Collision Simulator

Want to see electromagnetic propagation delay, collision waves, and exponential backoff animated live?

👉 Test the interactive CSMA/CD space-time simulator on Binary Dose.

How Operating Systems Avoid Deadlocks: Dijkstra's Banker's Algorithm

Binary Dose — Tue, 03 Nov 2026 20:19:25 +0000

How Operating Systems Avoid Deadlocks: Dijkstra's Banker's Algorithm

In multiprogramming systems, allocating shared hardware resources (CPU cores, GPUs, disk drives, mutexes) is a delicate balancing act.

Grant a request too eagerly, and you risk an unrecoverable system freeze.

In 1965, Edsger W. Dijkstra formulated the Banker's Algorithm—an algorithm named by analogy with a small-town banker managing revolving lines of cash credit.

⚡ Safe State vs Unsafe State vs Deadlock

A common misconception is that an Unsafe State is a deadlock. It is not!

┌────────────────────────────────────────────────────────┐
│                   ALL SYSTEM STATES                    │
│  ┌──────────────────────────────────────────────────┐  │
│  │                   UNSAFE STATES                  │  │
│  │       ┌──────────────────────────────────┐       │  │
│  │       │             DEADLOCK             │       │  │
│  │       └──────────────────────────────────┘       │  │
│  └──────────────────────────────────────────────────┘  │
│  ┌──────────────────────────────────────────────────┐  │
│  │                   SAFE STATES                    │  │
│  │   (Guaranteed Deadlock-Free Execution Sequence)   │  │
│  └──────────────────────────────────────────────────┘  │
└────────────────────────────────────────────────────────┘

Safe State: There exists at least one order where every process can obtain its maximum needed resources, finish execution, and release all locks.
Unsafe State: Not yet deadlocked, but the OS can no longer guarantee that a worst-case spike in resource claims won't cause a deadlock.
Deadlock: A closed dependency cycle has formed. No forward progress is possible.

🧠 The Safety Algorithm in 4 Steps

For n processes and m resource types:

Available[m]: Number of unallocated instances.
Allocation[n][m]: Resources currently held by each process.
Max[n][m]: Peak demand declared by each process.
Need[n][m] = Max[n][m] - Allocation[n][m]: Remaining claim.

# The Safety Check Loop
work = available.copy()
finish = [False] * num_processes

while True:
    # Find process whose remaining Need can be satisfied by Work
    found = False
    for p in range(num_processes):
        if not finish[p] and all(need[p][r] <= work[r] for r in range(num_resources)):
            work += allocation[p]  # Process finishes and returns resources!
            finish[p] = True
            safe_sequence.append(p)
            found = True
            break
    if not found:
        break

# If all finish == True, system is in a SAFE STATE!

🚀 Why Modern Cloud Kernels Avoid Strict Avoidance

Banker's Algorithm requires every process to declare its maximum resource needs in advance. In modern web servers and container runtimes with dynamic workloads, predicting peak memory or socket usage upfront is nearly impossible.

Instead, production kernels use Deadlock Detection and Preemption.

🛠️ Step Through Banker's Algorithm Interactively

Want to test custom Allocation, Max, and Available matrices and watch the safety sequence calculate live?

👉 Solve custom Banker's Algorithm matrices on the interactive Binary Dose simulator.

How Databases Safely Ignore Obsolete Writes: Thomas Write Rule Explained

Binary Dose — Tue, 03 Nov 2026 11:57:17 +0000

How Databases Safely Ignore Obsolete Writes: Thomas Write Rule Explained

In distributed databases and concurrency control, standard locking mechanisms (like 2PL) can cause painful deadlock cycles and lock contention.

To solve this, database engines use Timestamp Ordering (TSO): transactions execute lock-free, ordered by logical timestamps TS(T).

⚡ The Standard Timestamp Ordering Conflict

For every data record Q, the database tracks two timestamps:

R-TS(Q): The largest timestamp of any transaction that read Q.
W-TS(Q): The largest timestamp of any transaction that wrote to Q.

Under standard Timestamp Ordering, when an older transaction T₁ (TS = 10) attempts to execute write(Q) after a newer transaction T₂ (TS = 20) has already updated Q:

Time ────────────────────────────────────────────────────────►
T1 (TS = 10) ──── attempts write(Q) ───► 💥 CONFLICT!
T2 (TS = 20) ──── already executed write(Q) [W-TS(Q) = 20]

Standard TSO says:

"You are an older transaction attempting to overwrite a newer value. Abort and rollback T₁!"

Rolling back transactions wastes CPU cycles, bandwidth, and increases user latency.

🧠 The Thomas Write Rule Breakthrough

In 1979, Robert H. Thomas realized that under one specific condition, aborting T₁ is completely unnecessary:

IF:
   TS(T) < W-TS(Q)   (A newer transaction already wrote Q)
AND:
   TS(T) >= R-TS(Q)  (No transaction with TS > TS(T) has read Q!)

THEN:
   DO NOT ABORT T.
   SIMPLY IGNORE / DISCARD THE WRITE!

Why Can We Safely Ignore the Write?

The value that T₁ wanted to write was destined to be immediately overwritten by T₂ anyway.
Because no intermediate transaction ever read T₁'s value, skipping T₁'s write produces the exact same final database state as if T₁ had executed first!
T₁ continues executing without incurring a costly rollback.

🚀 View Serializability vs Conflict Serializability

Thomas Write Rule is famous in database theory because it generates schedules that are View Serializable but NOT Conflict Serializable:

Schedule S:
T1: read(A)                write(A) (ignored!)
T2:          write(A)
────────────────────────────────────────────────────────►
Result: Valid view-equivalent schedule without aborting T1!

🛠️ Step Through the Live Simulator

Want to inspect timestamp comparisons, simulate out-of-order writes, and test Thomas Write Rule interactively?

👉 Step through the interactive concurrency schedule simulator on Binary Dose.

DEV Community: Binary Dose

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)

The Implications of a:

3. The Bandwidth-Delay Product (BDP)

Why Do Page Faults Happen? The Demand Paging Lifecycle

Why Do Page Faults Happen? The Demand Paging Lifecycle

⚡ The 6-Step Page Fault Sequence

1. MMU Translation Failure

2. Hardware Trap #14

3. Frame Allocation & Disk DMA

4. Page Table Update & Restart

🔍 Major vs Minor Page Faults

🚀 Simulate Virtual Memory & Page Faults Interactively

Discrete Mathematics for Computer Science: The 10-Module Zero-Fluff Roadmap

The 10-Module Curriculum Overview

Phase 1: Set Theory, Relations & Functions

Phase 2: Order Theory & Algebraic Structures

Phase 3: Formal Logic & Inference Engines

Phase 4: Combinatorics & Recurrence Relations

Phase 5: Graph Theory Foundations & Advanced Topologies

Access the Course for Free

Atomic Hardware Instructions: Test-and-Set (TSL) vs Compare-and-Swap (CAS)

Atomic Hardware Instructions: Test-and-Set (TSL) vs Compare-and-Swap (CAS)

⚡ The Disastrous Race Condition

🛡️ Atomic Hardware Instructions

1. Test-and-Set Lock (TSL)

2. Compare-and-Swap (CAS)

Why Ethernet Mandates a 64-Byte Minimum Packet: CSMA/CD Explained

Why Ethernet Mandates a 64-Byte Minimum Packet: CSMA/CD Explained

⚡ The Worst-Case Collision Dilemma

📐 Deriving the 64-Byte Requirement

🛠️ Truncated Binary Exponential Backoff

🚀 Experience the Live Space-Time Collision Simulator

How Operating Systems Avoid Deadlocks: Dijkstra's Banker's Algorithm

How Operating Systems Avoid Deadlocks: Dijkstra's Banker's Algorithm

⚡ Safe State vs Unsafe State vs Deadlock

🧠 The Safety Algorithm in 4 Steps

🚀 Why Modern Cloud Kernels Avoid Strict Avoidance

🛠️ Step Through Banker's Algorithm Interactively

How Databases Safely Ignore Obsolete Writes: Thomas Write Rule Explained

How Databases Safely Ignore Obsolete Writes: Thomas Write Rule Explained

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`: