リニアライザブルとシリアライザブルの違いは何ですか？

質問

線形化可能性と直列化可能性の違いは何ですか（Javaの文脈で）？これらの違いを例で説明するか、良い参考文献を提供してください。

どのように解決するのですか？

両者の区別の中心は シリアライズ性 は グローバル プロパティであり、操作/取引の履歴全体のプロパティです。 リニアライズ可能性 は ローカルな性質 であり、単一の操作/トランザクションの特性である。 もう一つの違いは、線形化可能性には、次のような概念があることです。 リアルタイム 操作の線形化ポイントはその呼び出しと応答時間の間になければならない。 (操作の線形化ポイントはその呼び出しと応答時間の間になければならない（Tim Harris参照。 トランザクショナルメモリ、2版 . の Herlihy のスライドを参照してください。 The Art of Multiprocessor Programming, the section on Linearizability (マルチプロセッサ・プログラミングの技術) のスライドをご覧ください。 ここから入手可能 で、いくつかの例と証明を見ることができます。

両方の特性は、同じ目標である逐次一貫性を目指しています。 Herlihyの論文より。

データベースや分散システムに関する多くの研究は、並列計算の基本的な正しさの条件として直列化可能性を使用しています。このモデルでは、トランザクションは、他のトランザクションと共有されるオブジェクトのセットに対して、有限の一連のプリミティブ操作を適用する制御のスレッドとなります。履歴は、トランザクションが順次実行されているように見える、つまりインターリーブなしで実行されるものと等価であれば、直列化可能である。(部分的な)優先順位は、明白な方法でトランザクションの重ならない組に定義することができる。履歴が厳密に直列化可能なのは、直列化された履歴におけるトランザクションの順序が、その優先順位と互換性がある場合です...

...線形化可能性はトランザクションが単一のオブジェクトに適用される単一の操作で構成されるように制限されている厳密な直列化可能性の特別なケースとして見ることができます。それにもかかわらず、この単一操作の制限は、線形化可能な計算にその直列化可能な対応物とは異なる味を与え、実用的かつ形式的な結果を広範囲に渡って持っています。直接的な実用上の結果として、シリアライザブルに適した同時実行制御メカニズムは、不必要なオーバーヘッドを導入し、同時実行に不必要な制限を加えるため、一般的にリニアライザブルには適していません。

参考文献

• Harris, Tim, James Larus, and Ravi Rajwar: トランザクショナル・メモリ, 2ed . Synthesis Lectures on Computer Architecture. Morgn &; Claypool, 2010. ISBN 9781608452354。 URL: http://www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011?journalCode=cac

• ハーリー、モーリス、ジャネット・ウイング 線形化可能性。並行オブジェクトの正しさの条件 . ACM Trans. Prog. Lang. and Sys. Vol.12, No.3, 1990年7月, 463-492ページ. URL http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

• パパディミトリオ、クリストス データベース並行更新のシリアライズ可能性 . ACM誌 Vol 26. No 4. 1979年10月、631-653頁。URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf

• ハーリー、モーリス、ニル・シャヴィット マルチプロセッサ・プログラミングの技法 . Elsevier, 2008. ISBN 978-0-12-370591-4. URLはこちら。 http://www.elsevier.com/wps/find/bookdescription.cws_home/714091/description#description 線形化可能性に関するPPTスライドはこちら。 http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx

• アティヤ、ハギット、ジェニファー・ウェルチ シーケンシャルな一貫性とリニアライザブルの比較 . ACM Transactions on Computer Systems Vol.12, No.2, May 1994, Pages 91-122. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf

詳細。

もし本当に気になるなら、定義を紹介した論文を読んでください。 線形化可能性について、それは 線形化可能性。同時実行オブジェクトの正しさの条件 Herlihy and Wing . 密度が濃いですが、注目する価値はあります。 ソフトウェア トランザクション メモリのコミュニティでは、線形化可能性が目指すべき正しい目標/特性であるかどうかは未解決の問題であることに注意してください。

直列化可能性 は、操作の集合（システム）の結果が、すべての操作の特定の順序（"実行が特定の順序で行われたかのように..."）として表現可能であることについてである。 線形化可能性は、システム内の操作の1つの部分集合の特性である...ある操作/操作の集合が、他の操作に対して、あたかも（論理）時間内の特定の瞬間に発生したように見える場合、線形化可能であるとする。 ここでいう標準的な論文とは Papadimitriouです。 The Serializability of Concurrent Database Updates (データベースの並行更新の直列化可能性) .

線形化可能("linearizable)について考えるとき、(quot;atomic operation")と考えてください。システムの他の部分に対して原子的に起こる(ように見える)と、操作(のセット)は線形化可能(")です。 一般的な定式化は "各操作がその呼び出しと応答の間で瞬時に効果を発揮するような錯覚を与える." です。 線形化可能性 によるものです。 Herlihy のような他の種類の順序一貫性プロパティがグローバルであるのに対して、これはローカルなプロパティであることを強調するものです。