ライブネス
ライブネスにはいくつかの形態があります。以下のものは、ある相互排除(ミューテックス)装置で保護されたクリティカル・セクションを持つマルチプロセス・システムの観点から定義されています。すべてのプロセスがミューテックスを正しく使用していると仮定し、クリティカルセクションの実行が終了することを進捗と定義する。
デッドロックからの解放は、弱いながらもライブネスの一形態である。複数のプロセスと、相互排除装置で保護された1つのクリティカルセクションを持つシステムを考える。このようなシステムは、ある時点であるプロセス群がクリティカルセクションへのアクセスをめぐって競合しているときに、後の時点であるプロセスが最終的に前進する場合、デッドロックフリーであると言われます。そのプロセスは前述のグループに属する必要はなく、それ以前あるいはそれ以降にアクセスを得たかもしれない。
スタベーションからの自由(または「有限のバイパス」)は、デッドロックの自由よりも強力なライブ性保証です。これは、臨界領域へのアクセスを争うすべてのプロセスが、最終的に進歩することを意味する。スタベーションのないシステムは、デッドロックのないシステムでもある。
さらに強力なのが bounded bypass の要件である。これは、n個のプロセスが臨界領域へのアクセスを競っている場合、ある関数fについて他のプロセスから最大f(n)回バイパスされた後、各プロセスが進展することを意味している。