Data Structures in the Multicore Age

People

Concurrent Data Structures have a trade-off between correctness and performance.
Concurrent World Correctness - Safety, Nothing Bad Happens. Liveness, Something Good will Eventually Happen.
Consistency Conditions - Serializability, Linearizability, Sequential consistency, and Quiescent Consistency.
Contention Manager - Stalled threads keep the same resource while the winning thread holds it. Thus increasing traffic. A Contention Manager reduces that.
Different Threads require a shared resource. This moves away from a Turing Machine.
Future software engineers will need to learn how to program using these novel structures, understanding their performance benefits and their fairness limitations. - author's comment
Progress Conditions - Deadlockfreedom, Starvation-freedom, Lockfreedom, and Wait-Freedom.
Stalls - Threads access a shared resource one at a time.
The data structures of our childhood—stacks, queues, and heaps—will soon disappear, replaced by looser “unordered” concurrent constructs based on distribution and randomization. - author's comment
Threads need exclusive access to a resource. How do we get around this? Read-Only objects are trivial. Read-Write objects get exciting.
Threads-and-Objects Model - parallel programming model where threads communicate using shared objects.
We are experiencing a fundamental shift in the properties required of concurrent data structures and of the algorithms at the core of their implementation. - author's comment

Amdahl's Law[1] Describes the theoretical speedup for a fixed system after a given bottle-neck is cleared. Consequence - the bottle-neck always moves.

Parent Article: Reading Notes