# An Efficient Causal Group Communication Protocol for Free Scale Peer-to-Peer Networks
## 3 Results
### Protocol Composition
#### 3.1.2 Specification of the Causal Protocol  
Initially each process performs an initialization process. An internal peer performs this process as follows. \[\begin{array}{l}\text{\small  
of the messages that form the immediate dependency relation with the currently received message (see Listing 5). If (\(RV[m_{int}.Last]=1\)) then // FIFO condition  
If (\(m_{int}.DV\) & \(RV=m_{int}.DV\)) then // Causal condition  
Deliver(\(m_{int}\))  
End if  
If a delivery condition is satisfied, a peer updates its data structures (see Listing 6) and it can deliver a message to a corresponding application. If a delivery condition is not satisfied, a message should be buffered. An internal peer will receive its own message returned by a super peer. In this case, it should only update its receive vector \(RV\). After a message is delivered, a process should check its buffer. If a message in a buffer satisfies a delivery condition, it should be delivered using the same algorithm (see Listing 6). Since a super peer only transmits messages from other peers, it does not have a message emission phase. When a super peer receives a message from an internal peer, it checks the message delivery condition. Since an internal peer can only receive messages from a super peer, it means that only a FIFO dependency needs to be checked. To check the message delivery condition, a super peer uses the following algorithm (see Listing 7). If a delivery condition is satisfied, a super peer can forward this message to other peers (see Listing  
If for any pair in \(CI\) a bit vector is empty, this pair can be removed from \(CI\). If a delivery condition is satisfied in a super peer, it can forward this message to an internal group. To do this, a peer is required to update its data structures to ensure the delivery of messages that depend on this one. This requires an update of a clock so that messages that depend on this one can be delivered. After a message is delivered to a peer or a super peer, a process should check its buffer. If a message in a buffer satisfies a delivery condition, it should be delivered using the same algorithm (see Listing 12 for external peer, and Listing 13 for super peer). As bit vectors \(RV\), \(DV\) and \(VTx\) grow in size during the execution of a protocol with each message, it is necessary to use mechanisms to reduce bit vector sizes. Communication channels are considered to be reliable; thus, every message sent by a super peer will be delivered to an internal group peer. This means that an \(RV\) and \(VTx\) will have bits for each message set. Since a super peer numbers messages with consecutive integers after some execution time, an \(RV\) and \(VTx\) will start with consecutive set bits. Considering that, after a bit is set, it is not changed to a cleared state at any time. Thus, it is required to store bits between the first cleared bit and the last set bit. A vector \(DV\) is based on the immediate dependency relation. Each bit is set only once and then it is cleared when a message is sent or a dependent message is received. Thus, it is only required to store bits between the first and the last set bits. Figure 12: Message delivery to an external peer. To be completely functional, a protocol requires a mechanism to transform messages from an internal group to an external group and vice versa. This transformation is performed by a super peer because it participates in both groups at the same time. A message that originated from an internal group generally carries dependencies on other messages from an internal group and dependencies on messages from an external group. The dependencies on messages from an internal group are represented in a form of bit vector, but to be interpreted correctly in an external group, they should be transformed into a vector of pairs (process identifier, and message dependency). This transformation can be achieved by using the algorithm presented below (see Listing 14). If a message carries only dependencies on external messages, a \(CI[id_{ext}]\) will be an empty vector.