2021
73 posts from 2021
Abstract Interpretation: Cousot's Galois Connection Framework, Widening/Narrowing, and Sound Static Analysis by Construction
2021-12-29A deep exploration of abstract interpretation—the mathematical theory of sound approximation that underpins every modern static analyzer, from the Astrée system to the Rust borrow checker.
The Complexity Of The Network Simplex Algorithm For Minimum Cost Flow
2021-12-23A comprehensive technical exploration of the complexity of the network simplex algorithm for minimum cost flow, covering key concepts, practical implementations, and real-world applications.
Domain Theory: Scott's D∞ Construction, Solving Recursive Domain Equations, and the Foundations of Denotational Semantics
2021-12-19An in-depth exploration of domain theory—Scott's construction of a universal domain D∞ isomorphic to its own function space, continuous lattices, and how these ideas gave birth to denotational semantics.
A Deep Dive Into The Hat Trie: Array Compressed Trie With Efficient Cache Locality
2021-12-18A comprehensive technical exploration of a deep dive into the hat trie: array compressed trie with efficient cache locality, covering key concepts, practical implementations, and real-world applications.
Implementing A Van Emde Boas Tree For Predecessor Queries In O(Log Log U) Time
2021-12-13A comprehensive technical exploration of implementing a van emde boas tree for predecessor queries in o(log log u) time, covering key concepts, practical implementations, and real-world applications.
The Algorithm For Building A Fibonacci Heap With Decrease Key And Meld In Logarithmic Time
2021-12-06A comprehensive technical exploration of the algorithm for building a fibonacci heap with decrease key and meld in logarithmic time, covering key concepts, practical implementations, and real-world applications.
Building A Self Balancing Binary Search Tree With Weighted Average Rotation (Wavl) For Better Worst Case Balance
2021-12-01A comprehensive technical exploration of building a self balancing binary search tree with weighted average rotation (wavl) for better worst case balance, covering key concepts, practical implementations, and real-world applications.
The Performance Of Binary Search Trees: Treap, Splay Tree, Red Black Tree, And Avl Tree Under Random And Sequential Access
2021-11-18A comprehensive technical exploration of the performance of binary search trees: treap, splay tree, red black tree, and avl tree under random and sequential access, covering key concepts, practical implementations, and real-world applications.
A Detailed Analysis Of The Quickunion Disjoint Set Union Data Structure With Path Compression And Union By Rank
2021-11-04A comprehensive technical exploration of a detailed analysis of the quickunion disjoint set union data structure with path compression and union by rank, covering key concepts, practical implementations, and real-world applications.
Implementing An Exact Cover Solver Using Dancing Links (Knuth’S Algorithm X)
2021-10-30A comprehensive technical exploration of implementing an exact cover solver using dancing links (knuth’s algorithm x), covering key concepts, practical implementations, and real-world applications.
The Complexity Of The Isomorphism Problem For Graphs: Subgraph Isomorphism Via Color Refinement
2021-10-19A comprehensive technical exploration of the complexity of the isomorphism problem for graphs: subgraph isomorphism via color refinement, covering key concepts, practical implementations, and real-world applications.
Game Semantics: Fully Abstract Models of PCF, AJM Games, and Strategies as Sheaves
2021-09-30A rigorous exploration of game semantics—the technique that cracked the full abstraction problem for PCF by modeling computation as dialogue between Player and Opponent.
Linear Logic: Girard's Resource-Sensitive Logic, Exponential Modalities, and Linear Types in Rust
2021-09-29A comprehensive exploration of linear logic's resource-conscious foundations, proof nets, the ! and ? modalities translating intuitionistic to linear, and how Rust's ownership system mirrors these ideas.
A Rigorous Proof Of The No Free Lunch Theorem In Optimization: Convex Vs. Non Convex Landscapes
2021-09-28A comprehensive technical exploration of a rigorous proof of the no free lunch theorem in optimization: convex vs. non convex landscapes, covering key concepts, practical implementations, and real-world applications.
Building A Distributed Sampler From Scratch: Parallel Mcmc With Consensus And Mode Seeking
2021-09-24A comprehensive technical exploration of building a distributed sampler from scratch: parallel mcmc with consensus and mode seeking, covering key concepts, practical implementations, and real-world applications.
The Mathematical Foundations Of The Metropolis Hastings Algorithm For Markov Chain Monte Carlo
2021-09-17A comprehensive technical exploration of the mathematical foundations of the metropolis hastings algorithm for markov chain monte carlo, covering key concepts, practical implementations, and real-world applications.
Implementing A Finger Table For Consistent Hashing With Replication And Fault Tolerance
2021-09-11A comprehensive technical exploration of implementing a finger table for consistent hashing with replication and fault tolerance, covering key concepts, practical implementations, and real-world applications.
The Performance Of Minimal Perfect Hashing: Chd Algorithm, Empirical Hash Seeds, And Space Efficiency
2021-09-06A comprehensive technical exploration of the performance of minimal perfect hashing: chd algorithm, empirical hash seeds, and space efficiency, covering key concepts, practical implementations, and real-world applications.
A Deep Dive Into The Cuckoo Filter: Lower Memory Footprint Than Bloom Filters And Deletion Support
2021-08-28A comprehensive technical exploration of a deep dive into the cuckoo filter: lower memory footprint than bloom filters and deletion support, covering key concepts, practical implementations, and real-world applications.
The Design Of A Probabilistic Skip List With Path Compression And Concurrency Support
2021-08-24A comprehensive technical exploration of the design of a probabilistic skip list with path compression and concurrency support, covering key concepts, practical implementations, and real-world applications.
Optimizing Distributed Consensus: Comparing Fast Paxos, Epaxos, And Multi Paxos In Wan Deployments With Latency Benchmarks
2021-08-20A comprehensive technical exploration of optimizing distributed consensus, comparing Fast Paxos, Epaxos, and Multi Paxos in WAN deployments with latency benchmarks, covering key concepts, practical implementations, and real-world applications.
Implementing A Bloom Filter Cascade For Efficient Set Intersection And Summarization
2021-08-16A comprehensive technical exploration of implementing a bloom filter cascade for efficient set intersection and summarization, covering key concepts, practical implementations, and real-world applications.
Branch Prediction and Speculative Execution: How Modern CPUs Gamble on the Future
2021-08-15Explore how modern processors predict branch outcomes and execute instructions speculatively, the algorithms behind branch predictors, the performance implications for your code, and the security vulnerabilities like Spectre that emerged from these optimizations.
A Thorough Explanation Of The Hyperloglog Algorithm: Counting Cardinalities With Log Log Estimation And Bias Correction
2021-08-12A comprehensive technical exploration of a thorough explanation of the hyperloglog algorithm: counting cardinalities with log log estimation and bias correction, covering key concepts, practical implementations, and real-world applications.
Virtual Memory and Page Tables: How Operating Systems Manage Memory
2021-08-12A comprehensive exploration of virtual memory systems, page tables, address translation, and the hardware-software collaboration that enables modern multitasking. Understand TLBs, page faults, and memory protection.
Homotopy Type Theory: The Univalence Axiom, Higher Inductive Types, and ∞-Groupoids
2021-08-11A deep dive into the univalent foundations of mathematics, where equality is homotopy, types are spaces, and the universe mirrors the ∞-groupoid of all ∞-groupoids.
Category Theory for Programmers: Functors, Monads, and Natural Transformations
2021-08-10A rigorous yet intuitive journey through the categorical structures that secretly power functional programming—from categories and functors to adjunctions and the monad-as-monoid correspondence.
Building A Count Min Sketch With Conservative Update For Heavy Hitters In Network Traffic
2021-08-07A comprehensive technical exploration of building a count min sketch with conservative update for heavy hitters in network traffic, covering key concepts, practical implementations, and real-world applications.
The Algorithm Of The T Digest: Order Statistics, Merging, And Quantile Approximations For Streaming Data
2021-08-04A comprehensive technical exploration of the algorithm of the t digest: order statistics, merging, and quantile approximations for streaming data, covering key concepts, practical implementations, and real-world applications.
State Machine Replication: Viewstamped Replication Protocol, Zab (ZooKeeper Atomic Broadcast), and the Consensus-Scalability Continuum
2021-07-27A deep exploration of state machine replication — how Viewstamped Replication and Zab enable fault-tolerant services through ordered command execution, and how the consensus-scalability continuum shapes modern distributed systems design.
Designing A Time Series Database With Downsampling And Continuous Aggregates: Timescaledb Internals
2021-07-23A comprehensive technical exploration of designing a time series database with downsampling and continuous aggregates: timescaledb internals, covering key concepts, practical implementations, and real-world applications.
Streaming Systems: Apache Flink Checkpointing, Kafka Log Compaction, Watermarks and Event-Time Processing, and Exactly-Once Semantics
2021-07-22A deep exploration of streaming systems — how Flink's distributed checkpointing provides exactly-once state consistency, how Kafka's log compaction enables durable event storage, and how watermarks solve the event-time vs processing-time dilemma.
A Formal Analysis Of Multi Version Concurrency Control (Mvcc) In Postgresql: Snapshots, Garbage Collection, And Serializable Isolation
2021-07-17A comprehensive technical exploration of a formal analysis of multi version concurrency control (mvcc) in postgresql: snapshots, garbage collection, and serializable isolation, covering key concepts, practical implementations, and real-world applications.
Implementing A B+ Tree With Bulk Loading And Prefix Compression For Write Optimized Databases
2021-07-16A comprehensive technical exploration of implementing a b+ tree with bulk loading and prefix compression for write optimized databases, covering key concepts, practical implementations, and real-world applications.
B-Trees and LSM-Trees: The Foundations of Modern Storage Engines
2021-07-14An in-depth exploration of B-Trees and LSM-Trees, the two dominant data structures powering databases from PostgreSQL to RocksDB. Learn their trade-offs, internal mechanics, and when to choose each for your workload.
The Performance Of Database Caching Strategies: Lru, Clock, Arc, And 2Q Under Real World Workloads
2021-07-06A comprehensive technical exploration of the performance of database caching strategies: lru, clock, arc, and 2q under real world workloads, covering key concepts, practical implementations, and real-world applications.
Columnar Storage: Parquet Encoding, ORC Stripe Format, Apache Arrow In-Memory Columnar Format, Predicate Pushdown, and SIMD Scans
2021-07-03A deep exploration of columnar data formats — how Parquet and ORC organize data column-by-column for efficient analytics, Apache Arrow's in-memory representation for zero-copy data interchange, and the vectorized execution that makes modern query engines fast.
CPU Caches and Memory Hierarchy: The Hidden Architecture Behind Performance
2021-06-22A deep exploration of CPU cache architecture, from L1 to L3 caches, cache lines, associativity, replacement policies, and cache coherence. Learn how memory hierarchy shapes modern software performance.
Object Storage: RADOS/Ceph Architecture, the CRUSH Placement Algorithm, S3 API Semantics, and Erasure Coding at Scale
2021-06-21A deep exploration of object storage — how Ceph's RADOS and CRUSH algorithm enable scalable, self-managing storage clusters, the S3 API's influence on cloud storage, and how erasure coding reduces storage overhead.
Building A Distributed Log Structured Storage Engine: Wiredtiger’S B Tree And Concurrency Control
2021-06-19A comprehensive technical exploration of building a distributed log structured storage engine: wiredtiger’s b tree and concurrency control, covering key concepts, practical implementations, and real-world applications.
Distributed File Systems: GFS Design, HDFS Architecture, the Colossus Evolution, and Single-Master Metadata Bottlenecks
2021-06-18A deep exploration of distributed file systems — how Google's GFS pioneered the single-master model, how HDFS adapted it for the Hadoop ecosystem, and how modern systems have evolved beyond the single-master bottleneck.
Persistent Memory Programming: DAX Mappings, PMDK Libraries, Crash Consistency Without Write-Ahead Logging, and the Optane Legacy
2021-06-14A deep exploration of persistent memory — how DAX enables direct byte-addressable access to non-volatile memory, how the PMDK libraries solve the crash consistency problem at the instruction level, and the lessons of Intel Optane.
A Deep Dive Into The R Tree Spatial Index: Guttman’S Algorithm, Node Splitting, And R* Tree Variants
2021-06-13A comprehensive technical exploration of a deep dive into the r tree spatial index: guttman’s algorithm, node splitting, and r* tree variants, covering key concepts, practical implementations, and real-world applications.
The Implementation Of A Columnar Storage Format: Parquet Compression, Dictionary Encoding, And Row Groups
2021-06-13A comprehensive technical exploration of the implementation of a columnar storage format: parquet compression, dictionary encoding, and row groups, covering key concepts, practical implementations, and real-world applications.
Designing A Graph Database With Native Storage: Adjacency Lists, Property Graphs, And Traversal Optimization
2021-06-02A comprehensive technical exploration of designing a graph database with native storage: adjacency lists, property graphs, and traversal optimization, covering key concepts, practical implementations, and real-world applications.
NVMe and the Storage Stack: The NVMe Command Set, Submission/Completion Queues, SPDK, and the Death of the SCSI/SATA Bottleneck
2021-05-31A deep exploration of NVMe technology — how the command set and queue model eliminate the SCSI bottleneck, and why user-space storage via SPDK achieves microsecond-latency I/O on commodity flash.
Instrumenting Without Spying: Privacy-Preserving Telemetry at Scale
2021-05-27How we rebuilt our telemetry pipeline to respect user privacy without sacrificing insight.
A Detailed Analysis Of The Pagerank Algorithm: Power Iteration, Damping Factor, And Personalization
2021-05-25A comprehensive technical exploration of a detailed analysis of the pagerank algorithm: power iteration, damping factor, and personalization, covering key concepts, practical implementations, and real-world applications.
Implementing A K D Tree For Nearest Neighbor Search With Balanced Construction And Bounded Box Test
2021-05-18A comprehensive technical exploration of implementing a k d tree for nearest neighbor search with balanced construction and bounded box test, covering key concepts, practical implementations, and real-world applications.
The Theory Of Generalization Error In Support Vector Machines: Vc Dimension And Maximal Margin Classifiers
2021-05-17A comprehensive technical exploration of the theory of generalization error in support vector machines: vc dimension and maximal margin classifiers, covering key concepts, practical implementations, and real-world applications.
User-Space Networking: Snabb Switch, FD.io VPP (Vector Packet Processing), AF_XDP, and the Philosophy of Kernel Bypass
2021-05-14A deep exploration of user-space networking — how Snabb, VPP, and AF_XDP achieve line-rate packet processing by bypassing the kernel, and the architectural trade-offs of moving the network data plane into user space.
eBPF Internals: The In-Kernel Verifier, Safety Proofs, JIT Compilation to Native Code, Map Types, and XDP/TC Hooks
2021-05-08A deep exploration of eBPF internals — how the Linux kernel verifier proves safety, the JIT compilers that turn BPF bytecode into native instructions, the map infrastructure that enables stateful processing, and the XDP/TC hooks that make programmable networking possible.
Building A Distributed Machine Learning System: Parameter Server Architecture With Asynchronous Stochastic Gradient Descent
2021-05-05A comprehensive technical exploration of building a distributed machine learning system: parameter server architecture with asynchronous stochastic gradient descent, covering key concepts, practical implementations, and real-world applications.
The Performance Of Attention Mechanisms In Transformers: Self Attention Vs. Multi Headed With Flashattention Optimization
2021-05-01A comprehensive technical exploration of the performance of attention mechanisms in transformers: self attention vs. multi headed with flashattention optimization, covering key concepts, practical implementations, and real-world applications.
A Comprehensive Guide To Quantization Aware Training: Simulated Quantization, Straight Through Estimator, And Calibration
2021-04-30A comprehensive technical exploration of a comprehensive guide to quantization aware training: simulated quantization, straight through estimator, and calibration, covering key concepts, practical implementations, and real-world applications.
Implementing A Neural Network Training Framework With Automatic Differentiation Using Wengert Lists
2021-04-29A comprehensive technical exploration of implementing a neural network training framework with automatic differentiation using wengert lists, covering key concepts, practical implementations, and real-world applications.
Deterministic Monorepo CI Platforms: Engineering Consistency at Scale
2021-04-23A deep guide to building, operating, and evolving reproducible CI/CD systems for large monorepos without sacrificing developer velocity or safety.
System Calls: The Gateway Between User Space and Kernel
2021-04-18An in-depth exploration of how applications communicate with the operating system kernel through system calls. Learn about the syscall interface, context switching, and how modern OSes balance security with performance.
The Mathematics Of Gaussian Processes For Bayesian Optimization: Kernel Selection And Cholesky Factorization
2021-03-26A comprehensive technical exploration of the mathematics of gaussian processes for bayesian optimization: kernel selection and cholesky factorization, covering key concepts, practical implementations, and real-world applications.
Trusted Execution: Intel SGX Enclaves, AMD SEV-SNP, Attestation Protocols, and the Confidential Computing Promise
2021-03-25A deep exploration of trusted execution environments — how SGX and SEV encrypt computation, the attestation protocols that verify enclave integrity, and the promise of confidential computing that protects data even from the cloud operator.
Cache‑Friendly Data Layouts: AoS vs. SoA (and the Hybrid In‑Between)
2021-03-18How memory layout choices shape the performance of your hot loops. A practical guide to arrays‑of‑structs, struct‑of‑arrays, and hybrid layouts across CPUs and GPUs.
Designing An Online Learning Algorithm For Adversarial Bandits: Exp3, Follow The Regularized Leader
2021-03-02A comprehensive technical exploration of designing an online learning algorithm for adversarial bandits: exp3, follow the regularized leader, covering key concepts, practical implementations, and real-world applications.
Capability-Based Security: CHERI Architecture, Hardware Capabilities, Spatial and Referential Safety, and Compartmentalization
2021-02-26A deep exploration of the CHERI capability architecture — how hardware-enforced capabilities provide spatial memory safety, referential integrity, and fine-grained compartmentalization at the instruction level.
The Complexity Of The Edit Distance Problem: Needleman Wunsch, Smith Waterman, And Affine Gap Penalties
2021-02-18A comprehensive technical exploration of the complexity of the edit distance problem: needleman wunsch, smith waterman, and affine gap penalties, covering key concepts, practical implementations, and real-world applications.
A Deep Dive Into The Palindromic Tree (Eertree): Construction And Applications In Stringology
2021-02-17A comprehensive technical exploration of a deep dive into the palindromic tree (eertree): construction and applications in stringology, covering key concepts, practical implementations, and real-world applications.
Implementing A Fast Maximum Matching In General Graphs Using Blossom Algorithm (Edmonds)
2021-02-15A comprehensive technical exploration of implementing a fast maximum matching in general graphs using blossom algorithm (edmonds), covering key concepts, practical implementations, and real-world applications.
The Algorithmics Of Network Flow: Dinic’S Algorithm With Scaling Vs. Push Relabel With Gap Heuristics
2021-02-14A comprehensive technical exploration of the algorithmics of network flow: dinic’s algorithm with scaling vs. push relabel with gap heuristics, covering key concepts, practical implementations, and real-world applications.
Building A Game Theoretic Approach To Distributed Consensus: Rational Players, Payments, And Mechanism Design
2021-02-12A comprehensive technical exploration of building a game theoretic approach to distributed consensus: rational players, payments, and mechanism design, covering key concepts, practical implementations, and real-world applications.
The Performance Of Integer Linear Programming Solvers: Branch And Bound Vs. Cutting Planes For Real World Problems
2021-02-08A comprehensive technical exploration of the performance of integer linear programming solvers: branch and bound vs. cutting planes for real world problems, covering key concepts, practical implementations, and real-world applications.
Implementing A Linear Programming Solver Using The Simplex Algorithm: Degeneracy, Bland’S Rule, And Scaling
2021-02-03A comprehensive technical exploration of implementing a linear programming solver using the simplex algorithm: degeneracy, bland’s rule, and scaling, covering key concepts, practical implementations, and real-world applications.
A Rigorous Analysis Of The Fast Fourier Transform: Cooley Tukey Algorithm With Radix 2 Decimation In Time
2021-01-14A comprehensive technical exploration of a rigorous analysis of the fast fourier transform: cooley tukey algorithm with radix 2 decimation in time, covering key concepts, practical implementations, and real-world applications.
Designing A Randomized Algorithm For The Min Cut Problem: Karger’S Algorithm And Contractions
2021-01-10A comprehensive technical exploration of designing a randomized algorithm for the min cut problem: karger’s algorithm and contractions, covering key concepts, practical implementations, and real-world applications.