Linearizability

• Consistencyのレベルの一つ

• あるオブジェクトに対する並行操作は、何らかの逐次的な順序(Real-time Order)で実行されたものとみなせる + 操作の開始から完了までの何処かの一瞬で実行されたとみなせる

  • その瞬間のことを、Linearization pointという
    • Lockベースの実装の場合、クリティカルセクションがLinearization point
    • Lockを使わない実装の場合、メソッド呼び出しの結果が他から見えるようになる時点がLinearization point

• 同期実行であり、同一スレッド内での操作順の反転も発生しないという保証

• Quiescent Consistency, Sequential Consistencyの両方を満たしている

• 操作に全順序関係がある

  • SMR, Total Order BroadcastはLinearizableだと思われ? (kekeho)

• Composabilityを満たす

• Real-time Orderを満たす

• 単一のオブジェクトについて、Sequential ConsistencyとLinearizabilityは外部から見分けることができない

  • こうした理由から、External Consistencyと呼ばれることも

参考

• https://muratbuffalo.blogspot.com/2024/08/linearizability-correctness-condition.html
• nikezono/Linearizability
• http://www.bailis.org/blog/linearizability-versus-serializability/
• Linearizability a correctness condition for concurrent objects