Linearizability and Sequential Consistency Fundamentals Quiz Quiz

Explore core concepts of linearizability and sequential consistency in distributed systems with this beginner-friendly quiz. Sharpen your understanding of consistency models, identify key differences, and apply these principles to sample scenarios involving shared objects and concurrent operations.

1. Defining Linearizability

   Which property defines linearizability in the context of shared objects in distributed systems?

   1. Operations only need to be visible to the process that invoked them.
   2. No two operations can ever occur at the same time.
   3. All processes must execute operations in a fixed, pre-set order.
   4. Every operation appears to happen instantaneously at a single point between its invocation and response.

   Explanation: Linearizability requires that each operation appears to take effect instantly somewhere between its start and finish, creating a globally valid order. The second option is incorrect because linearizability does not force a fixed global order, just a valid one respecting real-time. The third is wrong since the effect must be visible to all, not just one process. The fourth confuses concurrency; linearizability allows concurrent operations as long as their order follows the rule.

2. Understanding Sequential Consistency

   What does sequential consistency guarantee in a multi-process system?

   1. The result is the same as if operations were executed in some sequential order, preserving each process’s program order.
   2. Each process has its own independent view of memory operations.
   3. All reads see the most recent write to a variable regardless of process order.
   4. Operations must happen instantly in real time.

   Explanation: Sequential consistency ensures that the overall effect is as if all operations were performed one at a time, in some order, while each process’s operations appear in that sequence in its original order. The second option actually describes a stronger property, like strict consistency. The third option contradicts the shared view required by sequential consistency. The fourth is an exact property of linearizability, not sequential consistency.

3. Real-Time Order Importance

   In which model must the real-time ordering of operations always be preserved?

   1. Parallel consistency
   2. Linearizability
   3. Sequential consistency
   4. Eventual consistency

   Explanation: Linearizability always preserves real-time ordering, ensuring that if one operation completes before another begins, their order is reflected. Sequential consistency does not guarantee this real-time linkage. Eventual consistency is much weaker and does not enforce ordering strictly. Parallel consistency is not a recognized consistency model.

4. Sample Scenario: Consistency Check

   If Process X writes 'A' then Process Y reads 'A', and both operations do not overlap in time, which consistency model guarantees that Y must see 'A'?

   1. Sequential consistency
   2. Linearizability
   3. Weak consistency
   4. Minimal consistency

   Explanation: Linearizability ensures that if the write completes before the read begins, the read must reflect that write. Sequential consistency could allow the read to see a previous value because it does not require real-time constraints. Weak consistency and minimal consistency are less strict and do not offer this guarantee. Only linearizability directly preserves this behavior.

5. Permissible Interleavings Example

   Which statement best describes a scenario allowed under sequential consistency but not under linearizability?

   1. No two writes occur simultaneously on the same variable.
   2. Every process reads its own writes as soon as they are made.
   3. A read returns an outdated value because there is no real-time ordering enforced.
   4. Operations happen in exactly the order they were issued globally.

   Explanation: Sequential consistency may permit a read to see a stale value if a real-time order is not enforced, while linearizability disallows such outcomes. The second and third options are unrelated to the difference and are not required by either model. The fourth is incorrect, as neither model requires a single fixed global issue order, only a valid one.

6. Atomicity Illustration

   What does atomicity mean in the context of linearizability?

   1. Operations appear to happen all at once, without intermediate states.
   2. Only the fastest process’s operations are ever considered.
   3. Each process operates independently of others.
   4. Operations can be split into several smaller steps.

   Explanation: Atomicity refers to the property that operations are indivisible and appear to take effect instantaneously. The second option is incorrect because processes interact under atomicity. The third option is the opposite of atomicity, allowing splitting. The fourth option is unrelated to atomicity or consistency models.

7. Comparing Models Directly

   Which is the main difference between linearizability and sequential consistency?

   1. Both require operations to be ordered by process speed.
   2. Sequential consistency is always stricter than linearizability.
   3. Linearizability and sequential consistency are identical models.
   4. Linearizability respects real-time ordering; sequential consistency does not.

   Explanation: The principal difference is that linearizability enforces real-time operation order while sequential consistency does not. The second statement is incorrect since linearizability is actually stricter. The third describes neither model correctly. The fourth is false because they are distinct models with different requirements.

8. System Feedback Scenario

   If a read operation returns an outdated value even after a completed write, which consistency model could permit this?

   1. Sequential consistency
   2. Absolute consistency
   3. Linearizability
   4. Immediate consistency

   Explanation: Sequential consistency can, in some situations, allow a read to see an old value if real-time order is not maintained. Linearizability would not permit this as it enforces real-time order. The terms 'absolute consistency' and 'immediate consistency' are not standard or recognized models and thus do not apply here.

9. Practical Example with Multiple Processes

   Suppose three processes perform operations on a shared counter: increments and reads. Which model ensures that the result of each read operation reflects all completed increments that finished before the read started?

   1. Isolated consistency
   2. Sequential consistency
   3. Linearizability
   4. Probabilistic consistency

   Explanation: Linearizability ensures that any read reflects the effect of all previously completed operations, maintaining real-time guarantees. Sequential consistency might allow a read to miss some completed increments. Probabilistic consistency does not guarantee deterministic outcomes. 'Isolated consistency' is not a standard consistency model.

10. Effect on System Design

    Why might designers choose sequential consistency over linearizability in a distributed system?

    1. Linearizability is a much weaker model than sequential consistency.
    2. Sequential consistency guarantees all reads see the latest write without exception.
    3. Sequential consistency is generally easier and more efficient to implement.
    4. Linearizability allows outdated values to be read.

    Explanation: Sequential consistency is often simpler to achieve, as it does not enforce real-time order, making it more scalable and efficient in practice. The second statement is false because linearizability requires up-to-date reads within its constraints. The third is untrue since sequential consistency allows exceptions without real-time order. The fourth inverts the relationship; linearizability is stricter, not weaker.