A scalable group communication protocol with hybrid clocks

摘要

In peer-to-peer (P2P) applications, messages have to be causally delivered to every peer of a group of n (>1) peers. Owing to the message overhead O(n), the vector clock cannot be used to causally deliver messages in a scalable group. On the other hand, since the message length is O(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.