2019
74 posts from 2019
Implementing A Cache Oblivious Matrix Multiplication Algorithm With Block Recursive Layouts
2019-12-30A comprehensive technical exploration of implementing a cache oblivious matrix multiplication algorithm with block recursive layouts, covering key concepts, practical implementations, and real-world applications.
Mechanism Design: VCG Auctions, the Revelation Principle, and the Architecture of Truthfulness
2019-12-23A deep exploration of mechanism design—the VCG mechanism, Myerson optimal auction, incentive compatibility, and how to design games where truth-telling is a dominant strategy.
A Quantitative Comparison Of Sorting Algorithms On Modern Cpu Architectures: Radix Sort Vs. Quicksort With Simd
2019-12-11A comprehensive technical exploration of a quantitative comparison of sorting algorithms on modern cpu architectures: radix sort vs. quicksort with simd, covering key concepts, practical implementations, and real-world applications.
Designing A Mapreduce Framework From Scratch: Job Scheduling, Data Locality, And Fault Tolerance
2019-12-04A comprehensive technical exploration of designing a mapreduce framework from scratch: job scheduling, data locality, and fault tolerance, covering key concepts, practical implementations, and real-world applications.
Algorithmic Game Theory: Nash Equilibrium Computation, PPAD-Completeness, and the Computational Lens on Strategy
2019-11-23A rigorous look at algorithmic game theory—computing Nash equilibria, the PPAD complexity class, and how computational constraints reshape strategic reasoning.
Smoothed Analysis: Why Simplex Works in Practice and the Spielman-Teng Framework
2019-11-19An exploration of smoothed analysis—Spielman and Teng's framework that explains why the simplex method and other algorithms transcend their worst-case bounds.
The Algebra Of Concurrent Programming: Modeling With Process Calculi Like Csp And Pi Calculus
2019-11-16A comprehensive technical exploration of the algebra of concurrent programming: modeling with process calculi like csp and pi calculus, covering key concepts, practical implementations, and real-world applications.
Implementing A Work Stealing Task Scheduler With Locality Aware Dequeues In Rust
2019-11-14A comprehensive technical exploration of implementing a work stealing task scheduler with locality aware dequeues in rust, covering key concepts, practical implementations, and real-world applications.
The Empirical Performance Of Spin Locks, Mutexes, And Sleep Locks On Multicore Systems
2019-10-30A comprehensive technical exploration of the empirical performance of spin locks, mutexes, and sleep locks on multicore systems, covering key concepts, practical implementations, and real-world applications.
Building A Concurrent B Tree With Optimistic Lock Coupling And Smo Safety
2019-10-22A comprehensive technical exploration of building a concurrent b tree with optimistic lock coupling and smo safety, covering key concepts, practical implementations, and real-world applications.
Average-Case Complexity: Levin's Distributional Problems, AvgP, and Cryptographic Implications
2019-10-20A deep examination of average-case complexity—Levin's theory of distributional NP-completeness, the class AvgP, and why cryptography needs hard-on-average problems.
Descriptive Complexity: Fagin's Theorem, Logic, and an Alternative to Turing Machines
2019-10-12An exploration of descriptive complexity—where computational classes are characterized by logical definability—and Fagin's theorem that NP equals existential second-order logic.
A Deep Dive Into The Memory Model Of C++11: Acquire Release Semantics And Sequential Consistency
2019-10-11A comprehensive technical exploration of a deep dive into the memory model of c++11: acquire release semantics and sequential consistency, covering key concepts, practical implementations, and real-world applications.
Designing A Transactional Memory System With Hardware Support: Htm Vs. Software Tm On Modern Cpus
2019-10-02A comprehensive technical exploration of designing a transactional memory system with hardware support: htm vs. software tm on modern cpus, covering key concepts, practical implementations, and real-world applications.
Circuit Complexity: AC0, NC, P/poly, and the PARITY ∉ AC0 Proof
2019-09-29A rigorous journey through circuit complexity classes—AC0, NC, P/poly—and the landmark result that PARITY cannot be computed by constant-depth polynomial-size circuits.
The Proof Of Correctness Of The Treiber Stack And Its Aba Problem Mitigation Using Stam’S Schemes
2019-09-26A comprehensive technical exploration of the proof of correctness of the treiber stack and its aba problem mitigation using stam’s schemes, covering key concepts, practical implementations, and real-world applications.
Implementing A Efficient Read Copy Update (Rcu) Mechanism For Linux Kernel Modules
2019-09-08A comprehensive technical exploration of implementing a efficient read copy update (rcu) mechanism for linux kernel modules, covering key concepts, practical implementations, and real-world applications.
A Comparison Of Concurrent Hash Table Designs: Cuckoo Hashing, Hopscotch Hashing, And Striped Locking
2019-09-06A comprehensive technical exploration of a comparison of concurrent hash table designs: cuckoo hashing, hopscotch hashing, and striped locking, covering key concepts, practical implementations, and real-world applications.
Communication Complexity: Yao's Two-Party Model, the Rectangle Method, and Lower Bounds Galore
2019-08-18A deep investigation of communication complexity—the mathematics of information exchange between parties—and its far-reaching implications for circuits, data structures, and streaming.
Building A Lock Free Skip List For Range Queries In Distributed Memory
2019-08-17A comprehensive technical exploration of building a lock free skip list for range queries in distributed memory, covering key concepts, practical implementations, and real-world applications.
The Performance Impact Of Cache Line Padding In Concurrent Queues On Numa Architectures
2019-08-16A comprehensive technical exploration of the performance impact of cache line padding in concurrent queues on numa architectures, covering key concepts, practical implementations, and real-world applications.
An In Depth Look At Concurrent Data Structures: Elimination Backoff Stacks, Michael Scott Queues, And Hazard Pointers
2019-08-04A comprehensive technical exploration of an in depth look at concurrent data structures: elimination backoff stacks, michael scott queues, and hazard pointers, covering key concepts, practical implementations, and real-world applications.
Designing A Scalable Key Value Store With Lsm Trees And Write Amplification Analysis
2019-08-02A comprehensive technical exploration of designing a scalable key value store with lsm trees and write amplification analysis, covering key concepts, practical implementations, and real-world applications.
A Formal Verification Of Linearizability In A Lock Free Linked List Using Proper Testing
2019-07-30A comprehensive technical exploration of a formal verification of linearizability in a lock free linked list using proper testing, covering key concepts, practical implementations, and real-world applications.
Implementing A Wait Free Concurrent Hash Map In C++ For High Throughput Systems
2019-07-30A comprehensive technical exploration of implementing a wait free concurrent hash map in c++ for high throughput systems, covering key concepts, practical implementations, and real-world applications.
The Algorithmic Complexity Of Distributed Graph Algorithms: Bfs, Minimum Spanning Tree, And All Pairs Shortest Paths
2019-07-24A comprehensive technical exploration of the algorithmic complexity of distributed graph algorithms: bfs, minimum spanning tree, and all pairs shortest paths, covering key concepts, practical implementations, and real-world applications.
Building A Distributed Message Queue With Kafka: Partitioning, Replication, And Exactly Once Semantics
2019-07-22A comprehensive technical exploration of building a distributed message queue with kafka: partitioning, replication, and exactly once semantics, covering key concepts, practical implementations, and real-world applications.
When Data Centers Learned to Sleep: Energy-Aware Scheduling in Practice
2019-07-19An engineer’s chronicle of how hyperscale fleets embraced energy-aware scheduling without sacrificing latency or trust.
A Thorough Explanation Of The Google File System’S Master Replication And Shadow Masters
2019-07-16A comprehensive technical exploration of a thorough explanation of the google file system’s master replication and shadow masters, covering key concepts, practical implementations, and real-world applications.
Designing A Distributed Bloom Filter With Counting And Scalable Extensions For Membership Tests
2019-07-14A comprehensive technical exploration of designing a distributed bloom filter with counting and scalable extensions for membership tests, covering key concepts, practical implementations, and real-world applications.
Sublinear Algorithms: Property Testing, Query Complexity, and the Power of Random Sampling
2019-07-07An exploration of sublinear-time algorithms—property testing, the regularity lemma connection, and how random sampling reveals global structure without reading the whole input.
The Implementation Of A Log Structured Merge Tree (Lsm Tree) With Level Based Compaction In Rocksdb
2019-07-02A comprehensive technical exploration of the implementation of a log structured merge tree (lsm tree) with level based compaction in rocksdb, covering key concepts, practical implementations, and real-world applications.
Implementing A Distributed Priority Queue With Request Batching And Hierarchical Aggregation
2019-06-27A comprehensive technical exploration of implementing a distributed priority queue with request batching and hierarchical aggregation, covering key concepts, practical implementations, and real-world applications.
Streaming Algorithms: Misra-Gries, Count-Min Sketch, AMS, and the Power of Small Space
2019-06-27A comprehensive tour of streaming algorithms—from frequency estimation sketches to frequency moments—and the space lower bounds that define what's possible.
Analyzing The Correctness Of Clock Synchronization Protocols: Ntp, Ptp, And Hybrid Logical Clocks
2019-06-26A comprehensive technical exploration of analyzing the correctness of clock synchronization protocols: ntp, ptp, and hybrid logical clocks, covering key concepts, practical implementations, and real-world applications.
Building A Partition Aware Transactional Database Using Calvin: Deterministic Ordering And Lock Free Execution
2019-06-25A comprehensive technical exploration of building a partition aware transactional database using calvin: deterministic ordering and lock free execution, covering key concepts, practical implementations, and real-world applications.
The Performance Of Distributed Query Processing With Join Aggregate Trees In Google Spanner
2019-06-16A comprehensive technical exploration of the performance of distributed query processing with join aggregate trees in google spanner, covering key concepts, practical implementations, and real-world applications.
A Deep Dive Into Apache Cassandra’S Snitch And Replication Strategy: Endpoint Aware Distribution
2019-06-11A comprehensive technical exploration of a deep dive into apache cassandra’s snitch and replication strategy: endpoint aware distribution, covering key concepts, practical implementations, and real-world applications.
Implementing A Distributed Snapshot Algorithm For Global State Collection In Asynchronous Systems
2019-06-01A comprehensive technical exploration of implementing a distributed snapshot algorithm for global state collection in asynchronous systems, covering key concepts, practical implementations, and real-world applications.
Designing A Consistent Hashing With Bounded Loads Using Google’S Consistent Hashing With Sparse Representation
2019-05-23A comprehensive technical exploration of designing a consistent hashing with bounded loads using google’s consistent hashing with sparse representation, covering key concepts, practical implementations, and real-world applications.
The Microbenchmarking Of Rpc Frameworks: Grpc, Thrift, And Zeromq In High Latency Environments
2019-05-20A comprehensive technical exploration of the microbenchmarking of rpc frameworks: grpc, thrift, and zeromq in high latency environments, covering key concepts, practical implementations, and real-world applications.
Building A Distributed File System Inspired By Gfs: Master Architecture, Chunk Replication, And Leases
2019-05-14A comprehensive technical exploration of building a distributed file system inspired by gfs: master architecture, chunk replication, and leases, covering key concepts, practical implementations, and real-world applications.
Online Algorithms: Competitive Analysis, Ski Rental, Paging, and the Primal-Dual Method
2019-05-12A thorough examination of online algorithms—decisions without foresight—through the lens of competitive analysis, from ski rental and paging to the k-server problem.
Parameterized Complexity: FPT, the W-Hierarchy, Kernelization, and Bounded Search Trees
2019-05-11An in-depth exploration of parameterized complexity theory—how structural parameters beyond input size can tame NP-hardness through FPT algorithms, kernelization, and the W-hierarchy.
NP-Completeness: The Cook-Levin Theorem, Polynomial Reductions, and the Hardest Problems in NP
2019-05-03A deep dive into the theory of NP-completeness—from Turing machines and the Cook-Levin theorem to the taxonomy of NP-complete problems and the P versus NP question.
Linear Programming: Simplex Geometry, Duality, and the Interior-Point Revolution
2019-04-19An exploration of linear programming from Dantzig's simplex method through von Neumann's duality to Karmarkar's interior-point breakthrough that reshaped optimization theory.
Comparing Gossip Protocols For Failure Detection: Swim, Lifeguard, And Hybrid Approaches
2019-04-15A comprehensive technical exploration of comparing gossip protocols for failure detection: swim, lifeguard, and hybrid approaches, covering key concepts, practical implementations, and real-world applications.
Network Flow: From Ford-Fulkerson to Push-Relabel and the Max-Flow Min-Cut Theorem
2019-04-13A rigorous journey through the algorithms that solve maximum flow—Ford-Fulkerson, Edmonds-Karp, Dinic, and Push-Relabel—together with the duality that binds flows to cuts.
Implementing A Distributed Transactional Key Value Store With Optimistic Concurrency Control
2019-04-10A comprehensive technical exploration of implementing a distributed transactional key value store with optimistic concurrency control, covering key concepts, practical implementations, and real-world applications.
A Rigorous Proof Of The Cap Theorem And Its Implications For Distributed Database Design
2019-04-09A comprehensive technical exploration of a rigorous proof of the cap theorem and its implications for distributed database design, covering key concepts, practical implementations, and real-world applications.
The Design And Implementation Of A Distributed Rate Limiter Using Token Buckets And Gossip Protocols
2019-04-09A comprehensive technical exploration of the design and implementation of a distributed rate limiter using token buckets and gossip protocols, covering key concepts, practical implementations, and real-world applications.
Building A Linearizability Tester For Distributed Systems: Monotonic Reads And Writes In Jetpack
2019-04-01A comprehensive technical exploration of building a linearizability tester for distributed systems: monotonic reads and writes in jetpack, covering key concepts, practical implementations, and real-world applications.
Analyzing The Performance Of Two Phase Commit (2Pc) And Three Phase Commit (3Pc) In Geo Distributed Systems
2019-03-27A comprehensive technical exploration of analyzing the performance of two phase commit (2pc) and three phase commit (3pc) in geo distributed systems, covering key concepts, practical implementations, and real-world applications.
Implementing A Distributed Hash Table (Dht) Using Kademlia: Node Lookup, Routing, And Replication
2019-03-25A comprehensive technical exploration of implementing a distributed hash table (dht) using kademlia: node lookup, routing, and replication, covering key concepts, practical implementations, and real-world applications.
The Algorithmic Foundations Of Blockchain Consensus: Proof Of Work, Proof Of Stake, And Dag Based Approaches
2019-03-24A comprehensive technical exploration of the algorithmic foundations of blockchain consensus: proof of work, proof of stake, and dag based approaches, covering key concepts, practical implementations, and real-world applications.
Implementing A Lock Free Concurrent Hash Map: From Theoretical Foundations To Practical Performance Optimization In C++20
2019-03-16A comprehensive technical exploration of implementing a lock free concurrent hash map: from theoretical foundations to practical performance optimization in c++20, covering key concepts, practical implementations, and real-world applications.
A Deep Dive Into Corfu: A Distributed Shared Log With Object Storage And Multi Stripe Techniques
2019-03-09A comprehensive technical exploration of a deep dive into corfu: a distributed shared log with object storage and multi stripe techniques, covering key concepts, practical implementations, and real-world applications.
Building A Write Ahead Log From First Principles: Durability, Ordering, And Crash Recovery Strategies
2019-03-08A comprehensive technical exploration of building a write ahead log from first principles: durability, ordering, and crash recovery strategies, covering key concepts, practical implementations, and real-world applications.
Designing A Conflict Free Replicated Data Type (Crdt) For Collaborative Text Editing: Operational Transformation Vs. Crdt
2019-03-02A comprehensive technical exploration of designing a conflict free replicated data type (crdt) for collaborative text editing: operational transformation vs. crdt, covering key concepts, practical implementations, and real-world applications.
The Performance Of Paxos With Multi Paxos And Fast Paxos: A Benchmarking Study Across Data Centers
2019-02-27A comprehensive technical exploration of the performance of paxos with multi paxos and fast paxos: a benchmarking study across data centers, covering key concepts, practical implementations, and real-world applications.
Implementing A Distributed Lock Service Using Redis Redlock And Its Consistency Guarantees Under Failures
2019-02-24A comprehensive technical exploration of implementing a distributed lock service using redis redlock and its consistency guarantees under failures, covering key concepts, practical implementations, and real-world applications.
A Comprehensive Analysis Of Zookeeper’S Zab Protocol: Atomic Broadcast And Recovery
2019-02-23A comprehensive technical exploration of a comprehensive analysis of zookeeper’s zab protocol: atomic broadcast and recovery, covering key concepts, practical implementations, and real-world applications.
Speculative Prefetchers: Designing Memory Systems That Read the Future
2019-02-14A field guide to building and validating speculative memory prefetchers that anticipate demand in modern CPUs and data platforms.
Building A Sharded Database With Consistent Hashing: From Virtual Nodes To Rendezvous Hashing
2019-02-08A comprehensive technical exploration of building a sharded database with consistent hashing: from virtual nodes to rendezvous hashing, covering key concepts, practical implementations, and real-world applications.
Optimizing Distributed Join Algorithms For Large Scale Stream Processing With Apache Flink
2019-02-05A comprehensive technical exploration of optimizing distributed join algorithms for large scale stream processing with apache flink, covering key concepts, practical implementations, and real-world applications.
Scaling Eventual Consistency With Crdts: A Practical Implementation Of State Based And Operation Based Types
2019-01-28A comprehensive technical exploration of scaling eventual consistency with crdts: a practical implementation of state based and operation based types, covering key concepts, practical implementations, and real-world applications.
Dynamic Programming: Bellman's Principle of Optimality and the Art of Reusing Computation
2019-01-27A deep exploration of how Bellman's recursive insight transforms exponential despair into polynomial hope across knapsack, shortest paths, sequence alignment, and reinforcement learning.
The Complexity Of Byzantine Fault Tolerance In Partially Synchronous Networks: Pbft And Its Variants
2019-01-18A comprehensive technical exploration of the complexity of byzantine fault tolerance in partially synchronous networks: pbft and its variants, covering key concepts, practical implementations, and real-world applications.
Designing A Dynamo Style Distributed Key Value Store With Merkle Trees For Conflict Resolution
2019-01-10A comprehensive technical exploration of designing a dynamo style distributed key value store with merkle trees for conflict resolution, covering key concepts, practical implementations, and real-world applications.
Deep Dive Into Paxos Vs. Raft: Trade Offs In Leader Election, Log Replication, And Safety Guarantees
2019-01-07A comprehensive technical exploration of deep dive into paxos vs. raft: trade offs in leader election, log replication, and safety guarantees, covering key concepts, practical implementations, and real-world applications.
Implementing Raft Consensus From Scratch In Go: A Step By Step Guide With Fault Injection Testing
2019-01-05A comprehensive technical exploration of implementing raft consensus from scratch in go: a step by step guide with fault injection testing, covering key concepts, practical implementations, and real-world applications.
Designing A Conflict Free Replicated Data Type (Crdt) For Collaborative Text Editing: A Deep Dive Into Rope Structures, Vector Clocks, And Operational Transformation Alternatives
2019-01-01A comprehensive technical exploration of designing a conflict free replicated data type (crdt) for collaborative text editing: a deep dive into rope structures, vector clocks, and operational transformation alternatives, covering key concepts, practical implementations, and real-world applications.
Implementing A Distributed Consensus Protocol From Scratch: Raft With Leader Election, Log Replication, Membership Changes, And Cluster Reconfiguration In Go
2019-01-01A comprehensive technical exploration of implementing a distributed consensus protocol from scratch: raft with leader election, log replication, membership changes, and cluster reconfiguration in go, covering key concepts, practical implementations, and real-world applications.