Taką sytuację nazywamy zakleszczeniem.
Wiele programów równoległych wymaga by ich podzadania były dodatkowo synchronizowane. Taką możliwość daje użycie bariery. Bariery są zwykle implementowane za pomocą blokad. Wyróżnia się klasa algorytmów, w których nie używa się ani blokad ani barier (ang. lock-free and wait-free algorithms). Jednak stosowanie tego podejścia napotyka spore trudności (za przedstawienie eleganckich dowodów, wykorzystujących elementy topologii algebraicznej, niemożliwości rozwiązania dość prostych problemów przyznano Nagrodę Gödla w 2004 roku).
Nie każda próba „zrównoleglenia” daje efekt w postaci przyspieszenia obliczeń. W ogólności, jeśli program jest dzielony na coraz więcej i więcej podzadań, to w pewnym momencie narzuty związane z komunikacją zaczynają przeważać nad zyskiem ze „zrównoleglenia” i pomimo zwiększania teoretycznej mocy obliczeniowej mamy do czynienia ze spowolnieniem obliczeń. Zjawisko to nazywane jest spowolnieniem równoległym (ang. parallel slowdown). Próbą górnego oszacowania możliwego przyspieszenia uzyskanego przez zrównoleglenie obliczeń dają prawa: Amdahla i Gustafsona.