Writing highly concurrent data structures is complicated

Writing highly concurrent data structures is complicated

• Writing highly concurrent data structures is complicated

• Modern programming languages provide efficient concurrent collections with atomic operations

Testing Atomicity of Composed Concurrent Operation – OOPSLA’12

• Testing Atomicity of Composed Concurrent Operation – OOPSLA’12

• Use library influence specification for POR

• Many violations we found in real applications

• Many were already fixed

Verifying the atomicity of composed operations

• Verifying the atomicity of composed operations

What do we want to check?

• What do we want to check?

• Specifying software correctness

• Scalability of static checking

• Large programs

• Many sources of unboundedness

• Inputs
• # threads
• # operations

What do we want to check?

• What do we want to check?

• Specifying software correctness

• Scalability of static checking

• Large programs

• Many sources of unboundedness

• Inputs
• # threads
• # operations

Check that composed operations are Linearizable [Herlihy & Wing, TOPLAS’90]

• Check that composed operations are Linearizable [Herlihy & Wing, TOPLAS’90]

• Returns the same result as some sequential run

What do we want to check?

• What do we want to check?

• Specifying software correctness

• Scalability of static checking

• Large programs

• Many sources of unboundedness

• Inputs
• # threads
• # operations

What do we want to check?

• What do we want to check?

• Specifying software correctness

• Scalability of static checking

• Large programs

• Many sources of unboundedness

• Inputs
• # threads
• # operations

Wolper’s definition is too restrictive for real life CCC

• Wolper’s definition is too restrictive for real life CCC

• We defined a data independence of linearizability for CCC

• A CCC is linearizable for a single input iff it is linearizable for every input

Data Independence detection is in general undecidable

• Data Independence detection is in general undecidable

• Syntactic rules that imply a program as data-independent

Small model reduction

• Small model reduction

• Decidable when the local state is bounded

• Explore all possible executions using:

• One input key and finite number of values
• Influenced based environment uses single value

• Employ SPIN

Writing concurrent data structures is hard

• Writing concurrent data structures is hard

• Employing atomic library operations is error prone

• Modular linearizability checking

• Leverage influence

• Leverage data independence

• Prove the linearizability of several composed operations

• Simple and efficient technique