Synchronization in message passing systems
Ye Su, Gurdip Singh · 2004
Processes in a distributed program may have to communicate and synchronize to accomplish their tasks. The problem of synchronization in different processes, where a region is a block of code whose execution may require synchronization. In general, the region occupancy rules may be complex and ad hot in nature and deriving an algorithm to enforce such rules can be a tedious and an error prone task. In this thesis, we propose a technique to derive algorithms for synchronization in message passing systems. We adopt an aspect oriented technique for systematic development of synchronization code for message passing systems. Our approach is to factor out synchronization as a separate aspect, synthesize synchronization code and then compose it with the functional code. Specifically, we allow the designer to first design the functional code. The designer can then annotate the functional code with regions and specify a high-level “global invariant” specifying the synchronization policy. Given this invariant, a region synchronization protocol is derived in a systematic manner that grants permissions for entering and exiting regions in a sequence that does not invalidate the invariant. Although algorithms for centralized systems have been presented earlier, we show that straightforward translation of these algorithms to distributed systems may result in an incorrect solution. We first give a correctness condition for a region synchronization algorithm in a distributed system and present translations for point-to-point message passing systems and broadcast based message systems such as a controller area network (CAN). We also show how application semantics can be used to improve the performance of our algorithms. With these optimizations, the performance of our algorithms matches that of existing algorithms designed for specific synchronization problems.