# An Efficient Causal Group Communication Protocol for Free Scale Peer-to-Peer Networks
## 4 Discussion
### Protocols Designed for Plain Networks
#### 4.1.2 Protocols that Use Logical References  
This section contains the protocols that are designed for plain peer-to-peer networks and do not use the global time reference. To ensure causal ordering, these protocols use the \"happened before\" relation defined by [PERSON] [30].  
The Causal Ordering in Deterministic Overlay Network [10] protocol uses the idea to forward each received message. Thus this protocol does not require any control information to be sent with a message, but in the worst case scenario, it produces \(n\)-\(1\) copies (where \(n\) is the number of peers in the system) of the same message saturating the communication channels.  
The Critical Causal Order of Events in Distributed Virtual Environment protocol [23] is based on the idea of reducing causal order violations and not completely removing them. To achieve this reduction, this protocol resends the last received message with the new message, thus doubling the average message size. However, the protocol does not require any control information to be sent alongside the message to ensure message causal ordering.  
An Efficient Algorithm for Causal Message Ordering [12] extends the idea of vector clock [32] for the cases where each message is addressed to a different subset of processes. This modification requires more information to be stored than in the Vector clock protocol. In the worst case scenario, this protocol requires storing an entry for each process in a group, thus producing an overhead of O(\(n\)) (where \(n\) is the number of peers in the system) and when sending a message, all of these entries must be included.  
Probabilistic Analysis of Causal Message Ordering [22] analyzes the probability of violation of causal order of messages. This protocol implies that if the message send is delayed after the last send or receive event, the probability decreases and can decrease down to \(0\). This method does not require any control information at all, but reduces the concurrency of the system.  
The Immediate Dependency Relation protocol [14] is based on the idea of sending only the identifiers of immediate predecessors of a message. This produces the reduced average overhead compared to the vector clock protocol. However, in the worst case scenario, the overhead in the communication channels can be as high as the number of processes in the system (O(\(n\)), where \(n\) is the number of peers in the system). In regard to storage requirements, this protocol stores vector clock and message control information, thus producing storage requirements twice as high as the number of peers in the system.  
An optimal algorithm for enforcing the causal messages ordering is proposed in [24]. The algorithm achieves the optimality by using four propagation constraints to reduce the propagation of redundant information and by using an encoding scheme to represent and attach in messages only the necessary causal dependency information. A performance analysis of the communication overhead of the optimal algorithm under a wide range of system conditions using simulations is presented in [25]. The results indicate that the optimal algorithm performs significantly better than the algorithm proposed in [33]. However, the communication overhead in the worst case is O(\(n\)), where \(n\) is the number of peers in the system (broadcast case).