This paper is a survey on the synchronization of a system of cooperating processes, when the mutual exclusion graph model and the semaphores are used. Threshold graphs and PVchunk semaphores are explained. Matroidal and matrogenic graphs are presented and their synchronization with a constant number of semaphores for each process are pointed out. Threshold dimension of a graph is explained and a sketched proof of its NP-completeness for k3 and of the polynomiality for k=2 is provided. The interest in characterizing new classes of graphs not 2-threshold, but synchronizable with a constant number of semaphores, is shown.
Threshold Graphs and Synchronization Protocols / Petreschi, Rossella; Sterbini, Andrea. - 1120/1996:(1996), pp. 378-395. (Intervento presentato al convegno Combinatorics and Computer Science tenutosi a Brest, France nel July 3–5, 1995) [10.1007/3-540-61576-8_97].
Threshold Graphs and Synchronization Protocols
PETRESCHI, Rossella;STERBINI, Andrea
1996
Abstract
This paper is a survey on the synchronization of a system of cooperating processes, when the mutual exclusion graph model and the semaphores are used. Threshold graphs and PVchunk semaphores are explained. Matroidal and matrogenic graphs are presented and their synchronization with a constant number of semaphores for each process are pointed out. Threshold dimension of a graph is explained and a sketched proof of its NP-completeness for k3 and of the polynomiality for k=2 is provided. The interest in characterizing new classes of graphs not 2-threshold, but synchronizable with a constant number of semaphores, is shown.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
