Synchronization Problems Solvable by Generalized PV Systems
Peter B. Henderson, Yechezkel Zalcstein · Journal of the ACM · 1980
A basic question m the area of asynchronous computation is.Given a synchromzaUon problem, what synchromzation primitives are needed for an "efficient" solution9 This paper is directed toward answering this question by providing characterizations of those synchronization problems solvable by DIjkstra's PV system of primitives and its various generalizations including PVgeneral, PVmultlple, PVchunk, Vector Addmon, and Loopless Penn Net systems These characterizations form the foundations of a formal synthesis procedure for determining effioent solutions to synchronization problems