non-blockingの意味するところ

海外の文献を読み漁っていると気づくのですが
2003年を境にこの文脈で使われる言葉の定義が変わります。

↑2003年ごろまでの構図

↑現在の構図。*1
non-blocking = obstruction-free という理解でもおおよそ間違いではないとは思いますが
論文を読むに当たって
non-blocking = ロックを使わないアルゴリズム全般
obstruction-free = 非lock-freeだけどロックだけはしない
というニュアンスの違いを感じます。

以後、現在の構図の方を前提に話します。ご注意ください。
まずは3つの分類の違いから

wait-free

操作が「他のスレッドの動向に関わらず有限ステップで完了できる」場合、そのアルゴリズムはwait-freeと呼ばれます。starvation-freeと呼んだりもします。
実際には初めからここに分類されるアルゴリズムは多くありませんが、例えばスレッド数に制約をつけたりすることでこちらに分類される場合もあります。

一見パフォーマンスが高そうに見えますが、必ずしもそうとは限りません。
少ないコア数の場合にはロックによる排他よりもスループットが低い場合も有り得ます。

実際にこの保証のあるアルゴリズムの必要性がある場面は私の知る限りではリアルタイム動作を保証したい場合のみで
・ロボットの操作（関節の操作が遅れると転んじゃう！）
・音響ソフトウェア（音が遅れて聞こえちゃう！）
などです。
ですがLinuxなどの非リアルタイムOS上でどうしてもwait-freeじゃないと…という状況は思いつきません。*2

また誤解が多いのですが「一定ステップで終了する事」ではなく「ステップ数の上限が固定できること」が条件なので
例えば「さすがに20スレッドに追い越される前には動作を必ず完了できる」場合などにもwait-freeの名前が付きます。

lock-free

操作が「いつも必ずどれかのスレッドで有効に行われている」場合、そのアルゴリズムはlock-freeと呼ばれます。進行保証が付いているとも言います。
歴史的な経緯からか意味と名前がいまいちぴったり来なくて、個人的にはwaste-freeとか呼べばいいのにと思っているけれど他に気にしてる人は居ないようです。

wait-freeと比べてstarvationが発生する危険があります。具体的に言うといつまで経っても他のスレッドに邪魔されて動作を完了できないスレッドが発生し得ます。*3
しかし前述したようにそれは必ずしもパフォーマンスの低下を意味しておらず、強いて言えば「レイテンシ保証を犠牲にスループットを手に入れた」という形容が適切な場合もあります。

obstruction-free

操作が「他のスレッドに邪魔さえされなければ終わる」場合、そのアルゴリズムはobstruction-freeと呼ばれます。lock-freeと比べて進行保証が付いていない特徴があります。

進行保証が無いと、複数のスレッドが走っていても「どのスレッドも全体での進行に寄与しない」瞬間が存在してしまいます。
lockを用いて居ないのになぜこのような事態になるかというと、複数のスレッドがお互いを邪魔しないよう動作した結果です。
詳しくはSTMの実装などを読んでください*4