線形化可能性
並行システムは、共有データ構造やオブジェクトを介して通信するプロセスの集合体である。並行システムでは、複数のプロセスが同時にオブジェクトにアクセスする可能性があり、プログラマーは期待される結果を推論できる必要があるため、線形化可能性が重要となる。並行システムの実行結果は、完了した操作の順序付けられたシーケンスである履歴となる。
履歴(history)は、一連のスレッドやプロセスがオブジェクトに対して行った呼び出しと応答のシーケンスと定義する。呼び出しは操作の開始であり、応答はその操作の終了を知らせるものと考えることができる。関数を呼び出すたびに、それに続く応答が発生する。これを利用して、オブジェクトのあらゆる用途をモデル化することができる。例えば、2つのスレッド、AとBが両方ともロックを取得しようとし、既に取得されている場合には手を引くとする。これは、両方のスレッドがロック操作を呼び出し、両方のスレッドが応答を受け取り、一方は成功し、一方は失敗したとモデル化される。
逐次履歴とは、すべての呼び出しが即座に応答するもので、つまり、呼び出しと応答が瞬時に行われると考えられる。逐次履歴は実際の並行性を持たないため、推論するのは簡単なはずだが、前の例は逐次履歴ではないため、推論するのは困難となる。ここで線形性が必要になる。
履歴 σ {\displaystyle \sigma } が線形化可能なのは、次のような完了した操作の線形順序がある場合である。
σ {\displaystyle \sigma } の中で完了したすべての操作について,その操作は,すべての操作が σ {\displaystyle \sigma } の順に1つずつ完了した場合に返すのと同じ結果を実行時に返す。