A new approach for fast causal message ordering with Central Control

Abstract

Message synchronization to respect the causal order of the messages is an integral part of distributed simulations. To achieve message synchronization, simulators delay the delivery of a received message until all causally preceding messages are processed. For non-centralized systems, time stamp order delivery is an option but enforces more strict synchronization than necessary besides its reliance on lookahead. In an alternative method, causal order delivery, message delays are reduced in the cost of substantial communication and computation overheads. Even the optimal causal order delivery algorithms such as MSES (Modified Schiper-Egglie-Sandoz) or KS (Kshemkalyani and Singhal) require immense control information (of the order of N2 in the worst case, for a distributed system of N simulators) to be kept in simulators and attached to messages. The reason is mainly the lack of information about other simulators which is solved by attaching control information to the messages. On the other hand, in a centralized system where all simulators send their messages via a central process, causal order delivery can be realized easily. Especially, for a typical first-in-first-out network, the central process does not need to perform anything other than just relaying the messages. The simulators deliver the messages in receive order. Unfortunately, this approach is not scalable since passing all messages through the central process causes serious communication and computation bottleneck. In this paper, a new approach called Central Control-Distributed Messaging (CCDM) mechanism is proposed. In CCDM, while there is a central process, simulators can also communicate directly. Message ordering is facilitated by the central process. Simulators send their messages directly to the destinations and also send a message including only the message identification and destination list to the central process. The central process evaluates messages, orders them by respecting causality and sends delivery information to destinations. Theoretical analysis and experimental results of CCDM on a simulated environment are also presented. CCDM reduces both communication and computation overheads on simulators by reducing the control information size. Moreover, it does not incur a serious network bottleneck around the central process. © 2012 Elsevier B.V., All rights reserved.