# Towards a Highly Available Model for Processing Service Requests Based on Distributed Hash Tables
## 2 Materials and Methods
### System Scalability Based on the Intrinsic Properties of the Chord DHT  
To explain mathematically the scalability of the system based on distributed hashing, one needs to show that its performance degrades very slowly, with respect to the number of peers participating in the DHT. If examining the Chord routing protocol in [9], note that, each peer \(p\), having Chord ID \(ID_{p}\), which has a routing table composed of the so-called finger nodes, the system has an interesting property. If the considered maximum dimension of the Chord ring is \(N=2^{M}\), i.e., \(cardinal(IDSet)=N=2^{M}\), that is, the binary representation of each peer's ID contains \(M\) bits, the following is true for the maximum \(M\) entries in the Chord finger table, used for routing messages via the DHT from source to destination:  
\[\forall k,0\leq k\leq M-1:\]  
\[Finger_{k}\approx ID_{p}+2^{k},\]  
where the approximation means that \(Finger_{k}\) points to the peer which has the closest peer ID to \(ID_{p}+2^{k}\). Of course, the finger table also contains the clockwise successor node of peer \(p\) on the Chord ring, but also its predecessor on the Chord ring. For small values of the deployed number of peers, i.e., \(No_{pers}\lll N\), there might be situations where more finger peers are identical, i.e.,  
\[0\leq i,j\leq M-1,i\
eq j:Finger_{i}=Finger_{j}.\]  
In most of these cases, the number of hops to route a message from the current peer \(p\) towards its destination is less than its maximum possible value. Note that in the Chord DHT [9], _with high probability_, the maximum possible number of DHT routing hops for a message to move from source to destination is in practice \(\approx log_{2}(No_{pers})\). Based on the FingerTable, which is actually the Chord decentralized routing table, which is a sorted list with respect to the fingers' Chord IDs, the distributed algorithm which describes how the routing is performed is described in Algorithm 1, below:```
1:for\(iteration=1,2,\ldots\infty\)do
2:if received new routing request towards \(ChordID(destination)\)then
3:if\((ChordID(predecessor)<ChordID(destination))\) and \((ChordID(destination)\leq ChordID(self))\)then
4: Reply directly to the (new) client; this peer handles its processing request
5:else
6:for\(k=0,1,2,\ldots,log_{2}(MAX(ChordID))-1\)do
7:if\(ChordFinger_{k}\leq ChordID(destination)\) and \(ChordID(destination)\leq ChordFinger_{k+1}\)then
8: Route message to ChordFinger_k
9:endif
10:endfor
11:endif
12:endif
13:endfor
```

**Algorithm 1** ChordImplicitLoadBalancing. This algorithm is distributed and independently run on each DHT peer, which means that the routing is performed as follows: each peer compares the Chord ID of the destination with the peers in its finger table, and finds the closest finger to that destination ID, i.e.,

\[ID_{FingerTable[closest]}\leq ID_{destination}\wedge ID_{FingerTable[closest+1]}>ID_{destination}.\]

The decentralized distributed routing stops when the current peer, that needs to route the message, realizes that \(it\) is the peer responsible for the Chord ID \(ID_{destination}\). In order to identify the theoretical maximum possible number of hops needed to route a message from current peer \(p\) to its destination, one needs to know that when routing a message, the peer compares the entries in its finger table with the ID of the destination, and chooses the closest finger ID as the next hop to route the message. In the best case, the destination is in the finger table of the current peer, which means that there is only one more hop towards the destination. In the worst case, each finger that becomes the next hop towards the destination should perform the steps described here, in a distributed recursive manner, until the destination is reached.