Distributed consensus algorithms form the backbone of modern fault-tolerant systems. The Paxos algorithm, proposed by Leslie Lamport, achieves consensus among a group of processes even when some of them fail. In Paxos, a proposer sends a prepare request with a proposal number to a majority of acceptors. Each acceptor promises not to accept proposals with lower numbers and responds with the highest-numbered proposal it has already accepted. The proposer then sends an accept request with the highest value from the responses, or its own value if none were returned. Once a majority of acceptors accept a proposal, consensus is reached.

Raft was designed as a more understandable alternative to Paxos. It separates consensus into three sub-problems: leader election, log replication, and safety. In Raft, one server is elected as leader and manages log replication to follower nodes. The leader accepts client requests, appends entries to its log, and replicates them to followers. When a majority acknowledge, the entry is committed. If the leader fails, a new election occurs using randomized timeouts to avoid split votes. Raft's clarity has made it popular in systems like etcd, CockroachDB, and TiKV.

Byzantine fault tolerance (BFT) handles a more challenging scenario where nodes may behave arbitrarily, including maliciously. Practical Byzantine Fault Tolerance (PBFT) by Castro and Liskov requires 3f+1 nodes to tolerate f Byzantine faults. The protocol proceeds through three phases: pre-prepare, prepare, and commit. The primary node sequences requests and broadcasts pre-prepare messages. Replicas verify and broadcast prepare messages. Once 2f+1 matching prepare messages are collected, nodes broadcast commit messages. After receiving 2f+1 commits, the operation is executed. While PBFT has O(n^2) message complexity, later protocols like HotStuff reduced this to O(n) using a three-phase pipeline with threshold signatures.

Vector clocks provide a mechanism for tracking causality in distributed systems without synchronized physical clocks. Each process maintains a vector of logical timestamps, one per process. When a process performs a local event, it increments its own entry. When sending a message, it attaches its vector clock. Upon receiving, the recipient takes the element-wise maximum of its clock and the received clock, then increments its own entry. Two events are causally ordered if one vector is element-wise less than or equal to the other; otherwise they are concurrent. This enables conflict detection in systems like Amazon's Dynamo and Riak.

B-tree indexes are the workhorse of relational database storage engines. A B-tree of order m allows each node to have at most m children and at least ceil(m/2) children (except the root). Keys within each node are sorted, and the tree remains balanced through split and merge operations during insertions and deletions. The height of a B-tree with n keys is O(log_m(n)), ensuring logarithmic lookup time. Most database implementations use B+ trees, where all data resides in leaf nodes connected by sibling pointers, enabling efficient range scans.

Write-ahead logging (WAL) ensures durability and atomicity in database systems. Before any modification reaches the data pages, the corresponding log records are written to stable storage. Each log record contains a log sequence number (LSN), the transaction ID, the page ID, and before/after images of the modification. During recovery, the database replays the log forward (redo) to restore committed changes and backward (undo) to rollback uncommitted transactions. ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the gold standard for WAL-based recovery, using three passes: analysis, redo, and undo.

Multi-version concurrency control (MVCC) allows readers and writers to operate concurrently without blocking each other. Each write creates a new version of the data rather than overwriting in place. Readers see a consistent snapshot based on their transaction's start timestamp. PostgreSQL implements MVCC by storing multiple row versions in the heap, with each version tagged by creation and deletion transaction IDs. Garbage collection (vacuum) removes versions no longer visible to any active transaction. MySQL's InnoDB uses undo logs to reconstruct older versions on demand, avoiding the storage overhead of keeping all versions in the main data structure.

Transaction isolation levels define the degree to which concurrent transactions are insulated from each other. Read Uncommitted allows dirty reads. Read Committed prevents dirty reads but allows non-repeatable reads. Repeatable Read prevents both but may allow phantom reads. Serializable ensures complete isolation, as if transactions executed sequentially. Implementation strategies include two-phase locking (2PL), optimistic concurrency control (OCC), and serializable snapshot isolation (SSI). SSI, used in PostgreSQL 9.1+, detects dangerous structures of read-write conflicts at commit time rather than acquiring locks upfront.

Lexical analysis transforms a stream of characters into a stream of tokens. The scanner typically uses a deterministic finite automaton (DFA) constructed from regular expressions. For example, an identifier might be matched by [a-zA-Z_][a-zA-Z0-9_]*, while integer literals match [0-9]+. Modern scanner generators like flex or re2c compile these patterns into efficient table-driven or direct-coded automata. The longest-match rule resolves ambiguity: the scanner always returns the longest possible token. Keywords are often recognized by a hash table lookup after an identifier is matched rather than by separate DFA states.

Parsing transforms a token stream into an abstract syntax tree (AST). LL parsers read input Left-to-right and produce a Leftmost derivation, while LR parsers produce a Rightmost derivation in reverse. Recursive descent parsers implement LL(1) grammars directly as a set of mutually recursive functions. LALR(1) parsers, generated by tools like yacc and bison, use a parse table with states, shift/reduce actions, and goto entries. The table is constructed from LR(0) item sets augmented with lookahead information. Operator precedence parsing handles expression grammars efficiently by associating precedence levels and associativity with operators, as in Pratt parsing.

Static single assignment (SSA) form is an intermediate representation where each variable is assigned exactly once. Phi functions at control flow join points merge values from different predecessors. SSA simplifies many optimizations: constant propagation becomes trivial because each definition uniquely determines the value at all uses. Dead code elimination reduces to removing definitions with no uses. The dominance frontier algorithm by Cytron et al. efficiently places phi functions. Global value numbering on SSA form discovers redundant computations by hashing expressions and recognizing when two computations produce the same value.

Register allocation assigns an unbounded number of virtual registers to a finite set of physical registers. Graph coloring allocates registers by building an interference graph where nodes are variables and edges connect simultaneously live variables. The graph is then colored with k colors (one per physical register). Chaitin's algorithm simplifies nodes with degree less than k, colors the simplified graph, and spills variables that cannot be colored. Linear scan allocation offers faster compilation by processing live intervals in order, maintaining an active set, and spilling the interval with the farthest next use when no register is available. Modern JIT compilers like V8's TurboFan use variations of linear scan for its speed.

Virtual memory provides each process with an isolated address space mapped to physical memory through page tables. The Memory Management Unit (MMU) translates virtual addresses to physical addresses using a multi-level page table structure. On x86-64, a four-level page table (PML4, PDPT, PDT, PT) maps 48-bit virtual addresses to physical frames. Each page table entry contains the physical frame number, present/absent bit, read/write permissions, user/supervisor mode, and dirty/accessed bits. Translation Lookaside Buffers (TLBs) cache recent translations; a TLB miss triggers a page table walk. Huge pages (2MB or 1GB) reduce TLB pressure for large memory workloads by using fewer, larger mappings.

The Linux kernel's Completely Fair Scheduler (CFS) uses a red-black tree of tasks sorted by virtual runtime (vruntime). Each task's vruntime advances at a rate inversely proportional to its weight (derived from its nice value). The task with the smallest vruntime is always selected next, ensuring fairness over time. CFS uses a configurable scheduling latency period during which all runnable tasks should run at least once. The minimum granularity prevents excessive context switching when many tasks compete. Real-time tasks use SCHED_FIFO or SCHED_RR policies that preempt CFS tasks. The bandwidth throttling mechanism limits CPU time for real-time groups to prevent starvation of normal tasks.

Memory-mapped I/O allows devices to be accessed through load and store instructions to specific physical addresses. In contrast, port-mapped I/O uses dedicated in/out instructions. Modern devices use memory-mapped I/O with Base Address Registers (BARs) configured during PCI enumeration. DMA (Direct Memory Access) enables devices to transfer data directly to/from memory without CPU involvement. The CPU sets up DMA descriptors specifying source, destination, and length, then signals the device. Scatter-gather DMA supports non-contiguous memory regions using descriptor chains. IOMMU (I/O Memory Management Unit) provides address translation and isolation for DMA, preventing devices from accessing unauthorized memory regions.

File systems organize persistent data through a hierarchy of directories and files. ext4 uses an extent-based allocation scheme where each extent maps a contiguous range of logical blocks to physical blocks, reducing metadata overhead for large files compared to indirect block pointers. The journal (JBD2) records metadata changes before committing them to the main file system, enabling fast crash recovery. XFS uses B+ trees extensively for directory entries, free space tracking, and extent allocation. ZFS and Btrfs implement copy-on-write semantics where modifications create new blocks rather than overwriting existing ones, enabling atomic snapshots and built-in checksumming for data integrity verification.

Symmetric encryption algorithms operate on fixed-size blocks or continuous streams. AES (Advanced Encryption Standard) processes 128-bit blocks through multiple rounds of SubBytes, ShiftRows, MixColumns, and AddRoundKey transformations. AES-128 uses 10 rounds, AES-192 uses 12, and AES-256 uses 14. The SubBytes step applies an S-box derived from the multiplicative inverse in GF(2^8), providing non-linearity. Modern CPUs include AES-NI instructions that execute entire rounds in single clock cycles, achieving throughputs exceeding 10 GB/s. ChaCha20, a stream cipher by Daniel Bernstein, operates on 512-bit states through 20 rounds of quarter-round operations mixing addition, XOR, and rotation. It achieves comparable security to AES while being faster on platforms without hardware AES acceleration.

Public-key cryptography enables secure communication without shared secrets. RSA security relies on the difficulty of factoring the product of two large primes. Key generation selects primes p and q, computes n=pq and phi=(p-1)(q-1), chooses public exponent e coprime to phi, and computes private exponent d as the modular inverse of e mod phi. Encryption computes c = m^e mod n, and decryption computes m = c^d mod n. RSA-2048 provides approximately 112 bits of security. Elliptic Curve Cryptography (ECC) achieves equivalent security with smaller key sizes: a 256-bit ECC key provides security comparable to RSA-3072. Operations on elliptic curves (point addition and scalar multiplication) over finite fields form the basis for ECDH key exchange and ECDSA signatures.

Hash functions map arbitrary-length inputs to fixed-length outputs. SHA-256 processes input in 512-bit blocks through 64 rounds of compression, producing a 256-bit digest. The Merkle-Damgard construction iteratively applies the compression function, with the previous output as the chaining value. SHA-3 (Keccak) uses a sponge construction that absorbs input blocks by XORing them into the state and applying a permutation, then squeezes output. BLAKE3 achieves high performance by using a Merkle tree structure enabling parallelism, with a core compression function based on ChaCha's quarter-round. Argon2, the Password Hashing Competition winner, defends against GPU and ASIC attacks by requiring configurable amounts of memory, time, and parallelism.

Transport Layer Security (TLS) 1.3 simplified the handshake to a single round trip. The client sends a ClientHello with supported cipher suites, key shares for likely groups, and a pre-shared key extension if resuming. The server responds with its key share, selected cipher suite, and encrypted extensions. Both sides derive traffic keys from the shared secret using HKDF (HMAC-based Key Derivation Function). Forward secrecy is mandatory: ephemeral Diffie-Hellman key exchange ensures that compromise of long-term keys does not reveal past session keys. AEAD (Authenticated Encryption with Associated Data) algorithms like AES-GCM and ChaCha20-Poly1305 provide both confidentiality and integrity.

Backpropagation computes gradients of the loss function with respect to each weight in a neural network by applying the chain rule of calculus. During the forward pass, each layer computes its output and caches intermediate values needed for gradient computation. During the backward pass, gradients flow from the loss through each layer in reverse order. For a fully connected layer y = Wx + b, the gradient with respect to W is the outer product of the incoming gradient and the cached input, while the gradient passed to the previous layer is W^T times the incoming gradient. Stochastic gradient descent (SGD) updates weights by subtracting the gradient scaled by the learning rate. Adam optimizer maintains per-parameter exponential moving averages of the gradient (first moment) and squared gradient (second moment), providing adaptive learning rates that converge faster than vanilla SGD.

Transformer architectures have revolutionized sequence modeling. Self-attention computes Query, Key, and Value projections from the input, then attention weights as softmax(QK^T / sqrt(d_k)), and finally the output as the weighted sum of values. Multi-head attention runs h parallel attention operations with different learned projections, concatenating results. Position information is injected through sinusoidal encodings or learned embeddings. The feed-forward network in each transformer block applies two linear transformations with a ReLU or GELU activation. Layer normalization stabilizes training by normalizing activations across the feature dimension. Pre-norm (normalizing before attention/FFN) has become standard as it enables more stable training of deep models.

Mixture of Experts (MoE) architectures replace the dense feed-forward layer with multiple expert networks and a gating mechanism. The gate produces a sparse routing distribution, selecting the top-k experts for each input token. This enables scaling model capacity (total parameters) while keeping compute (FLOPs per token) constant. Switch Transformer routes each token to a single expert, while GShard and ST-MoE use top-2 routing. Load balancing is critical: auxiliary losses penalize uneven expert utilization. Expert parallelism distributes experts across devices, with all-to-all communication routing tokens to their assigned experts. Capacity factors limit the maximum tokens per expert per batch, dropping excess tokens. Fine-grained experts (more, smaller experts) generally improve quality for the same compute budget.

Quantization reduces the precision of neural network weights and activations to enable faster inference. Post-training quantization (PTQ) converts a pre-trained model without retraining: weights are grouped, scales computed per group, and values rounded to the target precision. GPTQ uses second-order information (approximate Hessian) to minimize quantization error by jointly optimizing the rounding of columns in weight matrices. AWQ identifies salient weight channels based on activation magnitudes and scales them before quantization. INT4 weight-only quantization achieves 4x memory reduction with minimal quality loss for large language models. Mixed-precision strategies keep attention layers at higher precision while aggressively quantizing feed-forward layers, balancing speed and quality.

TCP congestion control prevents network collapse by adapting the sending rate to available bandwidth. The classic algorithm progresses through slow start (exponential growth), congestion avoidance (linear growth), and fast recovery. Slow start doubles the congestion window each round-trip time until reaching the slow-start threshold. Congestion avoidance increases the window by roughly one segment per RTT. On packet loss (detected by triple duplicate ACKs), fast retransmit resends the lost segment immediately, and fast recovery halves the congestion window. TCP CUBIC, the default in Linux, uses a cubic function of time since the last loss event, enabling faster window growth for high-bandwidth-delay-product networks. BBR (Bottleneck Bandwidth and Round-trip propagation time) by Google takes a different approach, modeling the network path to maximize throughput while minimizing latency, achieving significant improvements over loss-based algorithms.

HTTP/2 introduced multiplexing, allowing multiple requests and responses to share a single TCP connection through streams identified by unique IDs. Header compression (HPACK) uses Huffman coding and a dynamic table of previously transmitted headers, reducing overhead dramatically for repeated headers like cookies and user-agents. Server push enables proactive sending of resources before the client requests them. However, HTTP/2 suffers from head-of-line blocking at the TCP layer: a lost packet blocks all streams until retransmitted. HTTP/3 solves this by switching to QUIC, a UDP-based transport that provides independent stream processing. QUIC includes built-in encryption (TLS 1.3), 0-RTT connection establishment for resumed sessions, and connection migration across network changes using connection IDs rather than IP/port tuples.

BGP (Border Gateway Protocol) is the routing protocol of the internet, exchanging reachability information between autonomous systems (ASes). BGP uses path-vector routing where each route advertisement includes the full AS path, preventing loops. Route selection considers multiple attributes: local preference, AS path length, origin type, MED (Multi-Exit Discriminator), and community tags. eBGP peers exchange routes between different ASes, while iBGP distributes routes within an AS. Full-mesh iBGP requires O(n^2) sessions; route reflectors reduce this by centralizing route distribution. BGP security remains a concern: prefix hijacking occurs when an AS announces routes for IP space it doesn't own. RPKI (Resource Public Key Infrastructure) enables ASes to cryptographically verify the origin of route announcements.

DNS resolution translates domain names to IP addresses through a hierarchical delegation system. A recursive resolver queries root servers for the TLD (top-level domain) nameservers, then the TLD servers for the authoritative nameservers, and finally the authoritative servers for the actual records. Responses are cached according to TTL (Time To Live) values. DNSSEC adds cryptographic signatures to DNS records, allowing resolvers to verify authenticity using a chain of trust from the root zone. DNS over HTTPS (DoH) and DNS over TLS (DoT) encrypt queries to prevent eavesdropping and manipulation by network intermediaries. Modern resolvers like Unbound support prefetching, which refreshes popular cached entries before expiration to maintain low-latency responses.

Modern out-of-order processors execute instructions as their operands become available rather than in program order. The front end fetches instructions from the instruction cache, decodes them into micro-operations, and places them in the reorder buffer (ROB). The rename stage maps architectural registers to physical registers, eliminating false dependencies (WAR and WAW hazards). The scheduler dispatches ready micro-operations to execution units when their source operands are available. Results are written to the physical register file and broadcast to waiting instructions via the common data bus. The retirement stage commits completed instructions in program order, maintaining the illusion of sequential execution. Branch prediction is critical: a misprediction flushes the pipeline, wasting tens of cycles. Modern predictors like TAGE (TAgged GEometric history length) maintain multiple prediction tables indexed by different history lengths.

Cache hierarchies bridge the speed gap between fast processors and slow main memory. L1 caches (typically 32-64KB, 4-5 cycle latency) split into instruction and data caches. L2 caches (256KB-1MB, 12-15 cycles) are unified. L3 caches (8-256MB, 30-50 cycles) are shared across cores. Cache lines are typically 64 bytes. The MESI protocol (Modified, Exclusive, Shared, Invalid) maintains coherence across cores. When one core modifies a cache line, it transitions to Modified state and invalidates copies in other cores. Intel's ring bus or mesh interconnect carries coherence messages between cores and the LLC (Last Level Cache). NUMA (Non-Uniform Memory Access) architectures have memory directly attached to each processor socket; accessing remote memory incurs additional latency, making memory placement important for performance.

GPU architectures employ massive parallelism through thousands of lightweight threads organized into warps or wavefronts. NVIDIA's streaming multiprocessors (SMs) execute warps of 32 threads in lockstep SIMT (Single Instruction, Multiple Threads) fashion. Each SM has a register file, shared memory, L1 cache, and multiple execution units (INT32, FP32, FP64, tensor cores). Tensor cores perform matrix multiply-accumulate operations on 4x4 matrices, critical for deep learning workloads. GPU memory hierarchies include registers (fastest), shared memory (programmer-managed scratchpad), L1/L2 caches, and global GDDR6/HBM memory. Memory coalescing combines multiple thread memory accesses into fewer transactions when addresses fall within the same cache line. Occupancy (ratio of active warps to maximum warps) affects performance: higher occupancy hides memory latency through warp scheduling.

PCIe (Peripheral Component Interconnect Express) provides high-speed serial communication between CPUs and devices. PCIe 4.0 achieves 16 GT/s per lane with 128b/130b encoding, yielding ~2 GB/s per lane. A x16 slot provides ~32 GB/s bidirectional bandwidth. PCIe 5.0 doubles this to ~64 GB/s. The protocol stack includes the transaction layer (TLPs: memory read/write, completions, messages), data link layer (ACK/NAK, flow control), and physical layer (encoding, link training). CXL (Compute Express Link) builds on PCIe 5.0 to enable cache-coherent access to device-attached memory, allowing GPUs and accelerators to participate in the CPU's coherence domain.

Garbage collection automatically reclaims memory that is no longer reachable from the root set. Mark-sweep collectors traverse the object graph from roots, marking reachable objects, then sweep through the heap freeing unmarked objects. This causes fragmentation over time. Mark-compact collectors additionally relocate live objects to eliminate fragmentation, but require updating all pointers. Generational collectors exploit the weak generational hypothesis (most objects die young) by partitioning the heap into young and old generations. Minor collections frequently scan the young generation, promoting survivors to the old generation. Major collections scan the entire heap less frequently. G1 (Garbage First) divides the heap into regions and prioritizes collecting regions with the most garbage. ZGC and Shenandoah achieve sub-millisecond pause times through concurrent marking and relocation using colored pointers or Brooks forwarding pointers.

Type systems statically verify program properties at compile time. The Hindley-Milner type system infers the most general type for expressions without any type annotations, using Algorithm W based on unification. Parametric polymorphism (generics) allows functions and data structures to operate on any type. Rust's ownership system tracks which variable owns each piece of data and enforces that there is at most one mutable reference or any number of immutable references at any time, preventing data races at compile time. Lifetime annotations specify the relationship between reference lifetimes, enabling the borrow checker to verify memory safety. Algebraic data types (sum types like Rust's enum or Haskell's data) combined with pattern matching enable exhaustive handling of all cases, preventing null pointer errors.

Concurrency models vary significantly across languages. Go uses goroutines (lightweight green threads multiplexed onto OS threads) communicating through channels, following the CSP (Communicating Sequential Processes) model. The Go scheduler uses work stealing to balance goroutines across OS threads. Erlang processes are even lighter (a few hundred bytes each) with message-passing semantics and supervision trees for fault tolerance. Rust provides both message passing (channels) and shared state (Mutex, Arc) with compile-time data race prevention. Java's virtual threads (Project Loom) provide lightweight threads that automatically unmount from carrier OS threads during blocking operations. Python's asyncio uses cooperative multitasking with async/await syntax, running on a single-threaded event loop, suitable for I/O-bound workloads but limited by the GIL for CPU-bound parallelism.

Memory models define how threads observe each other's memory operations. The C++ memory model provides several ordering constraints: relaxed (no ordering guarantees beyond atomicity), acquire-release (synchronizes specific memory locations), and sequentially consistent (total order on all atomic operations). The x86 Total Store Order (TSO) model is relatively strong: loads are not reordered with other loads, stores are not reordered with other stores, and stores are not reordered with earlier loads. However, a load may be reordered with an earlier store to a different location. ARM and RISC-V have weaker memory models, requiring explicit fence instructions for ordering guarantees. Java's memory model defines happens-before relationships through synchronized blocks, volatile variables, and thread start/join operations.

Lock-free data structures enable concurrent access without traditional mutual exclusion, using atomic operations like compare-and-swap (CAS). A lock-free stack pushes by repeatedly reading the top pointer, setting the new node's next to it, and CAS-ing the top to the new node. If another thread modified the top between the read and CAS, the operation retries. The ABA problem occurs when a pointer value is reused: thread A reads top as node X, thread B pops X and pushes Y then pushes X again, and thread A's CAS succeeds even though the stack has changed. Solutions include tagged pointers (incrementing a counter with each CAS), hazard pointers (preventing reclamation of nodes being accessed), or epoch-based reclamation (batching deallocation to epochs when no thread is in a critical section).

Memory allocators significantly impact application performance. glibc's ptmalloc2 uses per-thread arenas to reduce contention, with each arena managing chunks through bins organized by size: fast bins (small, no coalescing), small bins (exact size), large bins (sorted by size), and unsorted bins (recently freed). jemalloc organizes memory into runs of same-sized regions within chunks, using thread-local caches and size-class-based allocation. tcmalloc (Google) maintains per-thread caches for small allocations and a central free list for larger ones, with periodic garbage collection to rebalance. mimalloc (Microsoft) uses sharded thread-local heaps with efficient free lists, achieving excellent performance across diverse workloads. All modern allocators must handle virtual memory fragmentation, page-level allocation, and transparent huge page interaction.

io_uring is Linux's modern asynchronous I/O interface, using shared ring buffers between user space and the kernel. The submission queue (SQ) contains entries describing I/O operations, and the completion queue (CQ) contains results. The application writes SQEs (submission queue entries) specifying the operation type (read, write, accept, connect, etc.), file descriptor, buffer, and offset. A single io_uring_enter system call can submit multiple operations and wait for completions simultaneously. Fixed files and fixed buffers avoid per-operation fd lookup and memory mapping overhead. Linked operations enable dependent sequences without returning to user space between steps. The SQPOLL mode uses a kernel thread to poll the submission queue, eliminating system calls entirely for sustained high-throughput workloads.

eBPF (extended Berkeley Packet Filter) enables safe, efficient programmability of the Linux kernel. eBPF programs are written in a restricted C subset, compiled to BPF bytecode, verified by the kernel's verifier (ensuring no infinite loops, valid memory access, and bounded execution), and JIT-compiled to native code. Programs attach to various kernel hooks: network packet processing (XDP, tc), tracing (kprobes, tracepoints, fentry), security (LSM), and scheduling. BPF maps provide shared state between eBPF programs and user space, supporting hash tables, arrays, ring buffers, and per-CPU variants. XDP (eXpress Data Path) processes packets at the earliest possible point in the network stack, achieving millions of packets per second for load balancing, firewalling, and DDoS mitigation.

Balanced binary search trees maintain O(log n) height guarantees through rotations and color/balance invariants. Red-black trees maintain five properties: every node is red or black, the root is black, leaves (NIL) are black, red nodes have black children, and all paths from a node to its leaves contain the same number of black nodes. Insertions may violate the red-parent property; fix-up involves recoloring and at most two rotations. AVL trees maintain a stricter balance: the height difference between left and right subtrees is at most one. This provides faster lookups (1.44 log n vs 2 log n worst case) but slower insertions due to more frequent rotations. B-trees generalize to multi-way branching, keeping all leaves at the same depth. With a branching factor of several hundred, B-trees minimize disk seeks by storing many keys per node, making them ideal for database indexes.

Skip lists provide probabilistic O(log n) search, insertion, and deletion. Each element is promoted to higher levels with probability p (typically 1/2 or 1/4). Searching starts at the highest level, moving forward while the next element is less than the target, then dropping down a level. Expected space is O(n) and expected height is O(log n). Skip lists are simpler to implement than balanced trees and support concurrent access more naturally through fine-grained locking or lock-free techniques. Redis uses skip lists for sorted sets because they support efficient range queries and have simpler concurrency characteristics than red-black trees.

Bloom filters provide space-efficient probabilistic set membership testing with no false negatives. An m-bit array is initialized to zeros. Insertion hashes the element with k independent hash functions, setting the corresponding bits. Query checks all k positions; if all are set, the element is probably in the set (with false positive probability approximately (1 - e^(-kn/m))^k for n elements). Counting Bloom filters replace bits with counters to support deletion. Cuckoo filters improve on Bloom filters by supporting deletion and achieving better space efficiency through cuckoo hashing with fingerprints. HyperLogLog estimates set cardinality using O(log log n) space: it hashes elements and tracks the maximum number of leading zeros, using stochastic averaging across multiple registers.

Consistent hashing distributes keys across a dynamic set of nodes while minimizing redistribution when nodes join or leave. Each node is mapped to multiple points on a hash ring using virtual nodes. A key is assigned to the first node encountered when walking clockwise from the key's position on the ring. When a node is added, it assumes responsibility for keys between it and its predecessor; only those keys need redistribution. Virtual nodes (multiple ring positions per physical node) ensure uniform distribution. Systems like Cassandra, DynamoDB, and Riak use consistent hashing for data partitioning. Rendezvous hashing (highest random weight) provides an alternative where each key computes a score for every node, selecting the highest; it offers better load distribution but requires evaluating all nodes.

Property-based testing generates random inputs to test program invariants rather than individual examples. QuickCheck pioneered this approach in Haskell, where developers specify properties like "reversing a list twice yields the original list" or "sorting produces a non-decreasing sequence." The framework generates hundreds of random inputs, and when a failure is found, automatically shrinks the input to a minimal failing case. Hypothesis (Python) and fast-check (JavaScript) bring property-based testing to mainstream languages. Stateful testing generates sequences of operations and verifies that a model (abstract state machine) stays in sync with the system under test. This approach has found bugs in databases, file systems, and distributed systems that example-based tests missed.

Chaos engineering proactively injects failures to verify system resilience. Netflix's Chaos Monkey randomly terminates instances in production, ensuring services handle individual node failures gracefully. Chaos Kong simulates entire availability zone failures. Litmus (now part of CNCF) provides a framework for running chaos experiments on Kubernetes: pod deletion, network partition, CPU/memory stress, and disk fill. Experiments define a steady state hypothesis (e.g., error rate below 1%), introduce turbulence, and verify the hypothesis still holds. Gradual rollout starts with non-critical environments and narrow blast radius, expanding as confidence grows. Game days bring teams together to practice incident response with controlled failure injection.

Observability encompasses logging, metrics, and tracing. Structured logging emits machine-parseable events (JSON) with consistent fields: timestamp, level, service, trace_id, and contextual attributes. Metrics track aggregated measurements: counters (monotonically increasing, e.g., request count), gauges (point-in-time values, e.g., queue depth), and histograms (distribution of values, e.g., latency percentiles). Prometheus scrapes metrics endpoints and evaluates alerting rules on time-series data. Distributed tracing follows a request across service boundaries using trace and span IDs propagated through headers. Each span records the service name, operation, duration, and status. Jaeger and Zipkin collect and visualize traces, revealing latency bottlenecks and error propagation paths across microservices.

Feature flags decouple deployment from release, allowing code to be shipped disabled and gradually enabled. Boolean flags gate simple on/off features. Percentage rollouts enable features for a fraction of users, increasing gradually while monitoring error rates and performance. User-targeting flags enable features for specific users, organizations, or segments. Kill switches provide instant rollback without redeployment. Flag evaluation should be fast (microseconds) and local (cached configuration). LaunchDarkly, Split.io, and open-source systems like Unleash and Flipt provide server-side evaluation with real-time configuration updates via streaming connections. Stale flags that are never cleaned up accumulate technical debt; flag lifecycle management includes creation date, owner, and scheduled removal.

Kubernetes orchestrates containerized workloads across clusters of machines. The control plane consists of the API server (RESTful interface), etcd (distributed key-value store for cluster state), the scheduler (assigns pods to nodes based on resource requirements and constraints), and controller managers (reconcile desired vs actual state). Worker nodes run kubelet (manages pod lifecycle), kube-proxy (implements service networking), and a container runtime (containerd or CRI-O). Pods are the smallest deployable units, containing one or more containers sharing network namespace and storage volumes. Deployments manage ReplicaSets that ensure the desired number of pod replicas are running. Rolling updates replace pods incrementally, while rollbacks revert to previous ReplicaSet configurations.

Service mesh architectures like Istio inject sidecar proxies (Envoy) alongside application containers. These proxies intercept all network traffic, providing transparent mutual TLS encryption, load balancing, circuit breaking, retries, and observability without application code changes. The control plane (istiod) distributes configuration to sidecar proxies using the xDS API. Traffic management rules enable canary deployments (routing a percentage of traffic to new versions), A/B testing, and fault injection for resilience testing. Authorization policies define fine-grained access control between services. Recent ambient mesh designs move proxy functionality from sidecars to node-level ztunnels and optional waypoint proxies, reducing resource overhead and operational complexity.

Infrastructure as Code (IaC) manages cloud resources through declarative configuration files. Terraform uses HCL (HashiCorp Configuration Language) to define providers, resources, data sources, and modules. The plan-apply workflow shows changes before execution. State tracks the mapping between configuration and real resources, stored in backends like S3 or Terraform Cloud. Pulumi allows infrastructure definition in general-purpose languages (TypeScript, Python, Go), enabling loops, conditionals, and abstractions. AWS CDK generates CloudFormation from TypeScript or Python constructs. GitOps extends IaC by using Git as the single source of truth: Argo CD or Flux continuously reconcile cluster state with repository definitions, automatically applying changes when commits are pushed.

Serverless computing abstracts away server management entirely. AWS Lambda executes functions in response to events (HTTP requests, queue messages, file uploads) with automatic scaling from zero to thousands of concurrent instances. Cold starts (initializing a new execution environment) add latency; provisioned concurrency keeps environments warm. Container-based serverless (AWS Fargate, Google Cloud Run) provides more flexibility than function-based systems, running arbitrary container images with per-request scaling. Event-driven architectures compose serverless functions with message queues (SQS), event buses (EventBridge), and step functions for orchestration. Edge computing pushes serverless execution to CDN points of presence: Cloudflare Workers, Lambda@Edge, and Deno Deploy run JavaScript/WebAssembly at the network edge with sub-millisecond cold starts.

Apache Kafka provides distributed, fault-tolerant event streaming. Topics are partitioned across brokers, with each partition being an ordered, immutable sequence of records. Producers append records to partitions based on a key hash or round-robin distribution. Consumer groups enable parallel processing: each partition is assigned to exactly one consumer in a group, and rebalancing redistributes partitions when consumers join or leave. Offsets track each consumer's position; committing offsets enables at-least-once processing (commit after processing) or at-most-once (commit before processing). Exactly-once semantics require idempotent producers and transactional reads from consumed topics to produced topics. Kafka Connect integrates with external systems through source connectors (ingest) and sink connectors (export) without custom code.

Stream processing engines compute continuous queries over unbounded data. Apache Flink maintains distributed state with exactly-once guarantees through checkpointing: barriers flow through the data stream, and when all sources advance past a barrier, operator state is snapshot to durable storage. Windowing groups events by time: tumbling windows (fixed, non-overlapping), sliding windows (fixed, overlapping), session windows (activity-based gaps), and global windows (custom triggers). Watermarks track event-time progress, allowing late events to be handled with allowed lateness periods or side outputs. Flink's RocksDB state backend enables state larger than memory by spilling to local SSD, with incremental checkpoints for efficient fault tolerance.

Data lake architectures store raw data in open formats on object storage. Delta Lake adds ACID transactions, schema enforcement, and time travel to Parquet files on S3/ADLS. The transaction log records every change as JSON entries, enabling concurrent reads and writes with optimistic concurrency control. Z-ordering co-locates related data within files, improving query performance for multi-dimensional filtering. Apache Iceberg provides similar capabilities with a different metadata design using manifest files listing data files with column-level statistics. Both support schema evolution (adding, dropping, renaming columns) and partition evolution (changing partitioning without rewriting data). The lakehouse pattern combines data lake storage with data warehouse query performance through these table formats.

ETL pipelines extract data from sources, transform it, and load it into target systems. Apache Airflow orchestrates these pipelines as directed acyclic graphs (DAGs) of tasks. Each task is an operator: BashOperator, PythonOperator, or provider-specific operators for databases, cloud services, and applications. Task dependencies define execution order, with sensors waiting for external conditions. The scheduler evaluates DAG files periodically, creating DAG runs for scheduled intervals. The executor backend (Celery, Kubernetes, or local) runs tasks in parallel according to resource constraints. dbt (data build tool) focuses on the transformation layer, compiling SQL models with ref() references into a dependency graph, enabling version control, testing, and documentation of data transformations.

Graph theory provides the mathematical foundation for network analysis and algorithm design. A graph G = (V, E) consists of vertices and edges. In directed graphs, edges have orientation; in undirected graphs, they do not. A path is a sequence of vertices connected by edges; a cycle is a path that starts and ends at the same vertex. A graph is connected if a path exists between every pair of vertices. Dijkstra's algorithm finds shortest paths from a source vertex by maintaining a priority queue of tentative distances, greedily extracting the minimum and relaxing adjacent edges. Its time complexity is O((V + E) log V) with a binary heap. The A* algorithm extends Dijkstra with a heuristic function estimating the remaining distance, exploring fewer nodes when the heuristic is admissible (never overestimates). For negative edge weights, Bellman-Ford iterates V-1 times over all edges, detecting negative cycles on the V-th iteration.

Information theory quantifies uncertainty and communication capacity. Shannon entropy H(X) = -sum(p(x) log2 p(x)) measures the expected information content of a random variable. For a fair coin, H = 1 bit; for a biased coin with p=0.9, H = 0.47 bits. Mutual information I(X;Y) = H(X) - H(X|Y) measures how much knowing Y reduces uncertainty about X. The channel capacity C = max I(X;Y) over input distributions gives the maximum reliable communication rate. Huffman coding achieves optimal prefix-free codes: build a binary tree bottom-up by repeatedly merging the two least probable symbols. Arithmetic coding encodes entire messages as single numbers in [0,1), achieving compression closer to the entropy than Huffman for skewed distributions. Kolmogorov complexity K(x) is the length of the shortest program that outputs x, providing an objective measure of randomness.

Linear algebra underlies machine learning, computer graphics, and scientific computing. Singular Value Decomposition (SVD) factors any matrix A into U * Sigma * V^T, where U and V are orthogonal and Sigma is diagonal with non-negative singular values. SVD enables dimensionality reduction (PCA), matrix approximation (truncated SVD), and pseudoinverse computation. The power method iteratively computes the dominant eigenvector by repeated matrix-vector multiplication and normalization. QR decomposition factors A = QR where Q is orthogonal and R is upper triangular, forming the basis for eigenvalue algorithms (QR iteration) and least squares solutions. Sparse matrix representations (CSR, CSC, COO) store only non-zero elements, enabling efficient computation on matrices with many zeros common in graph algorithms and finite element methods.

Probability theory enables reasoning under uncertainty. Bayes' theorem P(A|B) = P(B|A)P(A)/P(B) updates beliefs given new evidence. Markov chains model sequences where the next state depends only on the current state, not history. The stationary distribution pi satisfies pi = pi * P, where P is the transition matrix. Markov Chain Monte Carlo (MCMC) methods sample from complex probability distributions by constructing a Markov chain whose stationary distribution is the target distribution. The Metropolis-Hastings algorithm proposes new states and accepts them with probability min(1, (p(x')*q(x|x'))/(p(x)*q(x'|x))). Gibbs sampling, a special case, samples each variable conditionally on all others. These methods are fundamental to Bayesian inference, statistical physics, and generative modeling.

Memory safety vulnerabilities remain a leading cause of security breaches. Buffer overflows occur when writes exceed allocated bounds, overwriting adjacent memory. Stack-based overflows can overwrite return addresses, redirecting execution to attacker-controlled code. Modern mitigations include stack canaries (random values checked before function return), ASLR (Address Space Layout Randomization, randomizing base addresses of stack, heap, and libraries), DEP/NX (Data Execution Prevention, marking data pages as non-executable), and CFI (Control Flow Integrity, restricting indirect branch targets to valid destinations). Use-after-free vulnerabilities exploit dangling pointers to freed memory that has been reallocated for a different purpose. Temporal memory safety ensures pointers cannot be used after the pointed-to object's lifetime ends.

Web application security addresses vulnerabilities in the browser-server interaction model. Cross-Site Scripting (XSS) injects malicious scripts into web pages viewed by other users. Reflected XSS includes the payload in the request; stored XSS persists the payload in the application's database. Content Security Policy (CSP) headers restrict script sources, mitigating XSS by preventing inline scripts and limiting allowed domains. Cross-Site Request Forgery (CSRF) tricks authenticated users into performing unintended actions. Mitigations include anti-CSRF tokens (random values tied to the session and embedded in forms), SameSite cookie attributes, and checking the Origin header. SQL injection manipulates database queries by injecting SQL syntax through user inputs. Parameterized queries (prepared statements) separate SQL structure from data, preventing injection regardless of input content.

Zero-trust architecture assumes no implicit trust based on network location. Every access request is authenticated, authorized, and encrypted regardless of origin. Identity becomes the primary security perimeter rather than network boundaries. Multi-factor authentication combines something you know (password), something you have (hardware token or phone), and something you are (biometrics). Service-to-service communication uses mutual TLS with short-lived certificates issued by internal certificate authorities. Microsegmentation limits lateral movement by enforcing fine-grained network policies between workloads. Continuous verification re-evaluates trust based on device health, user behavior, and threat intelligence. The NIST SP 800-207 framework defines zero-trust architecture principles including resource access determined by policy, authentication and authorization enforced before access, and collection of telemetry for improving policy.

Supply chain security protects the integrity of software from development through deployment. Software Bill of Materials (SBOM) enumerates all components including dependencies, enabling vulnerability tracking. SLSA (Supply chain Levels for Software Artifacts) defines four levels of build integrity, from basic provenance (level 1) to hermetic, reproducible builds with two-party review (level 4). Sigstore provides free code signing through Cosign (container signing), Fulcio (certificate authority), and Rekor (transparency log). Dependency confusion attacks exploit package managers that check public registries before private ones, uploading malicious packages with names matching internal packages. Mitigations include namespace reservation, registry scoping, and hash pinning in lock files.

Distributed consensus algorithms form the backbone of modern fault-tolerant systems. The Paxos algorithm, proposed by Leslie Lamport, achieves consensus among a group of processes even when some of them fail. In Paxos, a proposer sends a prepare request with a proposal number to a majority of acceptors. Each acceptor promises not to accept proposals with lower numbers and responds with the highest-numbered proposal it has already accepted. The proposer then sends an accept request with the highest value from the responses, or its own value if none were returned. Once a majority of acceptors accept a proposal, consensus is reached.

Raft was designed as a more understandable alternative to Paxos. It separates consensus into three sub-problems: leader election, log replication, and safety. In Raft, one server is elected as leader and manages log replication to follower nodes. The leader accepts client requests, appends entries to its log, and replicates them to followers. When a majority acknowledge, the entry is committed. If the leader fails, a new election occurs using randomized timeouts to avoid split votes. Raft's clarity has made it popular in systems like etcd, CockroachDB, and TiKV.

Byzantine fault tolerance (BFT) handles a more challenging scenario where nodes may behave arbitrarily, including maliciously. Practical Byzantine Fault Tolerance (PBFT) by Castro and Liskov requires 3f+1 nodes to tolerate f Byzantine faults. The protocol proceeds through three phases: pre-prepare, prepare, and commit. The primary node sequences requests and broadcasts pre-prepare messages. Replicas verify and broadcast prepare messages. Once 2f+1 matching prepare messages are collected, nodes broadcast commit messages. After receiving 2f+1 commits, the operation is executed. While PBFT has O(n^2) message complexity, later protocols like HotStuff reduced this to O(n) using a three-phase pipeline with threshold signatures.

Vector clocks provide a mechanism for tracking causality in distributed systems without synchronized physical clocks. Each process maintains a vector of logical timestamps, one per process. When a process performs a local event, it increments its own entry. When sending a message, it attaches its vector clock. Upon receiving, the recipient takes the element-wise maximum of its clock and the received clock, then increments its own entry. Two events are causally ordered if one vector is element-wise less than or equal to the other; otherwise they are concurrent. This enables conflict detection in systems like Amazon's Dynamo and Riak.

B-tree indexes are the workhorse of relational database storage engines. A B-tree of order m allows each node to have at most m children and at least ceil(m/2) children (except the root). Keys within each node are sorted, and the tree remains balanced through split and merge operations during insertions and deletions. The height of a B-tree with n keys is O(log_m(n)), ensuring logarithmic lookup time. Most database implementations use B+ trees, where all data resides in leaf nodes connected by sibling pointers, enabling efficient range scans.

Write-ahead logging (WAL) ensures durability and atomicity in database systems. Before any modification reaches the data pages, the corresponding log records are written to stable storage. Each log record contains a log sequence number (LSN), the transaction ID, the page ID, and before/after images of the modification. During recovery, the database replays the log forward (redo) to restore committed changes and backward (undo) to rollback uncommitted transactions. ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the gold standard for WAL-based recovery, using three passes: analysis, redo, and undo.

Multi-version concurrency control (MVCC) allows readers and writers to operate concurrently without blocking each other. Each write creates a new version of the data rather than overwriting in place. Readers see a consistent snapshot based on their transaction's start timestamp. PostgreSQL implements MVCC by storing multiple row versions in the heap, with each version tagged by creation and deletion transaction IDs. Garbage collection (vacuum) removes versions no longer visible to any active transaction. MySQL's InnoDB uses undo logs to reconstruct older versions on demand, avoiding the storage overhead of keeping all versions in the main data structure.

Transaction isolation levels define the degree to which concurrent transactions are insulated from each other. Read Uncommitted allows dirty reads. Read Committed prevents dirty reads but allows non-repeatable reads. Repeatable Read prevents both but may allow phantom reads. Serializable ensures complete isolation, as if transactions executed sequentially. Implementation strategies include two-phase locking (2PL), optimistic concurrency control (OCC), and serializable snapshot isolation (SSI). SSI, used in PostgreSQL 9.1+, detects dangerous structures of read-write conflicts at commit time rather than acquiring locks upfront.

Lexical analysis transforms a stream of characters into a stream of tokens. The scanner typically uses a deterministic finite automaton (DFA) constructed from regular expressions. For example, an identifier might be matched by [a-zA-Z_][a-zA-Z0-9_]*, while integer literals match [0-9]+. Modern scanner generators like flex or re2c compile these patterns into efficient table-driven or direct-coded automata. The longest-match rule resolves ambiguity: the scanner always returns the longest possible token. Keywords are often recognized by a hash table lookup after an identifier is matched rather than by separate DFA states.

Parsing transforms a token stream into an abstract syntax tree (AST). LL parsers read input Left-to-right and produce a Leftmost derivation, while LR parsers produce a Rightmost derivation in reverse. Recursive descent parsers implement LL(1) grammars directly as a set of mutually recursive functions. LALR(1) parsers, generated by tools like yacc and bison, use a parse table with states, shift/reduce actions, and goto entries. The table is constructed from LR(0) item sets augmented with lookahead information. Operator precedence parsing handles expression grammars efficiently by associating precedence levels and associativity with operators, as in Pratt parsing.

Static single assignment (SSA) form is an intermediate representation where each variable is assigned exactly once. Phi functions at control flow join points merge values from different predecessors. SSA simplifies many optimizations: constant propagation becomes trivial because each definition uniquely determines the value at all uses. Dead code elimination reduces to removing definitions with no uses. The dominance frontier algorithm by Cytron et al. efficiently places phi functions. Global value numbering on SSA form discovers redundant computations by hashing expressions and recognizing when two computations produce the same value.

Register allocation assigns an unbounded number of virtual registers to a finite set of physical registers. Graph coloring allocates registers by building an interference graph where nodes are variables and edges connect simultaneously live variables. The graph is then colored with k colors (one per physical register). Chaitin's algorithm simplifies nodes with degree less than k, colors the simplified graph, and spills variables that cannot be colored. Linear scan allocation offers faster compilation by processing live intervals in order, maintaining an active set, and spilling the interval with the farthest next use when no register is available. Modern JIT compilers like V8's TurboFan use variations of linear scan for its speed.

Virtual memory provides each process with an isolated address space mapped to physical memory through page tables. The Memory Management Unit (MMU) translates virtual addresses to physical addresses using a multi-level page table structure. On x86-64, a four-level page table (PML4, PDPT, PDT, PT) maps 48-bit virtual addresses to physical frames. Each page table entry contains the physical frame number, present/absent bit, read/write permissions, user/supervisor mode, and dirty/accessed bits. Translation Lookaside Buffers (TLBs) cache recent translations; a TLB miss triggers a page table walk. Huge pages (2MB or 1GB) reduce TLB pressure for large memory workloads by using fewer, larger mappings.

The Linux kernel's Completely Fair Scheduler (CFS) uses a red-black tree of tasks sorted by virtual runtime (vruntime). Each task's vruntime advances at a rate inversely proportional to its weight (derived from its nice value). The task with the smallest vruntime is always selected next, ensuring fairness over time. CFS uses a configurable scheduling latency period during which all runnable tasks should run at least once. The minimum granularity prevents excessive context switching when many tasks compete. Real-time tasks use SCHED_FIFO or SCHED_RR policies that preempt CFS tasks. The bandwidth throttling mechanism limits CPU time for real-time groups to prevent starvation of normal tasks.

Memory-mapped I/O allows devices to be accessed through load and store instructions to specific physical addresses. In contrast, port-mapped I/O uses dedicated in/out instructions. Modern devices use memory-mapped I/O with Base Address Registers (BARs) configured during PCI enumeration. DMA (Direct Memory Access) enables devices to transfer data directly to/from memory without CPU involvement. The CPU sets up DMA descriptors specifying source, destination, and length, then signals the device. Scatter-gather DMA supports non-contiguous memory regions using descriptor chains. IOMMU (I/O Memory Management Unit) provides address translation and isolation for DMA, preventing devices from accessing unauthorized memory regions.

File systems organize persistent data through a hierarchy of directories and files. ext4 uses an extent-based allocation scheme where each extent maps a contiguous range of logical blocks to physical blocks, reducing metadata overhead for large files compared to indirect block pointers. The journal (JBD2) records metadata changes before committing them to the main file system, enabling fast crash recovery. XFS uses B+ trees extensively for directory entries, free space tracking, and extent allocation. ZFS and Btrfs implement copy-on-write semantics where modifications create new blocks rather than overwriting existing ones, enabling atomic snapshots and built-in checksumming for data integrity verification.

Symmetric encryption algorithms operate on fixed-size blocks or continuous streams. AES (Advanced Encryption Standard) processes 128-bit blocks through multiple rounds of SubBytes, ShiftRows, MixColumns, and AddRoundKey transformations. AES-128 uses 10 rounds, AES-192 uses 12, and AES-256 uses 14. The SubBytes step applies an S-box derived from the multiplicative inverse in GF(2^8), providing non-linearity. Modern CPUs include AES-NI instructions that execute entire rounds in single clock cycles, achieving throughputs exceeding 10 GB/s. ChaCha20, a stream cipher by Daniel Bernstein, operates on 512-bit states through 20 rounds of quarter-round operations mixing addition, XOR, and rotation. It achieves comparable security to AES while being faster on platforms without hardware AES acceleration.

Public-key cryptography enables secure communication without shared secrets. RSA security relies on the difficulty of factoring the product of two large primes. Key generation selects primes p and q, computes n=pq and phi=(p-1)(q-1), chooses public exponent e coprime to phi, and computes private exponent d as the modular inverse of e mod phi. Encryption computes c = m^e mod n, and decryption computes m = c^d mod n. RSA-2048 provides approximately 112 bits of security. Elliptic Curve Cryptography (ECC) achieves equivalent security with smaller key sizes: a 256-bit ECC key provides security comparable to RSA-3072. Operations on elliptic curves (point addition and scalar multiplication) over finite fields form the basis for ECDH key exchange and ECDSA signatures.

Hash functions map arbitrary-length inputs to fixed-length outputs. SHA-256 processes input in 512-bit blocks through 64 rounds of compression, producing a 256-bit digest. The Merkle-Damgard construction iteratively applies the compression function, with the previous output as the chaining value. SHA-3 (Keccak) uses a sponge construction that absorbs input blocks by XORing them into the state and applying a permutation, then squeezes output. BLAKE3 achieves high performance by using a Merkle tree structure enabling parallelism, with a core compression function based on ChaCha's quarter-round. Argon2, the Password Hashing Competition winner, defends against GPU and ASIC attacks by requiring configurable amounts of memory, time, and parallelism.

Transport Layer Security (TLS) 1.3 simplified the handshake to a single round trip. The client sends a ClientHello with supported cipher suites, key shares for likely groups, and a pre-shared key extension if resuming. The server responds with its key share, selected cipher suite, and encrypted extensions. Both sides derive traffic keys from the shared secret using HKDF (HMAC-based Key Derivation Function). Forward secrecy is mandatory: ephemeral Diffie-Hellman key exchange ensures that compromise of long-term keys does not reveal past session keys. AEAD (Authenticated Encryption with Associated Data) algorithms like AES-GCM and ChaCha20-Poly1305 provide both confidentiality and integrity.

Backpropagation computes gradients of the loss function with respect to each weight in a neural network by applying the chain rule of calculus. During the forward pass, each layer computes its output and caches intermediate values needed for gradient computation. During the backward pass, gradients flow from the loss through each layer in reverse order. For a fully connected layer y = Wx + b, the gradient with respect to W is the outer product of the incoming gradient and the cached input, while the gradient passed to the previous layer is W^T times the incoming gradient. Stochastic gradient descent (SGD) updates weights by subtracting the gradient scaled by the learning rate. Adam optimizer maintains per-parameter exponential moving averages of the gradient (first moment) and squared gradient (second moment), providing adaptive learning rates that converge faster than vanilla SGD.

Transformer architectures have revolutionized sequence modeling. Self-attention computes Query, Key, and Value projections from the input, then attention weights as softmax(QK^T / sqrt(d_k)), and finally the output as the weighted sum of values. Multi-head attention runs h parallel attention operations with different learned projections, concatenating results. Position information is injected through sinusoidal encodings or learned embeddings. The feed-forward network in each transformer block applies two linear transformations with a ReLU or GELU activation. Layer normalization stabilizes training by normalizing activations across the feature dimension. Pre-norm (normalizing before attention/FFN) has become standard as it enables more stable training of deep models.

Mixture of Experts (MoE) architectures replace the dense feed-forward layer with multiple expert networks and a gating mechanism. The gate produces a sparse routing distribution, selecting the top-k experts for each input token. This enables scaling model capacity (total parameters) while keeping compute (FLOPs per token) constant. Switch Transformer routes each token to a single expert, while GShard and ST-MoE use top-2 routing. Load balancing is critical: auxiliary losses penalize uneven expert utilization. Expert parallelism distributes experts across devices, with all-to-all communication routing tokens to their assigned experts. Capacity factors limit the maximum tokens per expert per batch, dropping excess tokens. Fine-grained experts (more, smaller experts) generally improve quality for the same compute budget.

Quantization reduces the precision of neural network weights and activations to enable faster inference. Post-training quantization (PTQ) converts a pre-trained model without retraining: weights are grouped, scales computed per group, and values rounded to the target precision. GPTQ uses second-order information (approximate Hessian) to minimize quantization error by jointly optimizing the rounding of columns in weight matrices. AWQ identifies salient weight channels based on activation magnitudes and scales them before quantization. INT4 weight-only quantization achieves 4x memory reduction with minimal quality loss for large language models. Mixed-precision strategies keep attention layers at higher precision while aggressively quantizing feed-forward layers, balancing speed and quality.

TCP congestion control prevents network collapse by adapting the sending rate to available bandwidth. The classic algorithm progresses through slow start (exponential growth), congestion avoidance (linear growth), and fast recovery. Slow start doubles the congestion window each round-trip time until reaching the slow-start threshold. Congestion avoidance increases the window by roughly one segment per RTT. On packet loss (detected by triple duplicate ACKs), fast retransmit resends the lost segment immediately, and fast recovery halves the congestion window. TCP CUBIC, the default in Linux, uses a cubic function of time since the last loss event, enabling faster window growth for high-bandwidth-delay-product networks. BBR (Bottleneck Bandwidth and Round-trip propagation time) by Google takes a different approach, modeling the network path to maximize throughput while minimizing latency, achieving significant improvements over loss-based algorithms.

HTTP/2 introduced multiplexing, allowing multiple requests and responses to share a single TCP connection through streams identified by unique IDs. Header compression (HPACK) uses Huffman coding and a dynamic table of previously transmitted headers, reducing overhead dramatically for repeated headers like cookies and user-agents. Server push enables proactive sending of resources before the client requests them. However, HTTP/2 suffers from head-of-line blocking at the TCP layer: a lost packet blocks all streams until retransmitted. HTTP/3 solves this by switching to QUIC, a UDP-based transport that provides independent stream processing. QUIC includes built-in encryption (TLS 1.3), 0-RTT connection establishment for resumed sessions, and connection migration across network changes using connection IDs rather than IP/port tuples.

BGP (Border Gateway Protocol) is the routing protocol of the internet, exchanging reachability information between autonomous systems (ASes). BGP uses path-vector routing where each route advertisement includes the full AS path, preventing loops. Route selection considers multiple attributes: local preference, AS path length, origin type, MED (Multi-Exit Discriminator), and community tags. eBGP peers exchange routes between different ASes, while iBGP distributes routes within an AS. Full-mesh iBGP requires O(n^2) sessions; route reflectors reduce this by centralizing route distribution. BGP security remains a concern: prefix hijacking occurs when an AS announces routes for IP space it doesn't own. RPKI (Resource Public Key Infrastructure) enables ASes to cryptographically verify the origin of route announcements.

DNS resolution translates domain names to IP addresses through a hierarchical delegation system. A recursive resolver queries root servers for the TLD (top-level domain) nameservers, then the TLD servers for the authoritative nameservers, and finally the authoritative servers for the actual records. Responses are cached according to TTL (Time To Live) values. DNSSEC adds cryptographic signatures to DNS records, allowing resolvers to verify authenticity using a chain of trust from the root zone. DNS over HTTPS (DoH) and DNS over TLS (DoT) encrypt queries to prevent eavesdropping and manipulation by network intermediaries. Modern resolvers like Unbound support prefetching, which refreshes popular cached entries before expiration to maintain low-latency responses.

Modern out-of-order processors execute instructions as their operands become available rather than in program order. The front end fetches instructions from the instruction cache, decodes them into micro-operations, and places them in the reorder buffer (ROB). The rename stage maps architectural registers to physical registers, eliminating false dependencies (WAR and WAW hazards). The scheduler dispatches ready micro-operations to execution units when their source operands are available. Results are written to the physical register file and broadcast to waiting instructions via the common data bus. The retirement stage commits completed instructions in program order, maintaining the illusion of sequential execution. Branch prediction is critical: a misprediction flushes the pipeline, wasting tens of cycles. Modern predictors like TAGE (TAgged GEometric history length) maintain multiple prediction tables indexed by different history lengths.

Cache hierarchies bridge the speed gap between fast processors and slow main memory. L1 caches (typically 32-64KB, 4-5 cycle latency) split into instruction and data caches. L2 caches (256KB-1MB, 12-15 cycles) are unified. L3 caches (8-256MB, 30-50 cycles) are shared across cores. Cache lines are typically 64 bytes. The MESI protocol (Modified, Exclusive, Shared, Invalid) maintains coherence across cores. When one core modifies a cache line, it transitions to Modified state and invalidates copies in other cores. Intel's ring bus or mesh interconnect carries coherence messages between cores and the LLC (Last Level Cache). NUMA (Non-Uniform Memory Access) architectures have memory directly attached to each processor socket; accessing remote memory incurs additional latency, making memory placement important for performance.

GPU architectures employ massive parallelism through thousands of lightweight threads organized into warps or wavefronts. NVIDIA's streaming multiprocessors (SMs) execute warps of 32 threads in lockstep SIMT (Single Instruction, Multiple Threads) fashion. Each SM has a register file, shared memory, L1 cache, and multiple execution units (INT32, FP32, FP64, tensor cores). Tensor cores perform matrix multiply-accumulate operations on 4x4 matrices, critical for deep learning workloads. GPU memory hierarchies include registers (fastest), shared memory (programmer-managed scratchpad), L1/L2 caches, and global GDDR6/HBM memory. Memory coalescing combines multiple thread memory accesses into fewer transactions when addresses fall within the same cache line. Occupancy (ratio of active warps to maximum warps) affects performance: higher occupancy hides memory latency through warp scheduling.

PCIe (Peripheral Component Interconnect Express) provides high-speed serial communication between CPUs and devices. PCIe 4.0 achieves 16 GT/s per lane with 128b/130b encoding, yielding ~2 GB/s per lane. A x16 slot provides ~32 GB/s bidirectional bandwidth. PCIe 5.0 doubles this to ~64 GB/s. The protocol stack includes the transaction layer (TLPs: memory read/write, completions, messages), data link layer (ACK/NAK, flow control), and physical layer (encoding, link training). CXL (Compute Express Link) builds on PCIe 5.0 to enable cache-coherent access to device-attached memory, allowing GPUs and accelerators to participate in the CPU's coherence domain.

Garbage collection automatically reclaims memory that is no longer reachable from the root set. Mark-sweep collectors traverse the object graph from roots, marking reachable objects, then sweep through the heap freeing unmarked objects. This causes fragmentation over time. Mark-compact collectors additionally relocate live objects to eliminate fragmentation, but require updating all pointers. Generational collectors exploit the weak generational hypothesis (most objects die young) by partitioning the heap into young and old generations. Minor collections frequently scan the young generation, promoting survivors to the old generation. Major collections scan the entire heap less frequently. G1 (Garbage First) divides the heap into regions and prioritizes collecting regions with the most garbage. ZGC and Shenandoah achieve sub-millisecond pause times through concurrent marking and relocation using colored pointers or Brooks forwarding pointers.

Type systems statically verify program properties at compile time. The Hindley-Milner type system infers the most general type for expressions without any type annotations, using Algorithm W based on unification. Parametric polymorphism (generics) allows functions and data structures to operate on any type. Rust's ownership system tracks which variable owns each piece of data and enforces that there is at most one mutable reference or any number of immutable references at any time, preventing data races at compile time. Lifetime annotations specify the relationship between reference lifetimes, enabling the borrow checker to verify memory safety. Algebraic data types (sum types like Rust's enum or Haskell's data) combined with pattern matching enable exhaustive handling of all cases, preventing null pointer errors.

Concurrency models vary significantly across languages. Go uses goroutines (lightweight green threads multiplexed onto OS threads) communicating through channels, following the CSP (Communicating Sequential Processes) model. The Go scheduler uses work stealing to balance goroutines across OS threads. Erlang processes are even lighter (a few hundred bytes each) with message-passing semantics and supervision trees for fault tolerance. Rust provides both message passing (channels) and shared state (Mutex, Arc) with compile-time data race prevention. Java's virtual threads (Project Loom) provide lightweight threads that automatically unmount from carrier OS threads during blocking operations. Python's asyncio uses cooperative multitasking with async/await syntax, running on a single-threaded event loop, suitable for I/O-bound workloads but limited by the GIL for CPU-bound parallelism.

Memory models define how threads observe each other's memory operations. The C++ memory model provides several ordering constraints: relaxed (no ordering guarantees beyond atomicity), acquire-release (synchronizes specific memory locations), and sequentially consistent (total order on all atomic operations). The x86 Total Store Order (TSO) model is relatively strong: loads are not reordered with other loads, stores are not reordered with other stores, and stores are not reordered with earlier loads. However, a load may be reordered with an earlier store to a different location. ARM and RISC-V have weaker memory models, requiring explicit fence instructions for ordering guarantees. Java's memory model defines happens-before relationships through synchronized blocks, volatile variables, and thread start/join operations.

Lock-free data structures enable concurrent access without traditional mutual exclusion, using atomic operations like compare-and-swap (CAS). A lock-free stack pushes by repeatedly reading the top pointer, setting the new node's next to it, and CAS-ing the top to the new node. If another thread modified the top between the read and CAS, the operation retries. The ABA problem occurs when a pointer value is reused: thread A reads top as node X, thread B pops X and pushes Y then pushes X again, and thread A's CAS succeeds even though the stack has changed. Solutions include tagged pointers (incrementing a counter with each CAS), hazard pointers (preventing reclamation of nodes being accessed), or epoch-based reclamation (batching deallocation to epochs when no thread is in a critical section).

Memory allocators significantly impact application performance. glibc's ptmalloc2 uses per-thread arenas to reduce contention, with each arena managing chunks through bins organized by size: fast bins (small, no coalescing), small bins (exact size), large bins (sorted by size), and unsorted bins (recently freed). jemalloc organizes memory into runs of same-sized regions within chunks, using thread-local caches and size-class-based allocation. tcmalloc (Google) maintains per-thread caches for small allocations and a central free list for larger ones, with periodic garbage collection to rebalance. mimalloc (Microsoft) uses sharded thread-local heaps with efficient free lists, achieving excellent performance across diverse workloads. All modern allocators must handle virtual memory fragmentation, page-level allocation, and transparent huge page interaction.

io_uring is Linux's modern asynchronous I/O interface, using shared ring buffers between user space and the kernel. The submission queue (SQ) contains entries describing I/O operations, and the completion queue (CQ) contains results. The application writes SQEs (submission queue entries) specifying the operation type (read, write, accept, connect, etc.), file descriptor, buffer, and offset. A single io_uring_enter system call can submit multiple operations and wait for completions simultaneously. Fixed files and fixed buffers avoid per-operation fd lookup and memory mapping overhead. Linked operations enable dependent sequences without returning to user space between steps. The SQPOLL mode uses a kernel thread to poll the submission queue, eliminating system calls entirely for sustained high-throughput workloads.

eBPF (extended Berkeley Packet Filter) enables safe, efficient programmability of the Linux kernel. eBPF programs are written in a restricted C subset, compiled to BPF bytecode, verified by the kernel's verifier (ensuring no infinite loops, valid memory access, and bounded execution), and JIT-compiled to native code. Programs attach to various kernel hooks: network packet processing (XDP, tc), tracing (kprobes, tracepoints, fentry), security (LSM), and scheduling. BPF maps provide shared state between eBPF programs and user space, supporting hash tables, arrays, ring buffers, and per-CPU variants. XDP (eXpress Data Path) processes packets at the earliest possible point in the network stack, achieving millions of packets per second for load balancing, firewalling, and DDoS mitigation.

Balanced binary search trees maintain O(log n) height guarantees through rotations and color/balance invariants. Red-black trees maintain five properties: every node is red or black, the root is black, leaves (NIL) are black, red nodes have black children, and all paths from a node to its leaves contain the same number of black nodes. Insertions may violate the red-parent property; fix-up involves recoloring and at most two rotations. AVL trees maintain a stricter balance: the height difference between left and right subtrees is at most one. This provides faster lookups (1.44 log n vs 2 log n worst case) but slower insertions due to more frequent rotations. B-trees generalize to multi-way branching, keeping all leaves at the same depth. With a branching factor of several hundred, B-trees minimize disk seeks by storing many keys per node, making them ideal for database indexes.

Skip lists provide probabilistic O(log n) search, insertion, and deletion. Each element is promoted to higher levels with probability p (typically 1/2 or 1/4). Searching starts at the highest level, moving forward while the next element is less than the target, then dropping down a level. Expected space is O(n) and expected height is O(log n). Skip lists are simpler to implement than balanced trees and support concurrent access more naturally through fine-grained locking or lock-free techniques. Redis uses skip lists for sorted sets because they support efficient range queries and have simpler concurrency characteristics than red-black trees.

Bloom filters provide space-efficient probabilistic set membership testing with no false negatives. An m-bit array is initialized to zeros. Insertion hashes the element with k independent hash functions, setting the corresponding bits. Query checks all k positions; if all are set, the element is probably in the set (with false positive probability approximately (1 - e^(-kn/m))^k for n elements). Counting Bloom filters replace bits with counters to support deletion. Cuckoo filters improve on Bloom filters by supporting deletion and achieving better space efficiency through cuckoo hashing with fingerprints. HyperLogLog estimates set cardinality using O(log log n) space: it hashes elements and tracks the maximum number of leading zeros, using stochastic averaging across multiple registers.

Consistent hashing distributes keys across a dynamic set of nodes while minimizing redistribution when nodes join or leave. Each node is mapped to multiple points on a hash ring using virtual nodes. A key is assigned to the first node encountered when walking clockwise from the key's position on the ring. When a node is added, it assumes responsibility for keys between it and its predecessor; only those keys need redistribution. Virtual nodes (multiple ring positions per physical node) ensure uniform distribution. Systems like Cassandra, DynamoDB, and Riak use consistent hashing for data partitioning. Rendezvous hashing (highest random weight) provides an alternative where each key computes a score for every node, selecting the highest; it offers better load distribution but requires evaluating all nodes.

Property-based testing generates random inputs to test program invariants rather than individual examples. QuickCheck pioneered this approach in Haskell, where developers specify properties like "reversing a list twice yields the original list" or "sorting produces a non-decreasing sequence." The framework generates hundreds of random inputs, and when a failure is found, automatically shrinks the input to a minimal failing case. Hypothesis (Python) and fast-check (JavaScript) bring property-based testing to mainstream languages. Stateful testing generates sequences of operations and verifies that a model (abstract state machine) stays in sync with the system under test. This approach has found bugs in databases, file systems, and distributed systems that example-based tests missed.

Chaos engineering proactively injects failures to verify system resilience. Netflix's Chaos Monkey randomly terminates instances in production, ensuring services handle individual node failures gracefully. Chaos Kong simulates entire availability zone failures. Litmus (now part of CNCF) provides a framework for running chaos experiments on Kubernetes: pod deletion, network partition, CPU/memory stress, and disk fill. Experiments define a steady state hypothesis (e.g., error rate below 1%), introduce turbulence, and verify the hypothesis still holds. Gradual rollout starts with non-critical environments and narrow blast radius, expanding as confidence grows. Game days bring teams together to practice incident response with controlled failure injection.

Observability encompasses logging, metrics, and tracing. Structured logging emits machine-parseable events (JSON) with consistent fields: timestamp, level, service, trace_id, and contextual attributes. Metrics track aggregated measurements: counters (monotonically increasing, e.g., request count), gauges (point-in-time values, e.g., queue depth), and histograms (distribution of values, e.g., latency percentiles). Prometheus scrapes metrics endpoints and evaluates alerting rules on time-series data. Distributed tracing follows a request across service boundaries using trace and span IDs propagated through headers. Each span records the service name, operation, duration, and status. Jaeger and Zipkin collect and visualize traces, revealing latency bottlenecks and error propagation paths across microservices.

Feature flags decouple deployment from release, allowing code to be shipped disabled and gradually enabled. Boolean flags gate simple on/off features. Percentage rollouts enable features for a fraction of users, increasing gradually while monitoring error rates and performance. User-targeting flags enable features for specific users, organizations, or segments. Kill switches provide instant rollback without redeployment. Flag evaluation should be fast (microseconds) and local (cached configuration). LaunchDarkly, Split.io, and open-source systems like Unleash and Flipt provide server-side evaluation with real-time configuration updates via streaming connections. Stale flags that are never cleaned up accumulate technical debt; flag lifecycle management includes creation date, owner, and scheduled removal.

Kubernetes orchestrates containerized workloads across clusters of machines. The control plane consists of the API server (RESTful interface), etcd (distributed key-value store for cluster state), the scheduler (assigns pods to nodes based on resource requirements and constraints), and controller managers (reconcile desired vs actual state). Worker nodes run kubelet (manages pod lifecycle), kube-proxy (implements service networking), and a container runtime (containerd or CRI-O). Pods are the smallest deployable units, containing one or more containers sharing network namespace and storage volumes. Deployments manage ReplicaSets that ensure the desired number of pod replicas are running. Rolling updates replace pods incrementally, while rollbacks revert to previous ReplicaSet configurations.

Service mesh architectures like Istio inject sidecar proxies (Envoy) alongside application containers. These proxies intercept all network traffic, providing transparent mutual TLS encryption, load balancing, circuit breaking, retries, and observability without application code changes. The control plane (istiod) distributes configuration to sidecar proxies using the xDS API. Traffic management rules enable canary deployments (routing a percentage of traffic to new versions), A/B testing, and fault injection for resilience testing. Authorization policies define fine-grained access control between services. Recent ambient mesh designs move proxy functionality from sidecars to node-level ztunnels and optional waypoint proxies, reducing resource overhead and operational complexity.

Infrastructure as Code (IaC) manages cloud resources through declarative configuration files. Terraform uses HCL (HashiCorp Configuration Language) to define providers, resources, data sources, and modules. The plan-apply workflow shows changes before execution. State tracks the mapping between configuration and real resources, stored in backends like S3 or Terraform Cloud. Pulumi allows infrastructure definition in general-purpose languages (TypeScript, Python, Go), enabling loops, conditionals, and abstractions. AWS CDK generates CloudFormation from TypeScript or Python constructs. GitOps extends IaC by using Git as the single source of truth: Argo CD or Flux continuously reconcile cluster state with repository definitions, automatically applying changes when commits are pushed.

Serverless computing abstracts away server management entirely. AWS Lambda executes functions in response to events (HTTP requests, queue messages, file uploads) with automatic scaling from zero to thousands of concurrent instances. Cold starts (initializing a new execution environment) add latency; provisioned concurrency keeps environments warm. Container-based serverless (AWS Fargate, Google Cloud Run) provides more flexibility than function-based systems, running arbitrary container images with per-request scaling. Event-driven architectures compose serverless functions with message queues (SQS), event buses (EventBridge), and step functions for orchestration. Edge computing pushes serverless execution to CDN points of presence: Cloudflare Workers, Lambda@Edge, and Deno Deploy run JavaScript/WebAssembly at the network edge with sub-millisecond cold starts.

Apache Kafka provides distributed, fault-tolerant event streaming. Topics are partitioned across brokers, with each partition being an ordered, immutable sequence of records. Producers append records to partitions based on a key hash or round-robin distribution. Consumer groups enable parallel processing: each partition is assigned to exactly one consumer in a group, and rebalancing redistributes partitions when consumers join or leave. Offsets track each consumer's position; committing offsets enables at-least-once processing (commit after processing) or at-most-once (commit before processing). Exactly-once semantics require idempotent producers and transactional reads from consumed topics to produced topics. Kafka Connect integrates with external systems through source connectors (ingest) and sink connectors (export) without custom code.

Stream processing engines compute continuous queries over unbounded data. Apache Flink maintains distributed state with exactly-once guarantees through checkpointing: barriers flow through the data stream, and when all sources advance past a barrier, operator state is snapshot to durable storage. Windowing groups events by time: tumbling windows (fixed, non-overlapping), sliding windows (fixed, overlapping), session windows (activity-based gaps), and global windows (custom triggers). Watermarks track event-time progress, allowing late events to be handled with allowed lateness periods or side outputs. Flink's RocksDB state backend enables state larger than memory by spilling to local SSD, with incremental checkpoints for efficient fault tolerance.

Data lake architectures store raw data in open formats on object storage. Delta Lake adds ACID transactions, schema enforcement, and time travel to Parquet files on S3/ADLS. The transaction log records every change as JSON entries, enabling concurrent reads and writes with optimistic concurrency control. Z-ordering co-locates related data within files, improving query performance for multi-dimensional filtering. Apache Iceberg provides similar capabilities with a different metadata design using manifest files listing data files with column-level statistics. Both support schema evolution (adding, dropping, renaming columns) and partition evolution (changing partitioning without rewriting data). The lakehouse pattern combines data lake storage with data warehouse query performance through these table formats.

ETL pipelines extract data from sources, transform it, and load it into target systems. Apache Airflow orchestrates these pipelines as directed acyclic graphs (DAGs) of tasks. Each task is an operator: BashOperator, PythonOperator, or provider-specific operators for databases, cloud services, and applications. Task dependencies define execution order, with sensors waiting for external conditions. The scheduler evaluates DAG files periodically, creating DAG runs for scheduled intervals. The executor backend (Celery, Kubernetes, or local) runs tasks in parallel according to resource constraints. dbt (data build tool) focuses on the transformation layer, compiling SQL models with ref() references into a dependency graph, enabling version control, testing, and documentation of data transformations.

Graph theory provides the mathematical foundation for network analysis and algorithm design. A graph G = (V, E) consists of vertices and edges. In directed graphs, edges have orientation; in undirected graphs, they do not. A path is a sequence of vertices connected by edges; a cycle is a path that starts and ends at the same vertex. A graph is connected if a path exists between every pair of vertices. Dijkstra's algorithm finds shortest paths from a source vertex by maintaining a priority queue of tentative distances, greedily extracting the minimum and relaxing adjacent edges. Its time complexity is O((V + E) log V) with a binary heap. The A* algorithm extends Dijkstra with a heuristic function estimating the remaining distance, exploring fewer nodes when the heuristic is admissible (never overestimates). For negative edge weights, Bellman-Ford iterates V-1 times over all edges, detecting negative cycles on the V-th iteration.

Information theory quantifies uncertainty and communication capacity. Shannon entropy H(X) = -sum(p(x) log2 p(x)) measures the expected information content of a random variable. For a fair coin, H = 1 bit; for a biased coin with p=0.9, H = 0.47 bits. Mutual information I(X;Y) = H(X) - H(X|Y) measures how much knowing Y reduces uncertainty about X. The channel capacity C = max I(X;Y) over input distributions gives the maximum reliable communication rate. Huffman coding achieves optimal prefix-free codes: build a binary tree bottom-up by repeatedly merging the two least probable symbols. Arithmetic coding encodes entire messages as single numbers in [0,1), achieving compression closer to the entropy than Huffman for skewed distributions. Kolmogorov complexity K(x) is the length of the shortest program that outputs x, providing an objective measure of randomness.

Linear algebra underlies machine learning, computer graphics, and scientific computing. Singular Value Decomposition (SVD) factors any matrix A into U * Sigma * V^T, where U and V are orthogonal and Sigma is diagonal with non-negative singular values. SVD enables dimensionality reduction (PCA), matrix approximation (truncated SVD), and pseudoinverse computation. The power method iteratively computes the dominant eigenvector by repeated matrix-vector multiplication and normalization. QR decomposition factors A = QR where Q is orthogonal and R is upper triangular, forming the basis for eigenvalue algorithms (QR iteration) and least squares solutions. Sparse matrix representations (CSR, CSC, COO) store only non-zero elements, enabling efficient computation on matrices with many zeros common in graph algorithms and finite element methods.

Probability theory enables reasoning under uncertainty. Bayes' theorem P(A|B) = P(B|A)P(A)/P(B) updates beliefs given new evidence. Markov chains model sequences where the next state depends only on the current state, not history. The stationary distribution pi satisfies pi = pi * P, where P is the transition matrix. Markov Chain Monte Carlo (MCMC) methods sample from complex probability distributions by constructing a Markov chain whose stationary distribution is the target distribution. The Metropolis-Hastings algorithm proposes new states and accepts them with probability min(1, (p(x')*q(x|x'))/(p(x)*q(x'|x))). Gibbs sampling, a special case, samples each variable conditionally on all others. These methods are fundamental to Bayesian inference, statistical physics, and generative modeling.

Memory safety vulnerabilities remain a leading cause of security breaches. Buffer overflows occur when writes exceed allocated bounds, overwriting adjacent memory. Stack-based overflows can overwrite return addresses, redirecting execution to attacker-controlled code. Modern mitigations include stack canaries (random values checked before function return), ASLR (Address Space Layout Randomization, randomizing base addresses of stack, heap, and libraries), DEP/NX (Data Execution Prevention, marking data pages as non-executable), and CFI (Control Flow Integrity, restricting indirect branch targets to valid destinations). Use-after-free vulnerabilities exploit dangling pointers to freed memory that has been reallocated for a different purpose. Temporal memory safety ensures pointers cannot be used after the pointed-to object's lifetime ends.

Web application security addresses vulnerabilities in the browser-server interaction model. Cross-Site Scripting (XSS) injects malicious scripts into web pages viewed by other users. Reflected XSS includes the payload in the request; stored XSS persists the payload in the application's database. Content Security Policy (CSP) headers restrict script sources, mitigating XSS by preventing inline scripts and limiting allowed domains. Cross-Site Request Forgery (CSRF) tricks authenticated users into performing unintended actions. Mitigations include anti-CSRF tokens (random values tied to the session and embedded in forms), SameSite cookie attributes, and checking the Origin header. SQL injection manipulates database queries by injecting SQL syntax through user inputs. Parameterized queries (prepared statements) separate SQL structure from data, preventing injection regardless of input content.

Zero-trust architecture assumes no implicit trust based on network location. Every access request is authenticated, authorized, and encrypted regardless of origin. Identity becomes the primary security perimeter rather than network boundaries. Multi-factor authentication combines something you know (password), something you have (hardware token or phone), and something you are (biometrics). Service-to-service communication uses mutual TLS with short-lived certificates issued by internal certificate authorities. Microsegmentation limits lateral movement by enforcing fine-grained network policies between workloads. Continuous verification re-evaluates trust based on device health, user behavior, and threat intelligence. The NIST SP 800-207 framework defines zero-trust architecture principles including resource access determined by policy, authentication and authorization enforced before access, and collection of telemetry for improving policy.

Supply chain security protects the integrity of software from development through deployment. Software Bill of Materials (SBOM) enumerates all components including dependencies, enabling vulnerability tracking. SLSA (Supply chain Levels for Software Artifacts) defines four levels of build integrity, from basic provenance (level 1) to hermetic, reproducible builds with two-party review (level 4). Sigstore provides free code signing through Cosign (container signing), Fulcio (certificate authority), and Rekor (transparency log). Dependency confusion attacks exploit package managers that check public registries before private ones, uploading malicious packages with names matching internal packages. Mitigations include namespace reservation, registry scoping, and hash pinning in lock files.

Distributed consensus algorithms form the backbone of modern fault-tolerant systems. The Paxos algorithm, proposed by Leslie Lamport, achieves consensus among a group of processes even when some of them fail. In Paxos, a proposer sends a prepare request with a proposal number to a majority of acceptors. Each acceptor promises not to accept proposals with lower numbers and responds with the highest-numbered proposal it has already accepted. The proposer then sends an accept request with the highest value from the responses, or its own value if none were returned. Once a majority of acceptors accept a proposal, consensus is reached.

Raft was designed as a more understandable alternative to Paxos. It separates consensus into three sub-problems: leader election, log replication, and safety. In Raft, one server is elected as leader and manages log replication to follower nodes. The leader accepts client requests, appends entries to its log, and replicates them to followers. When a majority acknowledge, the entry is committed. If the leader fails, a new election occurs using randomized timeouts to avoid split votes. Raft's clarity has made it popular in systems like etcd, CockroachDB, and TiKV.

Byzantine fault tolerance (BFT) handles a more challenging scenario where nodes may behave arbitrarily, including maliciously. Practical Byzantine Fault Tolerance (PBFT) by Castro and Liskov requires 3f+1 nodes to tolerate f Byzantine faults. The protocol proceeds through three phases: pre-prepare, prepare, and commit. The primary node sequences requests and broadcasts pre-prepare messages. Replicas verify and broadcast prepare messages. Once 2f+1 matching prepare messages are collected, nodes broadcast commit messages. After receiving 2f+1 commits, the operation is executed. While PBFT has O(n^2) message complexity, later protocols like HotStuff reduced this to O(n) using a three-phase pipeline with threshold signatures.

Vector clocks provide a mechanism for tracking causality in distributed systems without synchronized physical clocks. Each process maintains a vector of logical timestamps, one per process. When a process performs a local event, it increments its own entry. When sending a message, it attaches its vector clock. Upon receiving, the recipient takes the element-wise maximum of its clock and the received clock, then increments its own entry. Two events are causally ordered if one vector is element-wise less than or equal to the other; otherwise they are concurrent. This enables conflict detection in systems like Amazon's Dynamo and Riak.

B-tree indexes are the workhorse of relational database storage engines. A B-tree of order m allows each node to have at most m children and at least ceil(m/2) children (except the root). Keys within each node are sorted, and the tree remains balanced through split and merge operations during insertions and deletions. The height of a B-tree with n keys is O(log_m(n)), ensuring logarithmic lookup time. Most database implementations use B+ trees, where all data resides in leaf nodes connected by sibling pointers, enabling efficient range scans.

Write-ahead logging (WAL) ensures durability and atomicity in database systems. Before any modification reaches the data pages, the corresponding log records are written to stable storage. Each log record contains a log sequence number (LSN), the transaction ID, the page ID, and before/after images of the modification. During recovery, the database replays the log forward (redo) to restore committed changes and backward (undo) to rollback uncommitted transactions. ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the gold standard for WAL-based recovery, using three passes: analysis, redo, and undo.