A scalable group communication protocol with hybrid clocks
Isamu Tsuneizumi, Ailixier Aikebaier, Makoto Ikeda, Tomoya Enokido, Makoto Takizawa · Concurrency and Computation Practice and Experience · 2010
Abstract In peer‐to‐peer (P2P) applications, messages have to be causally delivered to every peer of a group ofn(>1) peers. Owing to the message overheadO(n), the vector clock cannot be used to causally deliver messages in a scalable group. On the other hand, since the message length isO(1) in a linear time (LT) and physical time (PT) protocols, which use the linear clock and physical clock, respectively, the protocols can be adopted to scalable groups. However, some pairs of messages are unnecessarily ordered, i.e. even if a pair of the messages is ordered in the protocols, the messages may not be causally ordered. The more the number of messages unnecessarily ordered, the longer it takes to deliver them. In this paper, we propose a hybrid time (HT) group communication protocol to reduce the number of messages unnecessarily ordered by taking advantage of the LT and PT. We evaluate the HT protocol compared with the PT and LT protocols in terms of the number of unnecessarily ordered messages. We show that the number of unnecessarily ordered messages can be reduced in the HT protocol. Copyright © 2010 John Wiley & Sons, Ltd.