# An Efficient Causal Group Communication Protocol for Free Scale Peer-to-Peer Networks
## 3 Results
### Protocol Composition
#### 3.1.4. Causal Protocol Description  
To describe how our proposed protocol detects causal order violations, we use a scenario (see Figure 3) composed of a network that consists of the following:  
* Two internal peers with identifiers in an internal group 1 and 2, denoted as \(P(i)_{1}\) and \(P(i)_{2}\). * A super peer with an identifier in an external group 1, denoted as \(Sp_{1}\). * Two external peers with identifiers in an external group 2 and 3, denoted as \(P(i)_{2}\) and \(P(i)_{3}\). This scenario contains three types of messages:  
* Messages in an external group, represented as a solid line. * Messages in an internal group from peer to super peer, represented by a dashed line. * Messages in an internal group from super peer to peers, represented by a dotted line. We mark with the \(X\) a message delivery that violates a causal order. Diffusion of \(m_{3}\) at \(P(i)_{2}\)  
* First, an internal peer increments its sequence number to 1 (see Listing 4, Line 1). * An internal peer generates a message \(m_{3}\) = (2, 1, 0, 01, \(Data\)) (see Listing 4, Line 2). * The \(DV\) variable is cleared (see Listing 4, Line 3). Reception of \(m_{3}\) at \(Sp_{1}\)  
* When a super peer \(Sp_{1}\) receives \(m_{3}\), it checks its delivery condition. The FIFO delivery condition is satisfied (see Listing 7, Line 1): 1 = 0 + 1 and message \(m_{3}\) can be delivered. Figure 3: Scenario example. * \(m_{3}\)_Last_ field is changed to 0 (\(LR[2].out=0\)) (see Listing 8, Line 1). * A clock for this super peer is updated with a new value (see Listing 8, Line 2): \(VTx(p)=(3,1,1)\), and \(LR\) is updated with message identifiers (see Listing 8, Line 3): \(LR[2]=<1\), \(3>\). * \(m_{3}\)_SN_ is updated to 3, and \(m_{3}\) is sent to all peers in an internal group. Transformation of \(m_{3}\) at \(Sp_{1}\) to External Group  
* \(I_{m}=11\) and \(I\) is set to \(\O\) (see Listing 14, Lines 1-2), and \(CI\) is created with value \(<\)1, 01\(>\) and \(TT[2]\) contains \(<\)1, 2\(>\) (see Listing 14, Line 7). * \(CI\) element \(<\)1, 01\(>\) has its bit 2 cleared (see Listing 14, Line 9): \(<\)1, \(\O\)\(>\), and this dependency is removed. \(CI\) is updated with message dependency (see Listing 14, Line 11): CI = \(<\)2, 1\(>\) and, \(m_{3}\) is transformed to an external group: \(m(e)_{3}=(1,3,<\)2, 1\(>\), 11, \(m_{3}\)_Data_). Reception of \(m(e)_{3}\) at \(P(e)_{3}\)  
* When a peer \(P(e)_{3}\) receives \(m(e)_{3}\), the process clock is updated \(VTx(p)=(11,0,1)\). * Then the delivery condition is checked. \(\circ\) The FIFO delivery condition is not checked because the message arrived from a super peer. \(\circ\)\(m(e)_{3}.CI\) contains \(<\)2, 1\(>\) and but \(VTx[2]=0\), so this dependency is not satisfied. \(\circ\) The message delivery condition is not satisfied; therefore, the message \(m(e)_{3}\) should be buffered. Reception of \(m_{2}\) at \(P(e)_{3}\)  
* When a peer \(P(e)_{3}\) receives \(m_{2}\), it checks its delivery condition. \(\circ\) The FIFO delivery condition is satisfied (see Listing 11, Line 1): 1 = 0 + 1 and \(m_{2}.CI\) contains \(<\)3, 1\(>\), and this dependency is satisfied because \(id_{ext}=3\). Both conditions are satisfied, and the message \(m_{2}\) can be delivered. * A clock component for peer 2 is updated with a new value (see Listing 12, Line 2): \(VTx(p)=(11,1)\) and \(CI\) is empty, so a new message dependency is inserted (see Listing 12, Line 10): \(CI=<\)2, 1\(>\). * Message buffer contains \(m(e)_{3}\). Its delivery condition should be revalidated. \(\circ\) The FIFO delivery condition is not checked because the message arrived from a super peer. \(\circ\)\(m(e)_{3}.CI\) contains \(<\)2, 1\(>\) and \(VTx[2]\) is an integer, so the causal condition is satisfied (see Listing 11, Line 2): \(1\leq 1\). \(\circ\) Both conditions are satisfied, and the message \(m(e)_{3}\) can be delivered. * A clock component for super peer (\(id_{ext}=1\)) is updated with a new value (see Listing 12, Line 2): \(VTx(p)=(111,1,1)\).