# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 3 Multi-Phase Adaptive Recoding
### Multi-Phase General Adaptive Recoding Problem (GAP)  
To formulate the optimization problem for multi-phase transmission, we first derive the probability mass functions of the innovative rank distributions. Let \(R_{i}\) be the random variable of the phase \(i\) innovative rank. In the following, we write \(\Pr(R_{i}=r_{i})\) as \(\Pr(r_{i})\) to simplify the notation. Note that \(R_{i+1}\) depends on the phase \(i\) innovative rank and the number of recoded packets \(t_{i,r_{i}}\) to be sent. When all \(t_{i,r_{i}}\) are given, \(R_{1}\to R_{2}\rightarrow\ldots\to R_{S}\) forms a Markov chain. Therefore, we have  
\[\Pr(r_{i})=\sum_{r_{1},r_{2},\ldots,r_{i-1}}\Pr(r_{1})\prod_{j=1}^{i-1}\Pr(r_ {j+1}\mid r_{j})=\sum_{r_{1},r_{2},\ldots,r_{i-1}}\Pr(r_{1})\prod_{j=1}^{i-1} \operatorname*{Bin}(t_{j,r_{j}},p,r_{j};r_{j}-r_{j+1}), \tag{2}\]  
where each index \(r_{1},r_{2},\ldots,r_{i-1}\) in the summation starts from \(0\) to \(M\).  
Recall that the principle of adaptive recoding is to maximize the average expected rank at the next node such that the average number of recoded packets per batch is \(t_{\text{avg}}\). The average number of recoded packets per batch can be obtained by  
\[\sum_{r_{1},r_{2},\ldots,r_{S}}\Pr(r_{1},r_{2},\ldots,r_{S})\sum_{i=1}^{S}t_{ i,r_{i}}=\sum_{i=1}^{S}\sum_{r_{i}}\Pr(r_{i})t_{i,r_{i}}.\]  
Note that the \(r_{i}\) in \(t_{i,r_{i}}\) is the index of the outer summation, which sums from \(0\) to \(M\). Let \(\bar{R}\) be the random variable of the rank of the batch at the next node after the current node completes the phase \(S\) transmission.  
**Theorem 1**.: \(\mathbb{E}[\bar{R}]=\sum_{i=1}^{S}\sum_{r_{i}}\Pr(r_{i})E(r_{i},t_{i,r_{i}}).\)__  
Proof.: The probability mass function of \(\bar{R}\) is  
\[\Pr(\bar{R}=k)=\sum_{r_{1},r_{S}}\Pr(r_{1},r_{S})\operatorname*{Bin}(t_{S,r_{ S}},p,r_{S};k-(r_{1}-r_{S})).\]  
Hence, \(\mathbb{E}[\bar{R}]\) equals  
\[\sum_{k=0}^{M}\sum_{r_{1},r_{S}}\Pr(r_{1},r_{S})\operatorname*{ Bin}(t_{S,r_{S}},p,r_{S};k-(r_{1}-r_{S}))k\] \[=\sum_{r_{1},r_{S}}\Pr(r_{1},r_{S})(r_{1}-r_{S}+E(r_{S},t_{S,r_{S }}))\] \[=\sum_{r_{1},r_{2},\ldots,r_{S}}\Pr(r_{1},r_{2},\ldots,r_{S})\sum_ {i=1}^{S-1}(r_{i}-r_{i+1})+\sum_{r_{S}}\Pr(r_{S})E(r_{S},t_{S,r_{S}})\] \[=\sum_{i=1}^{S-1}\sum_{r_{i}}\Pr(r_{i})\sum_{r_{i+1}}\operatorname* {Bin}(t_{i,r_{i}},p,r_{i};r_{i};r_{i}-r_{i+1})(r_{i}-r_{i+1})+\sum_{r_{S}}\Pr( r_{S})E(r_{S},t_{S,r_{S}})\] \[=\sum_{i=1}^{S}\sum_{r_{i}}\Pr(r_{i})E(r_{i},t_{i,r_{i}}).\qed\]  
Let \(T_{i}=(t_{i,r})_{r=0}^{M}\) and \(T=\bigcup_{i=1}^{S}T_{i}\). We first model an \(S\)-phase General Adaptive recoding Problem (GAP) that jointly optimizes all the phases:  
\[\max_{T} \sum_{i=1}^{S}\sum_{r_{i}}\Pr(r_{i})E(r_{i},t_{i,r_{i}})\] (3) s.t. \[\sum_{i=1}^{S}\sum_{r_{i}}\Pr(r_{i})t_{i,r_{i}}=t_{\text{avg}}.\]  
Any \(S\)-phase optimal solution is a feasible solution of the \(S^{\prime}\)-phase for \(S^{\prime}>S\); thus, increasing the phase would not give a worse throughput. In this model, it is not guaranteed that maximizing the outcomes of a phase would benefit the latter phases, i.e., it is unknown that whether a suboptimal phase would lead to a better overall objective. This dependency makes the problem challenging to solve.