In concurrent separation logic with rely-guarantee reasoning, the 'rely' condition specifies what other threads can do to the shared state, while the 'guarantee' specifies what THIS thread will do. If the precondition is P, the rely is R, and the guarantee is G, what postcondition can we conclude from {P} C {Q}?
Think about your answer, then reveal below.
Model answer: If {P} C {Q} is verified with rely R and guarantee G, then after C executes, the postcondition is Q * R* where R* represents any modifications allowed by R from concurrent threads. Formally, we can conclude the thread's final state satisfies Q (the guarantee), but the global state satisfies Q * (arbitrary environment modifications respecting R). The key insight is that other threads might have modified shared regions, but they can only modify according to R, which the specification accounts for.
Rely-guarantee is how separation logic scales to concurrent programs. When verifying a thread, you assume the environment (other threads) will respect the rely condition R — they won't do anything worse. In return, you guarantee your thread respects G. This reduces the verification problem from 'prove correctness despite arbitrary interference' to 'prove correctness given well-behaved interference.' The framework requires verifying that each thread's guarantee matches some other thread's rely, creating a closed-world assumption. This is the foundation for modular verification of concurrent systems.
Question 2 Short Answer
Higher-order separation logic predicates allow specifications to abstract over heap structure. A predicate like `tree(x, P, Q)` might abstract over a tree rooted at x where nodes satisfy predicate P and edges satisfy predicate Q. Why is this important for recursive data structure verification?
Think about your answer, then reveal below.
Model answer: Recursive data structures (linked lists, trees, graphs) have unbounded heap footprints that depend on structure depth. A simple points-to assertion x -> v cannot express 'x is the root of a list of length n' or 'x is a balanced tree.' Higher-order predicates are defined inductively: `list(x, n)` says 'x points to a pair (head, tail) where tail is a list of length n-1' (base: empty list). This inductive definition captures the whole structure in one predicate, enabling modular verification: you reason about list-manipulating code by instantiating the `list` predicate once, rather than manually unrolling the structure's heap layout.
Without higher-order predicates, separation logic specs for recursive data structures become intractable. Consider reversing a linked list: you must show the reversal preserves the list invariant (cells form a single chain with no cycles). With the `list(x)` predicate, you write {list(x)} reverse(x) {list(x)}, hiding the detailed heap structure. The proof unfolds the `list` predicate inductively as needed. This is analogous to type abstractions in type theory: instead of reasoning about the representation, you reason about the interface (the predicate's meaning). The power of higher-order separation logic is that these predicates can quantify over other predicates, enabling very expressive specifications.
Question 3 Multiple Choice
Quantitative separation logic extends the framework to reason about resource consumption (time, memory, bandwidth). How does this differ from simple (qualitative) separation logic?
AQuantitative separation logic uses integers instead of predicates
BQuantitative separation logic adds numeric annotations to separation logic assertions, tracking how much of a resource (time, memory) a computation consumes. For example, {time(10)} C {time(0)} states C consumes at most 10 time units
CQuantitative separation logic is only used for functional programs
DQuantitative separation logic eliminates the need for temporal properties
Qualitative separation logic asserts *which* heap regions are accessed (local reasoning about memory safety). Quantitative separation logic adds *how much* — annotating assertions with resource bounds. A predicate `credits(n)` represents n units of computational credit; {list(x) * credits(10)} C {list(x) * credits(0)} says C traverses the list using at most 10 time units. This bridges formal verification and complexity analysis, proving not just correctness but also resource bounds. The separating conjunction distributes resources: if C1 consumes c1 credits and C2 consumes c2 credits, and C1 and C2 operate on disjoint heap regions, then C1 ; C2 consumes c1 + c2 credits.
Question 4 Short Answer
Deny-guarantee reasoning complements rely-guarantee by specifying what a thread REFUSES to do (the deny condition). Why is this useful?
Think about your answer, then reveal below.
Model answer: Rely-guarantee specifies lower bounds on interference (what OTHER threads CAN do). Deny-guarantee specifies upper bounds on interference (what OTHER threads CANNOT do). For example, if thread A needs x > 0, the deny condition is 'other threads cannot set x <= 0.' This enables stronger specs: {x > 0} with deny 'x <= 0' guarantees x > 0 throughout thread A's execution, not just initially. Deny-guarantee is particularly useful for real-time systems and security, where certain invariants must be maintained against all concurrent interference.
Rely-guarantee alone is passive: assume the environment is well-behaved. But sometimes you need to actively constrain the environment. Deny-guarantee is the complement: you specify which state changes you will NOT tolerate, and verification proves that concurrent threads respect this bound. This is essential for systems where one component's safety depends on other components NOT doing certain things — e.g., a kernel refusing to allow user-space threads to disable interrupts. The combination of rely and deny gives bidirectional control: you promise what you'll do (guarantee), ask what the environment will do (rely), and forbid what the environment cannot do (deny).