参考
Charles E Leiserson. A simple deterministic algorithm for guaranteeing the forward progress of transactions. Information Systems, Vol. 57, pp. 69–74, 2016.
私はほぼアルゴリズムしか見ていません． 読んだことのある人は回れ右で良いと思います．
なぜ進行保証が嬉しいか？（0分）
一般的に高コストとして知られるデッドロック検知・解決が不要となる． ちなみに，本記事の内容は lock 技術における reader-writer fairness とは異なることに注意されたい．
進行保証のやり方（1分）
SAFE-ACCESS(x, L) : x というレコードに安全にアクセスしたいっす．今持ってるロックは L です．
1 : h(x) が取るべきロックで，既に持ってるかどうか？
2 : 持ってる
3 : 持っていない時
4 : これから取ろうとしているロックよりも全順序オーダーで大きいものを M とする．以後，バイオレーションと呼ぶ．
5 : L は自分が所持（するであろう）ロックの集合
6, 7 : バイオレーション 0 ならば，しっかりとロック待ちしてロックを取る．
8, 9 : バイオレーションが存在するなら， try lock で取れたらラッキー．
10 : バイオレーションが存在するし， try lock もダメだった時
11 : バイオレーション分トランザクション実行を巻き戻す．
12, 13 : バイオレーションを解放
14 : 取りたかったもののロックをしっかりロック待ちしてとる．
15, 16 : 解放したバイオレーションのロックを再回収．
17 : 再回収した分やり直す．
18 : やっと safe access to x.
なんで全順序でロック取ると嬉しいの？（1分）
デッドロックフリーとなることが基本的な理由．
Example
lock(a, ?) は説明の簡単のため排他ロックとする． a はユーザー名とし， ? はレコードアイテムとする． User a : lock(a, x), lock(a, y), … User b : lock(b, y), lock(b, x), … という実行スケジュールを仮定する．
実時間順序で直列化したスケジュールが lock(a, x) -> lock(b, y) -> lock(a, y) -> lock(b, x) このようになる時， x を獲得したユーザー a と y を獲得したユーザー b がお互いにロック解放待ちをしあうことになる． 通称デッドロックである． これの検知・解決には一般的に大きなコストがかかることが知られている． しかし，ロックの獲得順序がとある全順序 (ex, アルファベット順) に従うと仮定した時，上記スケジュールは lock(a, x) -> lock(b, x) -> lock(a, y) -> lock(b, y) となり，先にユーザー a が走り抜けた後に b が処理を進めることができる．