# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 3 Multi-Phase Adaptive Recoding
### Multi-Phase Relaxed Adaptive Recoding Problem (RAP)  
To maximize the throughput of BNC, we should maximize the expected rank of the batches at the destination node. However, it is unknown whether a suboptimal decision at an intermediate node would lead to a better throughput at the end. To handle this dependency, TAP relaxes the problem into maximizing the expected rank at the next node. We can see that this dependency is very similar to that we have in GAP. By adopting a similar idea, we relax the formulation of GAP by separating the phases into an \(S\)-phase Relaxed Adaptive recoding Problem (RAP):  
\[ \begin{split}\max_{\alpha_{i}\geq 0}&\sum_{i=1}^{S} \max_{T_{i}}\sum_{\tau_{i}}\Pr(r_{i})E(r_{i},t_{\
u_{i}})\\ \text{s.t.}&\sum_{i=1}^{S}\alpha_{i}=t_{\text{avg}}, \\ &\sum_{\tau_{i}}\Pr(r_{i})t_{i,\
u_{i}}=\alpha_{i},\forall i=1,2, \ldots,S.\end{split}  \tag{4}\]  
This relaxation gives a lower bound of (3) for us to understand the throughput gain. Also, by knowing \(\alpha_{i}\), RAP becomes \(S\) individual TAPs with different \(t_{\text{avg}}\)--that is, we can solve individual phases independently by Algorithm 1 when \(\alpha_{i}\)s are fixed. The formulation of RAP looks like it can be solved by considering all \(\Delta_{\cdot,\cdot}\) among the phases altogether and then applying Algorithm 1. Unluckily, this is not the case. Consider a two-phase problem: The expected rank achieved by phase 1 increases when we increase some \(t_{1,r}\) for some \(r\
eq 0\); however, at the same time, the distribution of \(R_{2}\) is changed. After that, the expected rank achieved by phase 2 decreases according to the following theorem, which can be proved by heavily using the properties of adaptive recoding and the first-order stochastic dominance of binomial distributions. If the decrement is larger than the increment, then the overall objective decreases, which means that we should increase some \(t_{2,r^{\prime}}\) for some \(r^{\prime}\
eq 0\) instead, although \(\Delta_{r^{\prime},t_{2,r^{\prime}}}\) may be smaller than \(\Delta_{r,t_{1,r}}\). If the resource for phase \((i+1)\) remains the same or is decreased when some \(t_{i,r}\), \(r\
eq 0\), are increased, then the expected rank achieved by phase \((i+1)\) in the objective of RAP decreases. See Appendix A. Below is a concrete example. Let \(M=4\), the source node sends four packets per batch, and the packet loss rate is \(10\%\). We consider the node right after the source node. At this node, let \(t_{\text{avg}}=4\) and \(p=10\%\), i.e., the same setting as the source node. This way, both nodes have the same set of values of \(\Delta_{r,t}\). We run a brute-force search for \((\alpha_{1},\alpha_{2})\) with a step size of \(0.001\). The solution is \(T_{1}=(0,1,2,3,4)\), \(T_{2}=(0,1,2.9263,4,5)\), when corrected to four decimal places. For our channel settings, we can use some properties of \(\Delta_{r,t}\) proved in [74]. First, \(\Delta_{r,t}=1-p\) when \(t<r\) and \(\Delta_{r,t}<1-p\) when \(r\
eq 0\). Therefore, we can perform a similar greedy algorithm as that in Algorithm 1, starting from \(T_{1}^{\prime}=T_{2}^{\prime}=(0,1,2,3,4)\). Next, there is another property that \(\Delta_{4,4}>\Delta_{3,3}>\Delta_{2,2}>\Delta_{1,1}>\Delta_{0,0}=0\). Now, the algorithm finds the largest \(\Delta_{r,t_{j,r}}\), which is \(\Delta_{4,4}\). There is a freedom to choose that \(\Delta_{4,4}\) in phase 1 or in phase 2. We can see that in \(T_{2}\), we have \(t_{2,4}=5\). This means that the \(\Delta_{4,4}\) in phase 2 is chosen. According to the greedy algorithm again, we should choose the next largest \(\Delta_{r,t_{j,r}}\), which is \(\Delta_{4,4}\) in phase 1. However, we can see that \(t_{1,4}=4\) but \(t_{2,3}=4>3\). That is, in order to achieve an optimal solution, we need to choose \(\Delta_{3,3}\) in phase 2 instead of the larger \(\Delta_{4,4}\) in phase 1. In other words, we cannot group all \(\Delta_{\cdot,\cdot}\) among the phases altogether and then apply Algorithm 1 to obtain an optimal solution.