Implementation of an Adaptive Total Ordering Protocol

†† Summary In distributed systems, the communication among group members often needs ordered messages to guarantee that every member receives the messages in the same order. Oftentimes, changes in distributed computing environment occur and this undermines the assumption of any ordering algorithm. Therefore, it is difficult to presume a suitable ordering algorithm and apply a single algorithm throughout the lifetime of the system. In this paper, we present an adaptive total ordering protocol and its implementation on our reconfigurable object model. Our adaptive protocol selects a suitable ordering protocol from optimistic and pessimistic total ordering protocols dynamically depending on the runtime environment. With optimistic protocol, it is possible to reduce the affect of the network latency which is not negligible in the pessimistic protocol, because the optimistic protocol delivers messages immediately after receiving them. The optimistic protocol though incurs high ordering cost during rollback, and so in this case, it is worth using the pessimistic algorithm instead. The adaptive protocol is realized on the reconfigurable object model. This object model enables dynamic changing of object behaviors by reconfiguring consists of meta-objects. The total ordering processes are dealt in one of the meta-objects, called reordering meta-object. Therefore reconfiguration makes it possible to switch a total ordering protocol to others dynamically depending on the runtime environment. We introduce the reconfigurable object model and the method to realize the total ordering protocol in this model. To explain the adaptive ordering protocol, we show the implementation including detecting environmental change and reconfiguring object. We looked into the feasibility of our adaptive total ordering protocol in this paper. We present the requirements to realize our adaptive protocol, and show how the adaptive protocol is implemented on the reconfigurable object model.