線形化可能性
並行プログラミングにおいて操作(または操作の集合)は、呼び出しイベントと応答イベント(コールバック)の順序付きリストで構成されており、応答イベントを追加することで以下のように拡張できる場合、線形化可能である。
拡張されたリストは逐次履歴として再表現することができる(直列化可能である)。
その逐次履歴は元の拡張されていないリストの部分集合である。
これは、非公式には、変更されていないイベントのリストは、その呼び出しが直列化可能であるが、直列スケジュールの応答の一部がまだ戻ってきていない場合に限り、線形化可能であることを意味する。
並行システムではプロセスが同時に共有オブジェクトにアクセスできる。複数のプロセスが1つのオブジェクトにアクセスしているため、あるプロセスがオブジェクトにアクセスしている間に、別のプロセスがオブジェクトの内容を変更するという事態が発生することがある。
この例では線形化可能性の必要性を示している。線形化可能なシステムでは、共有されたオブジェクトに対する操作が重なっても、それぞれの操作は瞬時に行われているように見える。線形化可能性は強力な正当性条件であり、複数のプロセスが同時にオブジェクトにアクセスした場合に、どのような出力が可能であるかを制約する。線形化可能性は、操作が予期せぬ方法で完了しないことを保証する安全特性でもある。システムが線形化可能であれば、プログラマーはシステムについて推論することができる。