Causally ordered delivery in a hierarchical group of peer processes

Large number of peer processes are cooperating by exchanging messages in peer-to-peer systems. In traditional group protocols, each process communicates with all the other processes in a flat group. Due to the communication and computation overhead O(n) to O(n2) for the number n of processes, it is difficult, may be impossible to adopt the group protocols to a scalable group. In this paper, we discuss a hierarchical group protocol aiming at reducing communication and computation overheads for a group of large number of peer processes. A hierarchical group is composed of subgroups, where each subgroup is furthermore composed of subgroups. Each subgroup supports its own synchronization mechanism to causally order messages. Even if messages are causally ordered in one subgroup, the messages may not be causally ordered in another subgroup. We discuss how to globally causally order messages by using local ordering mechanisms of each subgroup. Finally, we evaluate the hierarchical group protocol compared with traditional flat group protocol in terms of delivery time of messages.