⭐ Sequential Consistency

1. Definition

Sequential consistency (SC) is a memory consistency model that defines the order in which memory operations (reads and writes) appear to execute across multiple processors.

A system is sequentially consistent if the result of execution is the same as if all operations of all processors were executed in some sequential order, and the operations of each individual processor appear in program order.

2. Key Points

1. Global Ordering: All processors agree on the order of memory operations.
2. Program Order Preservation: Each processor’s own instructions execute in the order specified by its program.
3. Simplifies reasoning about concurrent programs, since the memory appears linearizable.

3. Formal Definition (Lamport, 1979)

A multiprocessor system is sequentially consistent if:

1. The results of execution are the same as if all memory operations were executed in some sequential order.
2. Each processor’s operations appear in the sequence in the order specified by its program.

4. Example

Consider two processors P1 and P2, sharing variables X and Y initially 0:

Sequentially consistent outcomes:

• r1 = 0, r2 = 1
• r1 = 1, r2 = 0
• r1 = 1, r2 = 1

Not allowed under SC:

• r1 = 0, r2 = 0 → violates sequential consistency because there is no sequential ordering where both reads return 0 after writes.

5. Importance

1. Predictable behavior: Makes it easier to reason about concurrent programs.
2. Foundation for multiprocessor memory systems: Ensures correctness in shared memory architectures.
3. Simplifies programming model: Programmers can assume a “single, global” order of memory operations.

6. Limitations

1. Performance Overhead: Enforcing sequential consistency may require stalls, memory fences, or strict ordering, which reduces performance.
2. Not required by modern processors: Many modern multiprocessors use relaxed consistency models (e.g., TSO, weak consistency) for higher performance.
3. Harder to implement in out-of-order execution or multithreaded caches without special mechanisms.

7. Relation to Other Concepts

8. Exam-Friendly Summary

• Sequential Consistency: Memory operations appear as if executed in some global sequential order, while preserving program order per processor.
• Benefits: Predictable, simple reasoning for shared memory programs.
• Limitations: Performance overhead; relaxed models are often used in practice.