Concurrency & Parallel Computation

← Back to Domain-Specific Families

Abstractions about coordinating simultaneous or interacting computations — synchronization primitives (semaphores, locks, thread pools), classic concurrency problems (dining philosophers, sleeping barber, fork bombs), distributed protocols (two-phase commit, terminating reliable broadcast), and models for analyzing parallel algorithms and scheduling.

34 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Analysis of parallel algorithms — The resource analysis of algorithms with cooperating concurrent operations, tracking total work, critical-path span, processor count, time, space, communication, synchronization, and scalability under a declared machine model.
• C-element — An asynchronous state-holding logic element whose output changes only when all inputs agree and otherwise retains its prior state.
• Communicating sequential processes — A process algebra for specifying and reasoning about concurrent systems as sequential processes that synchronize through named communication events or channels.
• Data dependency — A relation in which one program operation reads or writes a location whose value or ordering is affected by another operation, constraining safe reordering and parallel execution.
• Dining philosophers problem — A concurrency problem modeling processes that alternately need pairs of shared resources, exposing deadlock, starvation and fairness constraints.
• Event structure — A concurrency model representing events with causal enabling, conflict, and consistency relations that determine possible executions.
• Fork bomb — A denial-of-service failure pattern in which a process recursively creates new processes until process-table, memory or scheduling resources are exhausted.
• Happened-before — The least strict partial order on distributed events generated by local program order, message send-before-receive, and transitivity, capturing potential causality without assuming synchronized physical clocks.
• Instruction-level parallelism — The degree to which independent machine instructions from one execution stream can overlap or execute simultaneously.
• Inter-process communication — Operating-system and network mechanisms that let separate processes exchange data, synchronize actions or invoke services while preserving process isolation.
• Join-pattern — A concurrency construct that atomically fires a reaction when a declared combination of asynchronous messages is simultaneously available on several channels.
• Live distributed object — A running distributed protocol instance presented as one identity-bearing object with encapsulated state, participants and externally observable behavior.
• Load-link/store-conditional — An atomic instruction pair that reads a memory location and commits a later store only if the implementation has observed no conflicting update since the linked load.
• Locks with ordered sharing — A family of transaction-concurrency protocols that soften lock conflicts by admitting ordered sharing while preserving a serialization order.
• Makespan — The elapsed time from the start of the earliest scheduled operation to completion of the latest operation or job.
• Memory refresh — Periodically sense and restore charge in every dynamic-memory row before leakage crosses the retention margin, preserving stored bits at a recurring availability and energy cost.
• Micro-thread (multi-core) — A software-managed fine-grained threading scheme that overlaps computation with memory or I/O latency on multicore processors.
• Multiple buffering — A producer-consumer technique using two or more buffers so rendering, transfer or processing can proceed concurrently with display or consumption of previously completed data.
• Parallel algorithm — An algorithm organized so multiple operations can execute concurrently on several processing elements while coordinating dependencies and shared data.
• Parallel computing — Execute multiple computations simultaneously across processing elements by decomposing work and coordinating data, communication, synchronization, dependencies, and load to reduce time or increase throughput.
• Parallel RAM — A shared-memory abstract machine for analyzing parallel algorithms by processor count, time and concurrent memory-access rules.
• Polling system — A queueing system in which one server visits multiple queues according to a routing rule and applies a declared service discipline at each visit.
• Real-time computing — Computing whose correctness depends on producing results within specified timing constraints as well as computing the right values.
• Resource leak — Fail to release an acquired finite computing resource after its logical lifetime, causing retained ownership, exhaustion, or degraded availability across repeated execution.
• Semaphore (programming) — A concurrency synchronization object maintaining a nonnegative permit count with atomic wait and signal operations that block or release execution according to resource availability.
• Shared memory — A memory region or address-space resource that multiple execution agents can access for communication or coordinated computation.
• Single-machine scheduling — The optimization of job order and timing on one capacity-one resource under declared release, precedence and objective rules.
• Sleeping barber problem — A classic synchronization problem modeling one service worker, a bounded waiting room and arriving clients to illustrate mutual exclusion, blocking and coordination without lost wakeups.
• Temporal Process Language — A timed process calculus extending CCS with multiparty synchronization on an abstract global clock signal.
• Terminating Reliable Broadcast — A fault-tolerant distributed-broadcast specification requiring all correct processes eventually to decide the same delivered value or a distinguished sender-failure value despite crash failures.
• Thread pool — A concurrency pattern that reuses a bounded set of worker threads to execute tasks drawn from a queue instead of creating a new thread for every task.
• Thread-local storage — A storage mechanism giving each execution thread its own instance of a variable that otherwise has static or global lifetime and access syntax.
• Two-phase commit protocol — A distributed atomic-commit protocol in which a coordinator first collects durable prepare votes and then tells every participant to commit or abort the transaction.
• Unbounded nondeterminism — A concurrency-model behavior in which a computation may make an unboundedly delayed or infinitely branching choice while fairness can still require eventual progress.