## 5 Multi-Replication in Data Centric Storage
### Tug of War (ToW)  
None of the previous works study how many replicas should be allocated in a multi-replication DCS system depending on network conditions for a given event type. ToW [32] is, to the best of our knowledge, the only work in the literature that has addressed this problem. ToW provides the number of replicas that should be used following the \(4^{d}\) schema introduced by multi-replication GHT [30; 31] in order to minimize the overall network traffic. ToW presents 3 new contributions to DCS multi-replication research:  
1. It provides an analytical model that computes the optimal value of the network depth, \(d\), in order to minimize the network traffic. 2. It describes two different DCS operation modes: * **Write-one-query-all**: This is the same mechanism introduced in GHT with multiple replicas. Producers store the information in its closest replica. Then a consumer query has to reach all replicas in order to retrieve all the information related to an event type. An example of this operation mode is shown in Figure 4(a). Figure 4: Multi-replication grid in ToW with combing routing. * **Write-all-query-one**: It is a novel mechanism in which producers store the data in the closest replica, that in turn forwards the information to the remaining replicas. Therefore, all the information related to a particular event type is stored in every single replica. Thus, a consumer only needs to query its closest replication node to retrieve all the information. Figure 4(b) shows an example of this operation mode. 3. It proposes a new routing mechanism that is not hierarchical and recursive like the one proposed by multi-replication GHT. Since replicas are placed in a grid, the authors propose to connect them using a grid replication tree and call it \"combing routing\". Therefore, when a replica receives some data from a producer, in the write-all-query-one mode, it forwards the information along its own row and its own column. The replicas belonging to the same row replicates the information along its column (see Figure 4(b)). In the case a replica receives a query from a consumer in the write-one-query-all mode, it follows the same strategy, the replica routes the query to the rest of the replicas using the combing routing. In this case the replies follow the same path back (see Figure 4(a)). This means (in write-one-query-all mode) that some kind of data aggregation [42] must be in place in order to deliver replies efficiently, although the authors do not study this issue. ToW is analytically compared with multi-replication GHT, and it is shown to be more efficient due to the utilization of the combing routing instead of the hierarchical-recursive routing proposed by GHT with multiple replicas. Moreover, ToW proposes an analytical model to define the optimal value of the network depth, \(d\) (which leads to the number of replicas to be used). The authors analyze a scenario where \(n\) sensors are uniformly deployed in a square region, thus each side of that region has roughly \(\sqrt{n}\) nodes. The authors call \(f_{e}\) and \(f_{q}\) the frequency of producers' events and consumers' queries respectively. In addition, they define a parameter \(k\) that denotes the average number of sensors that detect the same event. The distance between two random nodes inside a unit square is([[http://mathworld.wolfram.com/SquareLinePicking.html](http://mathworld.wolfram.com/SquareLinePicking.html)]([http://mathworld.wolfram.com/SquareLinePicking.html](http://mathworld.wolfram.com/SquareLinePicking.html))), \(\overline{\delta}=0.52\). This helps to model what is the distance from a consumer or producer to its closest replica. **Write-all-query-one Mode**  
The measured cost (in distance) for a consumer to send a query to its closest replica with \(d=0\) has a cost of \(\overline{\delta}\sqrt{n}\). If \(d\) increases, then the distance to the closest replica is divided by a factor \(2^{d}\).