Glossaria.net

Glossary Concurrency / Term

Internal nondeterminism vs external (observable) nondeterminism

[Nondeterministic vs deterministic] Computations can have internally nondeterministic paths of execution, but the nondeterminism can be abstracted away by the computational model and not observable externally. Nondeterministic interleaving of concurrent computations is a key source of complexity in concurrency modeling, and observable nondeterminism is generally an undesirable property in concurrency models since it can lead to irreproducible error states.

A common example of nondeterminism is a race condition, which refers to uncontrolled contention for a shared resource, such as simultaneously accessing and updating the same memory location in an unspecified order (data race). Unintentional race conditions can be a pernicious problem to debug since the states and timings that cause them can be hard or impossible to reliably reproduce (irreproducibility).

The conventional approach to concurrency modeling is using concurrency control primitives like locks, which means leaving it up to programmer discipline to avoid accidental observable nondeterminism. Locking can have coarse- or fine-grained synchronization granularity, where coarse-grained granularity trades concurrency for deterministic execution while fine-grained granularity is more concurrent but less predictable.

Declarative concurrency models reduce the need to make trade-offs between concurrency and correctness by imposing a data dependency-based ordering of execution or, in other words, trading expressive power of state (shared mutable state) for observable determinism. An example of a deterministic concurrency model is functional reactive programming (FRP) as defined by Conal Elliott, which imposes ordering constraints based on the concept of continuous time.

Permanent link Internal nondeterminism vs external (observable) nondeterminism - Creation date 2020-09-05


< Hybrid user and system threads Glossary / Concurrency Internal vs external >