pandolfi@lifia.imag.fr (Xavier Pandolfi ) (11/13/90)
Hello,
Several weeks ago, I posted the following enquiry :
I am looking for articles/references concerning lower bounds
for the number of messages the participating processes
need to send in the worst case in order to respect :
1. the drinking philosophers problem
2. the dining philosophers problem
3. the mutual exclusion problem
when the solution under consideration is :
a. standard
b. without deadlock
c. starvation free
Please send informations ...
I received many messages but no answer to my questions :
Andy Glew (aglew@dwarfs.crhc.uiuc.edu) sent me references on
mutual exclusion algorithms with their upper bounds but no
reference on lower bounds for this problem. Anyway thank you Andy !
I also received messages from Ciaran McHale (cjmchale@cs.tcd.ie),
Arup Acharya (acharya@paul.rutgers.edu),
Bill Williston (freewill@nstar.UUCP),
Paulo Rosado (pr@fct.unl.pt).
Thanks to you all !
My own bibliography research gives the following result :
"How processes learn" K.M. Chandy and J. Misra,
Distributed Computing 1 (1986)
considers the standard mutual exclusion problem and proves that at
least one message must be exchanged by neighboring philosophers
between their drinking sessions.
Many people asked me a definition of the "drinking philosophers problem".
So here it is :
The drinking philosophers problem is a paradigm for conflict resolution
in distributed systems. In this problem there is an arbitrary graph with
a bottle on each edge and a philosopher at each node. A philosopher is
in one of three states : (1) "tranquil", (2) "thirsty", or (3) "drinking".
A philosopher may be in the tranquil state for an arbitrary period of time.
A tranquil philosopher may become thirsty.
A thirsty philosopher needs a nonempty set of bottles that he wishes to
drink from. A philosopher can drink only from bottles associated with
his incident edges. A thirsty philosopher remains thirsty until he gets
all bottles he needs to drink.
On holding all needed bottles, a thirsty philosopher starts drinking. He
may need different sets of bottles for different drinking sessions. On
entering the drinking state a philosopher remains in that state for a
finite period, after which he becomes tranquil.
Two philosophers are neighbors if and only if there is an edge between
them (they share a least one bottle).
The problem is to design a program that guarantees that neighbors do
not drink at the same time from a same bottle.
The dining philosophers problem is the particular case of the drinking
philosophers problem where a thirsty (hungry) philosopher always needs
to hold all the bottles (forks) associated with his incident edges in
order to start drinking (eating).
The mutual exclusion problem is the particular case of the dining
philosophers problem where the neighboring relation is total (the graph
is complete).
The system of philosophers is said to be deadlocked when no philosopher
is drinking and no thirsty philosopher can ever start drinking.
A solution is said to be "starvation" free if every thirsty philosopher
will eventually get to drink.
I think the original paper on this problem is :
"The drinking philosophers problem"
K.M. Chandy and J. Misra
ACM TOPLAS Vol 6(4), Oct 84, pp 632-646
--
-- Xavier Pandolfi
LIFIA - IMAG Tel : 76-57-46-58
46, Av Felix Viallet Mail : pandolfi@lifia.imag.fr
38031 Grenoble Cedex, France