Predicate control: synchronization in distributed computations with look-ahead |
| |
| Affiliation: | 1. Akamai Technologies, Inc., 8 Cambridge Center, Cambridge, MA 02142, USA;2. Department of Electrical and Computer Engineering, University of Texas at Austin, Austin, TX 78712, USA;1. Research Center of Forestry Remote Sensing & Information Engineering, Central South University of Forestry and Technology, Changsha 410004, China;2. Key Laboratory of State Forestry Administration on Forest Resources Management and Monitoring in Southern Area, Changsha 410004, China;3. Key Laboratory of Forestry Remote Sensing Based Big Data & Ecological Security for Hunan Province, Changsha 410004, China;1. Technological Center in Oil Well Cementing, Federal University of Rio Grande Do Norte, Natal, Rio Grande do Norte, ZIP code: 59072-970, Brazil;2. Federal University of Rio Grande Do Norte, Natal, Rio Grande do Norte, ZIP code: 59072-970, Brazil;3. Federal University of Rio Grande Do Norte, EAJ, Macaíba, ZIP code: 59280-000, Brazil;1. IDEXX, 1 IDEXX Drive, Westbrook, ME 04092, USA;2. College of Veterinary Medicine, Kansas State University, A-111 Mosier Hall, Manhattan, KS 66506-5802, USA;1. Ufa State Aviation Technical University, Ufa, Russia;2. Orenburg State University Kumertau branch, Kimrtau, Russia |
| |
| Abstract: | The predicate control problem involves synchronizing a distributed computation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual exclusion, readers writers, and dining philosophers, predicate control assumes a look-ahead, so that the computation is an off-line rather than an on-line input. Predicate control is targeted towards applications such as rollback recovery, debugging, and optimistic computing, in which such computation look-ahead is natural.We define predicate control formally and show that, in its full generality, the problem is NP-complete. We find efficient solutions for some important classes of predicates including “disjunctive predicates”, “mutual exclusion predicates”, and “readers writers predicates”. For each class of predicates, we determine the necessary and sufficient conditions for solving predicate control and describe an efficient algorithm for determining a synchronization strategy. In the case of “independent mutual exclusion predicates”, we determine that predicate control is NP-complete and describe an efficient algorithm that finds a solution under certain constraints. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
