Eşzamanlı programlamada wait-free algoritma progress guarantee hiyerarşisi, bir algoritmanın diğer thread'lerin davranışından bağımsız olarak kaç adımda tamamlanacağını garanti etmesi üzerine kurulur. Bu hiyerarşiyi anlamak, doğru eşzamanlılık soyutlamasını seçmek için gereklidir. Progress garantileri en güçlüden en zayıfa sıralanır: **Wait-Free:** Her thread, diğer thread'lerin hızından bağımsız olarak sonlu adımda tamamlar. Bu en güçlü garantidir. Bir thread yavaş çalışsa, dursa veya askıya alınsa bile diğer thread'ler etkilenmez. Wait-free algoritma gerçek anlamda starvation-free'dir. **Lock-Free:** Sistem genelinde (globally) ilerleme garantilidir; bir thread sonlu adımda tamamlar, ancak hangi thread olduğu belirtilmez. Tek bir thread teorik olarak sonsuz tekrar etmeye zorlanabilir (livelock riski), ancak toplam sistemde ilerleme duraksız sürer. **Obstruction-Free:** Bir thread izolasyonda çalıştığında sonlu adımda tamamlar. Çekişme durumunda garanti yoktur. **Blocking (Mutex):** Thread'ler birbirini bloke edebilir; priority inversion ve deadlock riskleri mevcuttur. Wait-free algoritma uygulamaları pratikte nadir görülür çünkü tasarımı son derece güçtür. En bilinen örnek, Fetch-And-Add (FAA) ile uygulanan kuyruk yapılarıdır. Dmitry Vyukov'un wait-free queue implementasyonu, her producer ve consumer için ayrı bir slot dizisi kullanır; her slot için FAA ile benzersiz index edinilir ve bu index'e yazma doğrudan gerçekleşir. Wait-free garantisi için "helping" mekanizması sıkça kullanılır: eğer bir thread yavaşlarsa, diğer thread'ler yavaş thread'in bekleyen operasyonunu tamamlar. Bu yardım protokolü algoritma karmaşıklığını önemli ölçüde artırır. Praktik tradeoff'lar: - Wait-free algoritma genellikle lock-free alternatiften daha fazla bellek ve hesaplama maliyeti taşır. - Gerçek zamanlı sistemlerde (hard real-time) wait-free garantisi mutex'ten üstündür çünkü priority inversion riski yoktur. - Kullanıcı alanı uygulamalarında lock-free genellikle yeterlidir; wait-free yalnızca sıkı latency SLA'sı olan bağlamlarda değer sağlar. - JVM tabanlı dillerde GC duraklatmaları zaten wait-free garantisini pratikte anlamsızlaştırabilir. Hiyerarşinin pratik anlamı: bir mutex-based yapıdan lock-free yapıya geçiş, çoğu workload'da ölçülebilir kazanım sağlar. Lock-free'den wait-free'ye geçiş ise çok daha küçük ve özelleşmiş bir kazanım seti sunar; test, doğrulama ve bakım maliyeti buna göre değerlendirilmelidir. Formal doğrulama araçları, TLA+, SPIN model checker, wait-free algoritma progress guarantee analizinde kullanılır. Özellikle TLA+ ile bir algoritmanın bütün thread senaryolarında belirli adım sayısında tamamladığını kanıtlamak mümkündür.