Article Preview
TopIntroduction
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.