Group Communication Protocols Based on Hybrid Types of Logical and Physical Clocks

摘要

In distributed systems, multiple processes are cooperating with each other by exchanging messages in underlying networks. In order to realize distributed applications, a group of n processes are required to cooperate with each other. In a distributed group, each member process is peer and directly exchanges messages with other processes with no centralized coordination. That is, each process sends messages to other processes and receives messages from other processes in a group. Each process has to not only reliably and efficiently but also causally deliver messages. In addition, a group is required to be scalable. In this paper, we discuss a hybrid type of clock (HC) to causally deliver messages in a scalable group. The HC protocol takes advantage of linear clock (LC) and physical clock (PC). There might be no causally precedent relation between some pair of messages ordered in the LC protocol. This means, some pair of messages are unnecessarily ordered. A physical clock in a computer is now synchronized with a time server in NTP and PTP. Thus, a process can read more precise physical time on each computer. In the LC and PC protocols, each message carries just LC and PC variables, respectively. Hence, the message length is O(1) for number n of processes in a group. We show unnecessarily ordered messages can be reduced in the HC protocol compared with the LC protocol through the evaluation of the implemented HC protocol.