# An Efficient Causal Group Communication Protocol for Free Scale Peer-to-Peer Networks
## 3 Results  
### Protocol Composition  
#### 3.1.1 Data Structure  
In order to define data structures to ensure message causal ordering, we need to define additional data types and structures that will be used throughout this document.  
A bit vector is an array of variable size. Each element can take only two values: set (represented by 1) and cleared (represented by 0). Each bit vector can be extended with zeros to a required size and the trailing zeros can be trimmed. An empty bit vector is denoted as \(\O\).  
Bits are numbers starting from 1. \(V[x]\) represents a bit at position \(x\) in vector \(V\). A bit at position 0 is assumed to be always set. Bit vectors support AND (&), OR (1) and NOT ( ) operations that are bitwise, i.e., the operation is applied to bits at Position 1, then bits at Position 2, etc.  
Extended Vector Time (\(VTx\)) is a vector of \(LTx\). Each element does not depend on others. Thus, a vector can have one element that is an integer and another element that is a bit vector at the same time.  
Data Structures in an Internal Peer  
Each internal peer maintains the following data:\(id_{int}\)--identifier of a peer in the internal group. This identifier must be unique in a group.
* \(SN\)--an integer representing a sequence number of a message.
* \(RV\)--bit vector representing received messages.
* \(DV\)--bit vector representing message IDR.  
Data Structures in an External Peer  
In an external group, each peer maintains the following variables:  
* \(id_{ext}(p)\)--identifier of a peer in the external group. This identifier must be unique in a group.
* \(VTx(p)\)--extended vector time. The size of a vector is \(G\), where \(G\) is the number of peers and super peers in an external group.
* \(CI\)--vector of pairs representing message control information. Each pair consists of a process identifier and \(LTx\). \(CI[x]\) is a pair where the process identifier is \(x\).  
Data Structures in a Super Peer  
A super peer maintains the following variables:  
* \(id_{ext}(sp)\)--identifier of a super peer in the external group.
* \(VTx(sp)\)--extended vector time. The size of a vector is \(G\), where \(G\) is the number of peers and super peers in an external group.
* \(I\)--bit vector representing identifiers of translated messages.
* \(LR\)--vector of pairs of size \(L\), where \(L\) is the number of peers in an internal group of this super peer. Each pair contains two sequence number names, _in_ and _out_.
* \(TT\)--vector of vectors of pairs. The size of a vector is \(G\). Each pair consists of two message identifiers called _in_ and _out_.  
Internal Group Message Structure  
Messages in an internal group are denoted by \(m_{int}\) and have the following structure:  
\[m_{int}\;=\;(id,\;SN,\;Last,\;DV,\;Data) \tag{1}\]  
where  
* \(Id\)--the identifier of a sending process in the internal group.
* \(SN\)--an integer representing a message sequence number.
* \(Last\)--an integer identifier of the last message from this peer.
* \(DV\)--a bit vector representing message dependency.
* \(Data\)--the user data to be transmitted.  
This message structure is used by both peers and super peers in an internal group (see Figure 2).  
External Group Message Structure  
In an external group, messages are denoted by \(m_{ext}\) and have the following structure:  
\[m_{ext}\;=\;(id,\;SN,\;CI,\;I,\;Data) \tag{2}\]  
Figure 2: Messages in a free scale peer-to-peer network.  
where  
* _Id_--the identifier of a sending process.
* _SN_--an integer representing a message sequence number.
* _CI_--vector of pairs representing message control information. Each pair consists of a process identifier and _LTx_.
* _I_--bit vector with internal message identifiers.
* _Data_--the user data to be transmitted.  
This message structure is used by both peers and super peer in an external group (see Figure 2).