Questions: Sequential Consistency

Question 1

Process A writes X=1 at time 3:00 PM. Process B begins reading X at 3:01 PM (after A's write completed) and reads X=0 (the initial value). Is this execution sequentially consistent?

• A. Yes — a total order exists where B's read is placed before A's write, and neither process's program order is violated
• B. No — B started after A finished, so B must see A's write under any reasonable consistency model
• C. No — sequential consistency requires all reads to return the most recently written value globally
• D. Yes — but only if A and B are on the same machine sharing memory

Answer: (A)

Sequential consistency does not respect real-time ordering between processes. It only requires that some valid total order of all operations exists such that each process's own operations appear in the same order they were issued. Here, a total order of [B reads X=0, A writes X=1] is valid: it preserves B's program order (trivially, one operation) and A's program order (trivially, one operation), and B reads X=0 which is consistent with X=0 being the value when B's read appears in the total order. Linearizability would reject this because A's write completed before B's read began in real time.

Question 2

How does sequential consistency differ from linearizability?

• A. Sequential consistency is stronger — it requires all processes to agree on a single global ordering of all operations
• B. Linearizability additionally requires the total order to respect real-time (wall-clock) ordering: if one operation completes before another begins, it must appear first
• C. Sequential consistency requires operations to be atomic; linearizability allows operations to take time
• D. Linearizability is weaker — it does not require each individual process's operations to appear in program order

Answer: (B)

Sequential consistency only requires a total order that is consistent with each process's program order — the order operations appeared from each process's perspective. Linearizability adds a stricter constraint: the total order must also be consistent with real-time. If operation A completed before operation B began (in wall-clock time), then A must appear before B in the total order. This additional constraint makes linearizability stronger and more expensive to implement but provides the intuitive guarantee that completed operations are visible to later operations.

Question 3

Under sequential consistency, if process A's write completes before process B's read begins (measured in real time), process B is expected to see the value written by A.

• T. True
• F. False

Answer: False

This guarantee is provided by linearizability, not sequential consistency. Sequential consistency only requires that a valid total ordering of all operations exists — one that preserves each process's program order. That total order can place B's read before A's write even if A's write completed first in real time. This is precisely the relaxation that makes sequential consistency weaker than linearizability and easier to implement: distributed systems can buffer, batch, and reorder operations across nodes without violating sequential consistency, as long as each individual node's operations stay in order.

Question 4

Sequential consistency guarantees that operations from a single process always appear in the global total ordering in the same sequence they were issued by that process.

• T. True
• F. False

Answer: True

This is the defining constraint of sequential consistency: per-process program order is preserved in the global total order. You cannot construct a sequentially consistent execution where a process's second operation appears before its first. What sequential consistency does NOT preserve is the relative ordering of operations from different processes — the system is free to interleave their operations in any order, as long as each process's own subsequence stays intact. This is both the key guarantee and the key limitation.

Question 5

Explain why sequential consistency is weaker than linearizability, and why this relaxation makes it easier to implement efficiently in distributed systems.

Model answer: Linearizability requires the total order of operations to respect real-time: if one operation's effect is visible (it 'completed') before another begins, the first must appear earlier in the total order. Sequential consistency drops this requirement — the total order only needs to preserve each process's own program order, with no constraints on cross-process real-time ordering. In a distributed system, enforcing real-time ordering requires tight coordination: nodes must communicate to agree on whether one operation 'completed' before another 'began,' typically requiring synchronization protocols with communication overhead proportional to latency. Sequential consistency allows nodes to operate independently, batching and reordering across nodes freely, as long as they report a consistent program-order-preserving sequence to each client — achievable with cheaper coordination mechanisms like causal ordering or vector clocks.

The real-time constraint in linearizability is what makes it expensive: to guarantee that a completed write is visible to subsequent reads from any process, the system must synchronize across all replicas before acknowledging the write. Sequential consistency allows writes to propagate asynchronously as long as the ordering seen by each individual client is consistent with program order. For many applications (feeds, timelines, document viewing) this weaker guarantee is sufficient and comes at significantly lower latency cost.