# How probable is a deadlock in the dining philosophers problem

I created this simulation of the dining philosophers problem, but did not manage to initialize it with four philosophers without running into a deadlock:

*Philosophers are represented by black beads. They think when running in small circles and eat when running in bigger circles. Forks are represented by yellow beads. The number of meals are counted.

Might it be the case that for $N=4$ participating philosophers a deadlock must inevitably be reached? Or can a situation be described in which four philosophers can eat for ever and ever?

I am looking for a quantitative model and analysis of the dining philosophers problem.

Let $N$ be the number of philosophers. Let the problem be implemented as an algorithm that takes as inputs the set $T_k$ of partial functions $t: [N] \rightarrow [k]$ with $t(i)$ being the point in time when philosopher $i$ starts trying to pick the fork to his left (maybe never). The algorithm stops when it detects a deadlock or an oscillating state in which a philosopher starves.

I wonder especially about the probability $p_{stop}^{(k,n)}$ that the algorithm will stop, depending on the number $n$ of philosophers that join the diner, $n \leq N$.

$$p_{stop}^{(k,n)} = \frac{|\text{functions t \in T_k^n for which the algorithm stops}|}{|T_k|}$$

with $T_k^n$ the functions $t\in T_k$ with $|\text{dom}(t)| = n$.

• It really depends on what algorithm the philosophers follow. Some algorithms provably avoid deadlock. – Yuval Filmus Apr 13 '16 at 14:34
• I'm interested in algorithms that do not try to avoid deadlock, like the one described at Wikipedia (en.wikipedia.org/wiki/Dining_philosophers_problem#Problems) on which my simulation is based. – Hans-Peter Stricker Apr 13 '16 at 14:53
• In that case my answer below works. – Yuval Filmus Apr 13 '16 at 14:55
• You can deadlock for any N > 1 (algorithm dependent). It just becomes more likely the higher N gets (up to a point, anyways). – Clockwork-Muse Apr 13 '16 at 15:32

the dining philosopher problem seems to be somewhat of a pedagogical "toy" example of concurrency and (dead)locking concepts for educational purposes. however it is studied seriously in some literature and there are some performance analyses of its probability of deadlock scenarios. here are some examples of quantitative models and performance analysis and other frameworks on the problem which attempt to consider the probability of deadlocks from theoretical derivations and observed scenarios (simulations etc).

I don't know what algorithm the philosophers follow, but let's assume that deadlock is reached if all philosophers try to start eating at the very same time. Since your time is discrete, under any reasonable probability distribution over the "thinking times", it will necessarily (almost surely) eventually happen that all philosophers try to start eating at the very same time (exercise, which also includes formulating the problem properly).

• That's what I suspected. What I wonder then is, why in the Wikipedia article it is stated that the algorithm "allows the system to reach a deadlock state". It would make a difference to the reader when it said, that a deadlock state is inevitable. – Hans-Peter Stricker Apr 13 '16 at 14:58
• The two are not necessarily equivalent. It might be that if you make a bad choice on the first round then a deadlock state is inevitable, but otherwise it cannot occur. – Yuval Filmus Apr 13 '16 at 15:00
• This contradicts your first statement: "[a deadlock] will necessarily (almost surely) eventually happen". – Hans-Peter Stricker Apr 13 '16 at 15:10
• All I'm saying is that in principle, "allows" and "inevitably" are different. In your case, it's "inevitably" for any algorithm in which deadlock is reached when all philosophers try to start eating at the very same time (under mild assumptions on the behavior of the philosophers). For other algorithms it could be only "allows". For example, with probability 1/2 we use a stupid algorithm, an otherwise we use one which avoids deadlocks. – Yuval Filmus Apr 13 '16 at 15:12