The congenial talking philosophers problem in computer networks
Resource
Distributed Computing 15 (3): 155-175
Journal
Distributed Computing
Journal Volume
15
Journal Issue
3
Pages
155-175
Date Issued
2002
Date
2002
Author(s)
Abstract
Group mutual exclusion occurs naturally in situations where a resource can be shared by processes of the same group, but not by processes of different groups. For example, suppose data is stored in a CD-jukebox. Then when a disc is loaded for access, users that need data on the disc can concurrently access the disc, while users that need data on a different disc have to wait until the current disc is unloaded. The design issues for group mutual exclusion have been modeled as the Congenial Talking Philosophers problem, and solutions for shared-memory models have been proposed [12, 14]. As in ordinary mutual exclusion and many other problems in distributed systems, however, techniques developed for shared memory do not necessary apply to message passing (and vice versa). So in this paper we investigate solutions for Congenial Talking Philosophers in computer networks where processes communicate by asynchronous message passing. We first present a solution that is a straightforward adaptation from Ricart and Agrawala's algorithm for ordinary mutual exclusion. Then we show that the simple modification suffers a severe performance degradation that could cause the system to behave as though only one process of a group can be in the critical section at a time. We then present a more efficient and highly concurrent distributed algorithm for the problem, the first such solution in computer networks.
Subjects
Distributed algorithms; Group mutual exclusion; Message passing; Mutual exclusion; Resource allocation
Other Subjects
Algorithms; Computational complexity; Computer networks; Computer simulation; Data communication systems; Philosophical aspects; Resource allocation; Theorem proving; Congenial talking philosophers problem; Distributed algorithms; Group mutual exclusion; Message passing; Distributed computer systems
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
3.pdf
Size
702.42 KB
Format
Adobe PDF
Checksum
(MD5):1a4fa0566a5840691d7390c9ab2a6c3f