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

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

Isamu Tsuneizumi (Seikei University, Japan), Ailixier Aikebaier (Seikei University, Japan), Makoto Ikeda (Seikei University, Japan), Tomoya Enokido (Risho University, Japan) and Makoto Takizawa (Seikei University, Japan)
Copyright: © 2011 |Pages: 12
DOI: 10.4018/jdst.2011070103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

To realize the cooperation of a group of multiple peer processes (peers), messages sent by peers must be causally delivered to every peer. In a scalable group, it is necessary to reduce the communication overhead to causally deliver messages. In this paper, the authors take advantage of the linear time (LT) and physical time (PT) protocols, as the message length is O(n) for the number n of peers. However, some pairs are unnecessarily ordered, that is, even if a pair of messages is ordered in the protocols, the messages may not be causally ordered. The greater the number of messages that are unnecessarily ordered, the larger the overhead is implied since the messages must be kept in a receipt queue if a message is lost or delayed. This paper discusses a hybrid time group communication (HT) protocol that reduces the number of messages unnecessarily ordered. The HT protocol is evaluated in terms of the number of unnecessarily ordered messages compared with the PT and LT protocols. It is demonstrated that the number of unnecessarily ordered messages can be reduced in the HT protocol compared with the LT and PT protocols.
Article Preview

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 p1, …, pn (n > 1). Each peer pi takes usage of its own physical clock ci. Here, maximum gap of each physical time of ci with accurate time is bounded to be some value λi. The accuracy λi of each physical clock of a peer pi depends on the distance, i.e. number of routers and traffic between the peer pi and the time server and on a type of operating system like Linux and Windows. Let dij be the minimum delay time between a pair of peers pi and pj . In this paper, we consider a homogeneous broadcast group where λi = λ and dij = d for every pair of peers pi and pj 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing