Algorytmy probabilistyczne to pewna grupa algorytmów, które wykorzystują losowanie do uzyskania rozwiązania.
Są one często stosowane w systemach współbieżnych procesów ubiegających się o współdzielone zasoby systemu komputerowego.
W wielu przypadkach nie istnieje w pełni rozproszone (tzn. bez centralnej pamięci i centralnego procesora) i symetryczne (identyczność protokołu) rozwiązanie wolne od blokady. W takich wypadkach stosuje się algorytmy probabilistyczne. W przypadku stosowania takich algorytmów nie mamy pewności, że konstruują one rozwiązania poprawne, wiemy jednak, że dają je z prawdopodobieństwem równym 1.
Przedstawimy teraz rozwiązanie Problemu pięciu filozofów z wykorzystaniem algorytmu probabilistycznego.
Najpierw jednak scharakteryzujemy Problem 5 filozofów:
Przy stole siedzi pięciu filozofów, którzy na przemian jedzą spaghetti ze wspólnej miski oraz myślą. Żeby się najeść filozof potrzebuje dwa widelce, przy czym każdy z widelców jest współdzielony z sąsiadem. Każdy z filozofów wykonuje zatem cyklicznie następujące czynności: myśli, bierze widelce, je, odkłada widelce i znowu myśli. Widelec jest używany w trybie wyłącznym, czyli tylko jeden z dwóch siedzących obok siebie filozofów może z niego korzystać. Ponad to filozof może korzystać tylko z widelców leżących bezpośrednio przy nim. Należy napisać dla filozofów taki algorytm, aby:

• nie doszło do zakleszczenia
• nie doszło do zagłodzenia żadnego z filozofów

Algorytm probabilistyczny dla tego problemu (dla każdego filozofa) przedstawia się następująco:

1. Rzuć monetę, by wylosować lewą lub prawą stronę
2. Czekaj aż wylosowany widelec będzie wolny i podnieś go
3. Jeśli drugi widelec jest zajęty to odłóż podniesiony widelec i przejdź do kroku 1.
4. Jeśli drugi widelec jest wolny to go podnieś
5. Jedz
6. Odłóż oba widelce

Przy takim algorytmie prawdopodobieństwo, że n filozofów podniesie ten sam widelec wynosi 1/2ⁿ i z każdą następną próbą maleje 2ⁿ krotnie.
Wydawać może się, że takie rozwiązanie jest banalne, jednak znalazło ono zastosowanie w protokole dostępu do sieci Ethernet, w tzw. technice CSMA/CD. Technika ta wykorzystuje mechanizm detekcji kolizji: do wspólnego medium (współdzielony zasób) podłączony jest szereg stacji roboczych. Każda stacja wykonuje następujący algorytm: stacja śledzi stan medium i zaczyna nadawać, gdy medium jest wolne. Gdy dojdzie do kolizji, tzn. gdy dwie stacje jednocześnie zaczną nadawać, wszystkie stacje przerywają nadawanie i wznawiają je po losowo wybranym odcinku czasu. Takie rozwiązanie sprawdza się bardzo dobrze, lecz nie może być stosowane w systemach sztywnego czasu rzeczywistego (HRT).