Invariant

As explained in C++ Concurrency in Action, Second Edition

An invariant is a condition that remains true about a data structure or program state when it is in a valid state.

An invariant is a condition that remains true about a data structure in a valid state. Updates may temporarily break it; shared access becomes risky if another thread can observe that intermediate state. section 3.1

Removing a node from a doubly linked list

If node A points next to B, B should point back to A. Removing a node requires changing both neighboring links. Between those updates, the forward and backward links disagree, so a concurrent reader may observe a broken invariant. section 3.1

Figure 3.1. Deleting a node from a doubly linked list

The diagram shows how deleting a node temporarily leaves the links inconsistent. section 3.1

Ways to prevent other threads from observing broken invariants include:

• Protect the data structure so other threads cannot see intermediate updates. section 3.1.2
• Redesign updates as indivisible changes that each preserve the invariants; this is difficult and involves memory-model nuances. section 3.1.2
• Use transactional updates that commit together and restart if another thread has changed the data. section 3.1.2

How C++ Concurrency in Action, Second Edition covers it

How deep it goes

Works through a doubly linked-list deletion and explains how separate updates temporarily break its invariant.

Examples

Uses doubly linked-list deletion and queue insertion to illustrate broken and preserved invariants.

What you can do after

Evaluate whether concurrent updates can expose a data structure while its invariants are broken.

How it connects

Connects invariants to race conditions, mutexes, lock-free programming, and software transactional memory.

liveBookmanning.com

Read C++ Concurrency in Action, Second Edition on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  100 C++ Mistakes and How to Avoid ThemA class invariant is a condition on an object's state that must hold whenever the object is usable, including after construction and public operations.
• 

  liveBookmanning.com
  Fabulous Adventures in Data Structures and AlgorithmsAn invariant is a property that remains true throughout the valid states or operations of a computation.
• 

  liveBookmanning.com
  Unit Testing Principles, Practices, and PatternsAn invariant is a condition that must remain true for a software object or component.
• 

  liveBookmanning.com
  Learn Haskell by ExampleAn invariant is a property that must remain true for every valid state of a data structure or computation.
• 

  liveBookmanning.com
  F# in Action: A Revised Edition of Get Programming with F#An invariant is a condition that must remain true for a value or domain entity to be considered valid.
• 

  liveBookmanning.com
  Software Design for Python ProgrammersThe Class Invariant Principle states that a condition governing a class's valid objects must remain true during runtime.
• 

  liveBookmanning.com
  Object-Oriented Software Design in C++A design principle stating that a class condition must remain true throughout the runtime of its objects.
• 

  liveBookmanning.com
  Functional Design and Architecture: Examples in HaskellAn invariant is a condition or property that remains true for every valid state or execution covered by its specification.
• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresAn invariant is an internal property of a data structure or mathematical object that remains true throughout a process or across permitted transformations.
• 

  liveBookmanning.com
  The Art of CodeAn invariant is a condition that must remain true for a value or data structure to be valid.
• 

  liveBookmanning.com
  Machine Learning System DesignThe property of remaining unchanged under specified transformations or perturbations.

Compare how 12 books explain invariant →

Related concepts

• property-based testingused by · Property-based testing is a software-testing technique that generates varied inputs and checks whether specified general properties of the software’s behavior hold across them.
• illegal stateaddresses · An illegal state is a program or system state that violates constraints required by its data model, domain rules, or specification.
• contractpart of · An API contract is a specification of the operations, data, and behavioral expectations that govern interactions between software components.
• initializerused by · An initializer is a function, declaration, or language construct that establishes the initial value or state of an object, value, computation, or process.
• accessor methodused by · An accessor method or function provides access to an object's property or state by retrieving its value, assigning a value, or defining behavior for such access.
• factoryused by · A factory is a function, method, class, or component that creates and returns objects or other values while encapsulating construction details or selection.

This explainer was generated by Manning's knowledge graph from the text of C++ Concurrency in Action, Second Edition. The section links point to the parts of the book it draws on.