# An Efficient Causal Group Communication Protocol for Free Scale Peer-to-Peer Networks
## 1 Introduction  
Multiparty overlay systems, such as peer-to-peer, are technologies that can solve problems in information distribution and processing, in areas including file distribution [1,2], multiplayer interactive games [3] and telecommunication [4]. These systems are characterized by considering a group communication between \(n\) (\(\geq\)2) peers that are distributed geographically. To achieve a consistent exchange of information in this environment, messages from the peers have to be causally ordered [5]. The use of causal ordering in the overlay peer-to-peer systems provides message synchronization and reduces the indeterminism produced by asynchronous execution of the peers and by random and unpredictable delays of the messages in the communication channels. Causal ordering guarantees that the actions (requests or questions) are delivered before corresponding reactions (results or answers). Some works have proposed protocols to guarantee causal ordering delivery of the messages [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]. These protocols can be classified into three categories. The first category includes the protocols designed for plain peer-to-peer networks. We can classify [12, 14, 24, 25] in this category. One disadvantage of these protocols is that the size of the control information in the worst case scenario grows with the number of peers in the network. In addition, the protocols from this category add additional processing to the peers that also depends on the number of peers in the system. The second category includesprotocols that are designed for free scale peer-to-peer networks. In the case of this topology, the peers can be separated into two groups: peers and super peers. Super peers are characterized by higher processing powers and/or bandwidth. This network topology was designed to solve some problems of the plain P2P networks, such as bottlenecks caused by the very limited capabilities of some peers. Free scale peer-to-peer networks take advantage of system heterogeneity, assigning greater responsibility to those who are more capable of handling it [28]. The similar topology can be seen in the Virtual Private Network (VPN) technology [29], where Intranet computers can communicate directly between each other but the remote clients communicate through the VPN server. However, up to date there are no protocols to guarantee causal ordering delivery of the messages, specifically designed for such networks. To overcome the lack of dedicated solutions for these networks, some protocols for plain topology can be adapted by establishing the causal order under each super peer. Nevertheless, besides the problems related to the uncontrolled overhead growth, these approaches may induce unnecessary inhibition on the delivery of messages. The third category incorporates all the protocols that are designed for the hierarchical networks [7; 8; 11; 13; 15; 16; 17; 18; 26; 27], where the network topology is established to disable the direct communication among peers, allowing only the connections among super peers and between a super peer and each of its dependent peers. Similar to the case of free-scale networks, some protocols proposed for other topologies can be adapted to hierarchical networks. This is the case of the protocol proposed by [PERSON] and [PERSON] [10], which has good characteristics in hierarchical sparse networks where the peers have a low message sending rate. However, since this protocol has a quadratic traffic cost, serious overloads in super peers' channels be caused in dense networks. Besides this approach, there are some protocols specifically designed for hierarchical networks [13; 17; 18] which are based on the use of a global time reference to ensure causal ordering of messages. Unfortunately, the characteristics of most hierarchical networks make it difficult to establish a global time reference; this is mainly due to the absence of shared memory and the lack of perfectly synchronized clocks [30].