Communication synchronization

Abstract:

Distributed systems generally employ asynchronous communication, despite most theoretical models of such systems being synchronous, and despite synchrony having established performance and robustness benefits for distributed applications. One reason is that synchronous communication is often impractical. Existing mechanisms for providing synchronous abstractions either are not general or do not scale. To address this shortcoming, this document proposes a scalable communication synchronization framework to provide shared logical time. Communication synchronization aligns all network communication to create a single shared sequence of communication events. This sequence is then used as a time reference. The decentralized "average neighbor algorithm" is proposed to maintain synchrony despite drift between local clocks in the system, and this algorithm is proven to be correct and robust. Simulation results indicate that the overhead costs of providing synchrony are minimal, requiring only a small (e.g. 0.1%) fraction of the bandwidth at each network link, and small fixed incoming data buffers. Thus, the framework allows adoption of synchrony in many circumstances where it has previously been impractical.