Questions: Concurrency Verification

Question 1

Why is concurrent program verification fundamentally harder than sequential program verification?

• A. Concurrent programs use more memory
• B. The number of possible interleavings of thread actions is exponentially large, and correctness must hold under ALL possible schedules. A bug may only appear under a specific rare interleaving that is almost impossible to reproduce by testing. Sequential programs have a single execution order, making reasoning tractable
• C. Concurrent programs cannot be expressed in Hoare logic
• D. Concurrent programs always have bugs

Answer: (B)

With n threads each executing k steps, there are (nk)! / (k!)^n possible interleavings. Even small concurrent programs have astronomically many schedules. A data race might occur only when thread A reads between thread B's write and thread C's write — a specific 3-step interleaving among millions. Testing exercises a tiny fraction of interleavings; formal verification must cover all of them. This combinatorial explosion is the defining challenge of concurrency verification.

Question 2

In concurrent separation logic, the separating conjunction P * Q ensures thread safety because it guarantees that the heap regions owned by different threads are disjoint.

• T. True
• F. False

Answer: True

If thread 1 owns heap region described by P and thread 2 owns region described by Q, and the specification uses P * Q, then the regions are disjoint by the semantics of *. Neither thread can access the other's region, preventing data races. When threads need to communicate through shared state, they must explicitly transfer ownership through a shared resource invariant (e.g., a lock invariant that grants access to the shared region to whichever thread holds the lock). This disciplined ownership model is what makes compositional reasoning about concurrent programs possible.

Question 3

Explain the rely-guarantee approach to concurrency verification and how it enables compositional reasoning about threads.

Model answer: Each thread is specified with four conditions: a precondition (P), postcondition (Q), rely (R) — what the thread assumes other threads will do to shared state, and guarantee (G) — what this thread promises about its own modifications to shared state. A thread is correct if, assuming its environment adheres to R, the thread's execution from P establishes Q while adhering to G. Compositionality comes from checking that each thread's guarantee implies the other threads' rely conditions — the guarantees of one thread justify the assumptions of the others.

Rely-guarantee, introduced by Jones (1983), was the first compositional approach to concurrent verification. Without it, you must reason about all interleavings globally. With rely-guarantee, each thread is verified independently under assumptions about its environment, and a compatibility check ensures the assumptions are justified. This is analogous to assume-guarantee reasoning in model checking and to interface contracts in modular software design. The approach complements concurrent separation logic: separation logic handles spatial (heap) decomposition, while rely-guarantee handles temporal (interference) decomposition.