Computing & Embedded Topics
53 topics
- Computing & Embedded
Leader Election and Securing a Single Coordinator in Distributed Systems
An essay-style treatment of leader election, the mechanism by which equal nodes choose a single leader holding write and coordination authority and hand it over on failure, covering safety and liveness requirements and the FLP limit, the Bully, Ring, Raft/Paxos consensus, and lease-based algorithms, term numbers and majority quorums, split-brain prevention with fencing tokens, cases in ZooKeeper, etcd, Kafka KRaft, and Kubernetes Lease, failure-detection sensitivity tuning with pre-vote, and professional considerations on quorum design, membership change, and build-versus-buy strategy.
- Computing & Embedded
The Roofline Model and Performance Analysis
A visual performance model plotting a compute kernel's arithmetic intensity (FLOP/Byte) on the horizontal axis and peak compute and memory bandwidth as two roofs, diagnosing at a glance whether performance is compute bound or memory bound. Attainable performance P=min(peak, bandwidth x intensity); the ridge point I*=peak/bandwidth separates memory bound (left) from compute bound (right). Arithmetic intensity is a design variable movable by tiling and fusion, and the gap between the performance point and the roof reveals optimization room. It extends to compute ceilings (vectorization, FMA) and bandwidth ceilings (NUMA, prefetch), and to hierarchical rooflines per memory level. Mixed precision and tensor cores create multilayered roofs, and it explains why small-batch LLM decode is memory bound, becoming a common diagnostic language for HPC and AI acceleration.
- Computing & Embedded
CAN (Controller Area Network) and In-Vehicle Networks
A multi-master fieldbus for vehicles and industry in which many ECUs share a two-wire bus and realize low-cost, high-reliability real-time communication via message-priority non-destructive bitwise arbitration and multi-layer error confinement. Covers the evolution to CAN FD/CAN XL and Automotive Ethernet and security (SecOC).
- Computing & Embedded
Hash Table
A data structure that maps a key to an array index via a hash function to perform insertion, lookup, and deletion in average O(1). It resolves collisions with chaining or open addressing and preserves amortized O(1) via load-factor management and rehashing, covering hash-function distribution quality, the worst case, HashDoS, and concurrency.
- Computing & Embedded
Actor Model
A model of concurrent computation in which lightweight, share-nothing actors communicate solely through asynchronous message passing. State encapsulation and sequential mailbox processing achieve lock-free massive concurrency, while a supervision tree and the 'Let it crash' philosophy isolate faults and self-heal. Location transparency lets single-node code scale to a distributed cluster, proven in high-availability systems for messaging, games, and telecom such as Erlang/OTP, Akka, Elixir, and Microsoft Orleans. It covers the differences from shared memory+locks, CSP, and reactive streams, and the trade-offs of message-guarantee levels, mailbox backlog, and persistence design.
- Computing & Embedded
P versus NP and NP-Completeness
The P-NP problem asks whether a problem whose solution is easy to verify (NP) is also easy to solve (P)—an open question of computational complexity theory. NP-completeness, via polynomial-time reduction and the Cook-Levin theorem, binds the "hardest" problems to which all of NP reduces (SAT, TSP, graph coloring, 0/1 knapsack, and thousands more) into a single community of fate, where a polynomial-time algorithm for any one implies P=NP. Once a problem is shown NP-complete, one must pivot from a perfect optimal method to approximation, heuristics/metaheuristics, parameterization, and special-input strategies; this classification and trade-off judgment underpins design quality and public-key cryptographic security strategy.
- Computing & Embedded
Greedy Algorithm
A problem-solving strategy that aims at the global optimum by making the locally optimal choice at each step and never revoking it; it guarantees correctness only when the greedy choice property and optimal substructure (and further, a matroid) hold. Under those conditions it yields provably optimal solutions in polynomial time—minimum spanning tree (Kruskal/Prim), Huffman coding, activity selection, fractional knapsack—but when conditions break (0/1 knapsack, non-canonical coin systems) it falls into the local optimum trap and gives a wrong answer, so legitimacy must be verified via the exchange argument. For NP-hard problems it provides practical solutions with a guaranteed ratio such as the ln n approximation for set cover. The key is to diagnose the boundary with dynamic programming and brute force and select the right paradigm at the balance point of correctness and performance.
- Computing & Embedded
Flynn's Taxonomy and Parallel Computing Architectures
The most fundamental framework for classifying parallel computing architectures, proposed by Michael J. Flynn in 1966, which divides computers by the number of instruction and data streams into SISD, SIMD, MISD, and MIMD. SISD is the archetype of sequential execution; SIMD applies one instruction to bulk data to exploit data parallelism (vector units, GPUs); MISD is a rare, fault-tolerance-oriented category; and MIMD is the most flexible structure running multiple instruction streams on different data, splitting into shared memory (SMP/NUMA) and distributed memory (clusters). The GPU's SIMT is a thread-level extension of SIMD, and real systems are heterogeneous, nesting SIMT GPUs and vector units inside MIMD nodes. It is treated as the first-order architectural decision frame, alongside the scaling limits of Amdahl's and Gustafson's laws and the data-movement costs of NUMA, interconnects, and cache coherence.
- Computing & Embedded
Shortest Path Algorithm
A family of algorithms that find the minimum-weight path in a weighted graph. On the basis of relaxation and optimal substructure, it divides into greedy Dijkstra (strong for single-source on positive graphs), DP Bellman-Ford (handling negative edges/cycles), Floyd-Warshall (all-pairs), and A* (focusing search on the destination via a heuristic). Used in OSPF (link-state, Dijkstra) and RIP (distance-vector, Bellman-Ford) routing, navigation, game pathfinding, and arbitrage detection; the key is to diagnose weight nature, query scope, and graph scale and select/accelerate (A*, Contraction Hierarchies, bidirectional search) at the balance point of accuracy and performance.
- Computing & Embedded
Parallel Performance Laws (Amdahl's Law and Gustafson's Law)
Two complementary laws describing the speedup from adding processors — Amdahl's Law, where with fixed work the serial fraction sets the ceiling on speedup (1/(1−p)) under strong scaling, and Gustafson's Law, where scaling the problem size lets performance grow almost linearly with processor count under weak scaling — organizing their formulas, numbers, and differing assumptions, together with the Universal Scalability Law (USL) that reflects contention and communication costs to point out the realistic optimal concurrency, its application to multicore, GPU distributed training, and Spark, and the professional-engineer-level strategy for capacity planning and investment decisions.
- Computing & Embedded
Video Codecs and Video Compression (H.264·HEVC·AV1·VVC)
A lossy-compression technology that removes spatial·temporal·statistical·psycho-visual redundancy through hybrid block-based coding (prediction → transform·quantization → entropy → in-loop filter) — covering the cross-generation efficiency of H.264·HEVC·VVC·AV1 and the selection strategy from the standpoint of hardware decoding·license·ecosystem.
- Computing & Embedded
Dynamic Programming
An algorithm design technique that, for problems with optimal substructure and overlapping subproblems, decomposes the problem into subproblems and stores/reuses their solutions to reduce exponential search to polynomial time — covering memoization/tabulation and a comparison with greedy and divide-and-conquer.
- Computing & Embedded
AUTOSAR (Automotive Standard Software Architecture)
An open automotive SW standard that decouples ECU software from hardware to enable reuse·portability·collaboration — covering the static·real-time Classic Platform (layered structure·VFB·RTE·BSW/MCAL) and the dynamic·service-oriented Adaptive Platform (ARA·ara::com·SOME/IP·OTA), bound by the Foundation·ARXML methodology, plus CP-vs-AP comparison and SDV·security-safety integration trends (R25-11·DDS·Rust·CAPI), in essay form.
- Computing & Embedded
Queueing Theory and IT System Performance Modeling
A theory that quantifies with probabilistic models the waiting created by irregular arrivals and finite service. It predicts response time and capacity with Little's Law and the M/M/c formula, and shows that latency surges nonlinearly as utilization rises—the foundation for IT performance design and capacity planning.
- Computing & Embedded
Virtual Memory and Page Replacement Algorithms
A core OS memory-management technique that provides an independent address space decoupled from physical memory and loads only the pages needed for execution — covering address translation (TLB, page tables) and demand paging with page-fault handling, the effective-access-time (EAT) sensitivity, a numerical comparison of OPT, FIFO, LRU, and Clock replacement algorithms and Belady's anomaly, frame allocation and working-set-based thrashing countermeasures, and advances from huge pages, nested paging, and MGLRU to CXL tiered memory and memory compression, organized in depth from a professional-engineer perspective.
- Computing & Embedded
Byzantine Fault Tolerance (BFT) and PBFT
The strongest fault-tolerance technology that preserves consensus through an N≥3f+1 quorum and multiple cross-verification even in an adversarial environment where nodes send lying, contradictory messages — covering the Byzantine Generals problem, signatures and the quorum principle, PBFT's Pre-prepare·Prepare·Commit phases and view change, comparison with CFT·PoW, and scalable BFT such as HotStuff·PoS with blockchain·CBDC application.
- Computing & Embedded
Interrupt and DMA (Direct Memory Access)
An essay-form treatment of the two foundational techniques that bridge the speed gap between the CPU and I/O devices. The interrupt is an event-driven control transfer that frees the CPU from busy waiting; it covers the handling cycle (context save, vector branch, ISR, return), vectored/nested/priority handling, the exception-vs-hardware, maskable-vs-NMI, and edge-vs-level types, and the decomposition of interrupt latency. DMA entrusts data movement to a dedicated controller to free the CPU from copying; it covers the transfer procedure, cache coherence, cycle-stealing/burst/transparent modes, and scatter-gather and descriptor rings. It compares polling, interrupts, and DMA, and presents recent trends such as MSI-X, IOMMU, interrupt coalescing, and virtualized interrupts, along with professional-engineer implications from the real-time, security, multicore, and power perspectives.
- Computing & Embedded
Process Synchronization
A technique that coordinates the execution order and timing of processes/threads accessing shared resources concurrently to preserve consistency — the three requirements of the critical section problem (mutual exclusion, progress, bounded waiting) and Peterson's algorithm, a comparison of semaphore (P/V), mutex (ownership), and monitor (condition variables) stacked on TAS/CAS atomic instructions, the classic producer-consumer, readers-writers, and dining-philosophers problems and their solutions, recent trends such as lock-free, memory barriers, and distributed locks, and professional-engineer considerations such as the transition into deadlock/starvation/priority inversion, granularity, observability, and formal verification, organized as an essay.
- Computing & Embedded
SOTIF (ISO 21448, Safety of the Intended Functionality)
An essay-form treatment of SOTIF (ISO 21448:2022), the automotive safety standard for risk that arises—without any fault—from the performance limits and misperception of the intended function. It covers the division of labor with ISO 26262 (which handles the fault space), the strategy of dividing scenarios into four areas (Area 1–4) of known×safe to shrink Area 2·3, the concepts of triggering condition·functional insufficiency·performance limitation·ODD·reasonably foreseeable misuse, the distinction between verification and validation and the approval trap, minimal risk state·acceptance criteria (GAMAB·MEM·ALARP), recent trends linking ISO/PAS 8800 (AI safety)·UL 4600·ISO/SAE 21434, and the professional-engineer considerations around ODD design·data governance·continuous safety assurance.
- Computing & Embedded
Dynamic Voltage and Frequency Scaling (DVFS)
A power-management technique that adjusts supply voltage and operating frequency together at run time to pull down the V²·f term; covers the dynamic/static power model, control governors (schedutil, Intel Speed Shift/HWP) and heterogeneous big.LITTLE/EAS, the race-to-idle vs. low-voltage trade-off, application cases from mobile to HPC, and the security surface exposed by Plundervolt and Hertzbleed.
- Computing & Embedded
Zero-Copy I/O and Kernel Bypass
Explains the principle of zero-copy I/O—removing unnecessary CPU copies between kernel and user space to save CPU, memory bandwidth, and cache—by contrasting it with the traditional four-copy read/write path, compares implementation techniques such as mmap, sendfile, scatter-gather DMA, and splice with the RDMA, DPDK, and io_uring kernel bypass, and organizes application cases in Kafka, Netflix, and AI data centers along with adoption strategy and trade-offs.
- Computing & Embedded
Garbage Collection
An automatic memory-management technique in which the runtime identifies and reclaims unreachable heap objects — covering the background in the dangers of manual management (leaks, dangling pointers), root sets and reachability with precise/conservative collection, reference counting, mark-sweep-compact, copying, and generational collection (weak generational hypothesis, write barriers, remembered sets), tri-color marking and concurrent-mark consistency, a comparison of Serial/Parallel/CMS/G1/ZGC/Shenandoah collectors with STW, safepoints, and concurrent-mode failure, recent trends such as Generational ZGC, the Go GC, and container awareness with a Kubernetes JVM case, and professional-engineer considerations including the latency/throughput/memory-cost trade-off, logical leaks, language choice, and security.
- Computing & Embedded
LoRaWAN (Low-Power Wide-Area Network, LPWAN)
An LPWAN MAC protocol running on the LoRa (CSS) physical layer in the unlicensed Sub-GHz band, delivering small-volume data over long distances at ultra-low power via a star-of-stars architecture, ADR, Classes A/B/C, and dual AES-128 keys — an IoT wide-area connectivity technology combined selectively with NB-IoT and others based on traffic profile and data sovereignty.
- Computing & Embedded
ISO 26262 (Automotive Functional Safety)
An international functional safety standard that reduces the risk of automotive E/E malfunction to an acceptable level — grading risk via HARA→ASIL (A–D), unfolding the safety lifecycle and V-model, quantifying random hardware failures with the SPFM·LFM·PMHF metrics, and covering ASIL decomposition·SEooC·FTTI plus the convergence with SOTIF (21448)·ISO/SAE 21434·AI-safety standards in the autonomous-driving era, in essay form.
- Computing & Embedded
Speculative Execution & Branch Prediction
A topic on branch prediction, which guesses a conditional branch's direction/target in advance to fill the gaps of a deep pipeline, and speculative execution, which pulls not-yet-resolved instructions in and runs them on that guess, rolling back on misprediction — covering the BHT 2-bit saturating counter, BTB, RAS, and correlating/tournament/TAGE predictors, ROB- and register-renaming-based misprediction recovery, control/data speculation, and the Spectre·Meltdown transient-execution attacks (where the architectural state recovers but cache traces remain) and their mitigations, organized from a professional-engineer perspective.
- Computing & Embedded
Cache Coherence Protocol (Cache Coherence, MESI)
A hardware state machine that manages copies of the same block scattered across multicore private caches in Modified·Exclusive·Shared·Invalid states to guarantee the visibility of a single latest value — covering the write-propagation/serialization requirements, invalidate vs. update policy, the scalability trade-off of snooping vs. directory, MESI transitions and the MOESI/MESIF extensions, the false-sharing performance trap, and recent trends such as CXL and HTM, from a professional-engineer perspective.
- Computing & Embedded
CPU Scheduling
A core operating-system technique that selects the next process to run from the ready queue to extract the efficiency of multiprogramming — covering process state transitions and the long/medium/short-term scheduler layers, preemptive vs. non-preemptive scheduling and the trade-offs among performance metrics, a numerical comparison of FCFS, SJF, priority, RR, and MLFQ, countermeasures for the convoy effect, starvation, and priority inversion, and practice from Linux CFS/EEVDF and heterogeneous-multicore energy-aware scheduling to Kubernetes CFS throttling, organized in depth from a professional-engineer perspective.
- Computing & Embedded
Real-Time Operating System (RTOS)
An operating system whose primary goal is not throughput but determinism that guarantees a response within a deadline — distinguishing hard/firm/soft real-time, the schedulability trade-off between preemptive priority scheduling and RMS·EDF, realizing predictability with priority inheritance·fixed-block memory·upper-bounded interrupts, and covering the GPOS comparison and the PREEMPT_RT·mixed-criticality·TSN trends in an essay form.
- Computing & Embedded
Intermittent Computing
Ultra-low-power computing that preserves and restores state using checkpointing and non-volatile memory under intermittent power from energy harvesting.
- Computing & Embedded
Gossip Protocol for Distributed State Dissemination
An essay-style treatment of the Gossip Protocol, which spreads membership, event, and configuration state without a central bottleneck by repeatedly exchanging information with a small set of peers, covering push, pull, and push-pull dissemination, fanout and convergence, SWIM-style failure detection, duplicate and conflict handling, network partitions, comparison with broadcast, consensus, and message queues, service discovery and cache invalidation cases, and engineering considerations for security, observability, and tuning.
- Computing & Embedded
Logical Clocks in Distributed Systems
A logical clock tracks the happens-before ordering and causality of events using only process counters and message exchange, without trusting the drift/skew of physical time — covering the Lamport scalar clock that gives a total order and the vector clock that even detects concurrency, their clock-condition and metadata-cost comparison, physical-logical hybrids such as HLC/TrueTime, and application to ordering and conflict resolution in Dynamo, CRDTs, and distributed DBs, in essay form.
- Computing & Embedded
Sorting Algorithms (Bubble, Insertion, Quick)
A comparison of the operation, complexity, and stability of bubble and insertion sort (O(n²)) and quicksort (average O(n log n) divide-and-conquer).
- Computing & Embedded
Linear Data Structures: Stack, Queue, and List
The input/output principles, operations, uses, and comparison of the linear data structures stack (LIFO), queue (FIFO), and list (random access).
- Computing & Embedded
Data Structures: Linear and Non-Linear
Concepts and types of linear structures (stack, queue, list) and non-linear structures (tree, graph), and a comparison based on their connection forms.
- Computing & Embedded
Paging and Segmentation
The concepts, address translation, and comparison of fixed-size paging (internal fragmentation) and logical-unit segmentation (external fragmentation), along with paged segmentation as a combination and TLB acceleration.
- Computing & Embedded
Parallel-Processing Interconnection Networks and the Torus
The communication structure connecting processors and memory that governs parallel performance. Bus, crossbar, mesh, and hypercube; the torus shortens distance and provides symmetric distribution by connecting the mesh edges.
- Computing & Embedded
Directed Acyclic Graph (DAG) and Topological Sort
A directed, cycle-free graph expressing precedence and dependency. Topological sort (Kahn: remove nodes with in-degree 0 first) determines build and scheduling order.
- Computing & Embedded
Non-Uniform Memory Access (NUMA)
A ccNUMA structure that directly attaches local memory to each processor for scalability at the cost of differing local/remote access latency — providing an in-depth treatment of the composition of nodes, interconnects, and integrated memory controllers; locality alignment across the OS, application, and virtualization (vNUMA) layers such as first-touch, affinity, and interleave; false sharing and cache-coherence traffic; comparison with UMA and distributed memory; and extension to CXL and tiered memory.
- Computing & Embedded
CRDT (Conflict-Free Replicated Data Type)
A replicated data type that, thanks to the commutativity, associativity, and idempotency of its merge operation, necessarily converges (SEC) to the same state even when multiple replicas update independently without coordination — covering state/operation-based types, G/PN-Counter, OR-Set, and sequence CRDT variants, comparison with consensus and OT, and application strategy for real-time collaboration and multi-region.
- Computing & Embedded
Priority Inversion
A phenomenon where a high-priority task runs late because a low-priority task holds a resource and a medium-priority task preempts it. Resolved by priority inheritance and priority ceiling.
- Computing & Embedded
Embedded Software Testing
Closed-loop verification covering hardware, real-time behavior, resource constraints, and safety. The MIL to SIL to PIL to HIL stages, with MC/DC coverage per ISO 26262 and DO-178C.
- Computing & Embedded
Big-Endian and Little-Endian
The byte order for storing multibyte data. Big (MSB first, the network standard) vs. little (LSB first, x86), and conversion in heterogeneous communication.
- Computing & Embedded
Thrashing
Excessive multiprogramming causes page faults to surge so the CPU does little but swap, and performance collapses. Working set and PFF.
- Computing & Embedded
Deadlock
This essay covers the definition of deadlock and its distinction from starvation and livelock, the four necessary conditions (mutual exclusion, hold and wait, no preemption, and circular wait), detection via resource-allocation graphs, the trade-offs among prevention, avoidance (banker's algorithm), detection, and recovery techniques, practical cases in databases, multithreading, and distributed systems along with the dining-philosophers problem, and professional-engineer considerations such as lock ordering, timeouts, retries, and observability.
- Computing & Embedded
Tree Sort
An algorithm that sorts by inserting into a binary search tree and then performing an in-order traversal. Covers its principle and complexity (average O(n log n), O(n²) when skewed), avoiding the worst case with balanced trees such as AVL and red-black, and applications to dynamic data.
- Computing & Embedded
Memory Interleaving
A technique that divides memory into multiple banks and channels and distributes consecutive addresses across them to raise bandwidth through parallel, overlapped access. Covers low-/high-order interleaving, bank conflicts, the relationship with cache, and extension to HBM and NUMA.
- Computing & Embedded
Race Condition
A non-deterministic error in which the result varies with execution order due to unprotected concurrent access to a shared resource. Covers critical sections and mutual exclusion (mutex, semaphore, CAS), and control of deadlock and TOCTOU.
- Computing & Embedded
Bloom Filter
A probabilistic data structure that determines set membership using only an m-bit array and k hash functions; 'not present' is 100% accurate while only 'present' allows false positives, cheaply filtering large-scale membership queries with minimal memory—covering its operating principle, the false-positive-probability sizing formula (m/n·ln2), use cases such as LSM databases and safe browsing, and trade-offs against counting and cuckoo filters.
- Computing & Embedded
WebAssembly (Wasm)
A portable binary instruction format that compiles from many languages to run safely at near-native speed in browsers, servers, and at the edge—a lightweight isolated execution layer based on a stack VM, linear memory, and capability-based isolation, extended by WASI and the component model.
- Computing & Embedded
Consistent Hashing
A distribution technique that places keys and nodes on a single hash ring and assigns each key to the first node clockwise, minimizing remapping to an average of K/N when nodes are added or removed—using virtual nodes to ensure load balance and weighting, and serving as the standard routing foundation for distributed stores, caches, and load balancers.
- Computing & Embedded
Distributed Consensus Algorithms — Paxos and Raft
A technique by which multiple nodes agree on the same command order through majority quorum and log replication under partial failures—covering the principles of Paxos and Raft, leader election, safety, and practical adoption in systems such as etcd.
- Computing & Embedded
Algorithm Complexity and Big-O Notation
The concepts and types of time and space complexity and Big-O notation (O(1) to O(n!)), and how the growth rate of computation time differs by input size.
- Computing & Embedded
File System Structure and Journaling
The layered structure of a file system that organizes a storage device's blocks into files and directories (VFS, superblock, inode, extent), and the principle and modes of journaling (WAL) that guarantees multi-block updates atomically. Covers alternatives such as Soft Updates, Copy-on-Write and log-structuring, a comparison of ext4/XFS/ZFS/F2FS, and latest trends including flash optimization and distributed file systems.