The Congenial Talking Philosophers
The problem concerns a set of N philosophers
P1 , P2 , ..., PN
which spend their time thinking alone and talking in a forum. Initially,
all philosophers are thinking.
From time to time, when a philosopher is tired of thinking,
it wishes to attend a forum of its choice. Given that there is only one
meeting room, a philosopher attempting to
enter the meeting room to attend a forum can succeed
only if the meeting room is empty (and in this case the philosopher starts the
forum), or some philosopher interested in the forum is already
in the meeting room (and in this case the philosopher joins this
ongoing forum). We assume that when a philosopher has attended a forum,
it spends an unpredictable but finite amount of time in the forum.
After a philosopher leaves a forum (that is, exits the
meeting room), it returns to thinking.
The problem is to design an algorithm for the philosophers
satisfying the following requirement:
- Mutual Exclusion:
If some philosopher is in a forum, then no other philosopher can be in
a different forum simultaneously.
- Bounded Delay:
A philosopher attempting to attend a forum will eventually succeed.
- Concurrent Entering:
If some philosophers are interested in a forum and no philosopher is interested
in a different forum, then the philosophers can attend
the forum concurrently.
The problem has been proposed by Joung (1998a),
to model the design issues
where resources can be shared by processes of the same group but
the sharing cannot across the group;
and solutions for the problem for various execution models have been
proposed. For shared-memory models, please refer to
Joung (1998a),;
for complete message-passing networks, please refer to
Joung (1998b);
and for ring networks, please refer to Wu and Joung (1998).
For java applets illustrating some concepts of the algorithms presented in
the above papers see the following workbenches:
Reference
-
Y.-J. Joung (1998a).
Asynchronous group mutual exclusion (extended abstract).
In Proceedings of the 17th Annual ACM Symposium on Principles of
Distributed Computing (PODC), pages 51-60, Puerto Vallarta, Mexico, June 1998. ACM Press.
Full version in Distributed Computing,
Vol. 13, No. 4, 2000.
-
Y.-J. Joung (1998b).
The congenial talking philosophers problem in computer networks.
Extended abstract to appear in Proc. 13th International Symposium on
DIStributed Computing (DISC'99).
Full version submitted for publication.
K.-P. Wu and Y.-J. Joung (1998).
Asynchronous
Group Mutual Exclusion in Ring Networks. In Proceedings of the 13th International Parallel Processing Symposium (IPPS) & 10th Symposium on Parallel and Distributed Processing (SPDP), pages 539-543,
San Juan, Puerto Rico, April 1999.
Full version in
IEE Proceedings-Computers and Digital Techniques, Vol. 147, No. 1, pages 1-8, January 2000.
-
G. Ricart and A. K. Agrawala (1981).
An optimal algorithm for mutual exclusion in computer networks.
Communications of the ACM, 24(1):9--17.
Related Sites:
Workbench for Ricart and Agrawala's Algorithm
Last updated 2/26/2001.