Design and Implementation of Hybrid Time (HT) Group Communication Protocol for Homogeneous Broadcast Groups

Introduction

In peer-to-peer (P2P) information systems (Schollmeier, 2001), a group of multiple peer processes (peers) are cooperating to achieve some objectives by exchanging messages with each other. A P2P system is in nature fully distributed with no centralized coordinator and is scalable. Here, messages are required to be causally delivered to peers (Nakamura & Takizawa, 1994). Each peer has to causally order messages received by using some types of clock. The vector time (VT) (Mattern, 1989) is widely used to causally deliver messages in group communication protocols (Birman & Van Renesse, 1994; Moser et al., 1991; Nakamura & Takizawa, 1994). Only and all the messages to be causally ordered can be ordered. However, it is difficult, maybe impossible to adopt the VT protocol due to the message overhead O(n) for the number n of peers in a scalable P2P group. In addition, it is not easy to change the membership information in every peer in presence of the membership change so that a new peer joins or a member peer leaves a group.

Messages can be causally delivered to peers in the linear time (LT) protocol (Lamport, 1978) and the physical time (PT) protocol. Since the message length is O(1) in the LT and PT protocols, the LT and PT protocols can be adopted for a scalable group. However, some messages are unnecessarily ordered. Suppose a peer receives a message m. The peer can deliver the message m only if the peer delivers every message which precedes the message m in the ordering rule of the protocol. If the peer does not receive some message m’ preceding the message m, the peer has to wait for the message m’ even if m’ does not causally precede m.

Thus, the more number of messages are unnecessarily ordered, the longer it takes to deliver the messages. In order to realize an efficient scalable group protocol, we have to reduce the number of unnecessarily ordered messages.

A group is composed of multiple peers p₁, …, p_n (n > 1). Each peer p_i takes usage of its own physical clock c_i. Here, maximum gap of each physical time of c_i with accurate time is bounded to be some value λ_i. The accuracy λ_i of each physical clock of a peer p_i depends on the distance, i.e. number of routers and traffic between the peer p_i and the time server and on a type of operating system like Linux and Windows. Let d_ij be the minimum delay time between a pair of peers p_i and p_j . In this paper, we consider a homogeneous broadcast group where λ_i = λ and d_ij = d for every pair of peers p_i and p_j and each message is sent to every peer. Here, messages which are surely causally ordered in terms of the clock accuracy and minimum delay time are ordered in the physical time. Messages which cannot be ordered in the physical time are ordered in the LT protocol. In this paper, we discuss a hybrid time (HT) protocol which takes advantage of the PT and LT protocols. In the evaluation, we show the number of unnecessarily ordered messages can be reduced in the HT protocol compared with the LT and PT protocols for d ≥ 2λ.

First, we present a system model. Next we discuss the linear (LT) and physical time (PT) protocols. We discuss how to order messages in a heterogeneous broadcast group with the hybrid time (HT) protocol. Finally, we evaluate the HT protocol in terms of the number of unnecessarily ordered messages compared with the PT and LT protocols.