Minimal threshold separators and memory requirements for synchronization

Suppose that in a system of asynchronous parallel processes, certain pairs of processes mutually exclude one another (must not be in their critical sections simultaneously). This situation is modeled by a graph in which each process is represented by a vertex and each mutually excluding pair is repr...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1989-02, Vol.18 (1), p.152-165
Main Author: ORDMAN, E. T
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Graphs
Labeling
Philosophers
Tape drives
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Suppose that in a system of asynchronous parallel processes, certain pairs of processes mutually exclude one another (must not be in their critical sections simultaneously). This situation is modeled by a graph in which each process is represented by a vertex and each mutually excluding pair is represented by an edge. Henderson and Zalcstein have observed that if this graph is a threshold graph, then mutual exclusion can be managed by simple entrance and exit protocols using ${\bf PV}$-chunk operations on a single shared variable whose possible values range from zero to $t$, the minimal threshold separator number of the graph. A new expression is given for this separator $t$ of a threshold graph in terms of the normal decomposition of the threshold graph given by Zalcstein and Henderson. It is shown that $t + 1$ values would be needed in the shared variable even if the mutual exclusion were being managed by the Fischer-Lynch test-and-set operator, which is considerably less restrictive than ${\bf PV}$-chunk.
ISSN:0097-5397
1095-7111
DOI:10.1137/0218010