# On Maximizing the Probability of Achieving Deadlines in Communication Networks
## Appendix A Proof of Convergence to a Stable Solution for DAP-CDFs
### Proof 1: Steady Progress  
Consider an approach based on induction using an integer index \(r\), whose initial value is zero and is incremented on each round after completing a CDF exchange by the broadcasting in line 11 of the AMPAD. For the proof, we denote the resulting CDF \(F_{u}\) by \(F^{r}_{u}\), which is initialized as \(F^{0}_{u}(\tau)=0\) (except for the sink, as noted). Similarly, we define  
\[F^{r}_{u\to v}(\tau):=f_{uv}(\tau)*F^{r-1}_{v}(\tau) \tag{1}\]for \(r\geq 1\) for representing the CDFs \(F_{u\to v_{l}}\) calculated at round \(r\) (AMPAD, line 13). It is to be noted, however, that index \(r\) is used exclusively for clarity of the proof, but the nodes themselves do not use it nor know it. Assume that all links exhibit a minimum link delay \(t_{\min}\) for any data packet transfer. Concretely, no link can transfer data packets with zero delay. This implies a delay \(t_{\min}\) below which all link PDFs are always equal to zero. Formally, by defining \(E\) as the set of all links in the network  
\[\forall uv\in E:\forall\tau<t_{\min}:f_{uv}(\tau)=0.\] (A2)  
then using \(r\), we define the stable region \(]-\infty,\hat{\tau}_{r}[\) for a CDF \(F_{u}^{r}(\tau)\) as follows:  
\[F_{u}^{r}(\tau)\text{ is stable for }\tau\in]-\infty,\hat{ \tau}_{r}[\] (A3) \[\iff \forall q>r,\forall\tau<\hat{\tau}_{r}:F_{u}^{q}(\tau)=F_{u}^{r}( \tau),\] (A4)  
where \(\hat{\tau}_{r}\) is a round-dependent variable whose initial value at \(r=0\) is \(\hat{\tau}_{0}=0\). The initial stable region of all CDFs is therefore, trivially, the set of negative real numbers. Next, we show that the stable region \(]-\infty,\hat{\tau}_{r}[\) of the CDFs \(F_{u}^{r}\) grows with \(r\) and is lower bounded by \(\hat{\tau}_{r}\geq rt_{\min}\). \(F_{u}^{r}(\tau)\) is stable for \(\tau\in]-\infty,rt_{\min}[\). Proof. : We will prove this lemma by induction. The induction basis for \(r=0\) is trivial to show. For the induction step, we will show now that \(F_{u}^{r+1}(\tau)\) is stable for \(\tau\in]-\infty,\hat{\tau}_{r}+t_{\min}[\) using the assumption that \(F_{v}^{r}(\tau)\) is stable for \(\tau\in]-\infty,\hat{\tau}_{r}[\). At the beginning of round \(r+1\), each node knows the CDFs \(F_{v}^{r}\) of all its neighbors from the previous round. This is also true in particular during the first calculation of lines 12-16 of the ADPAD when \(r=1\) and each node has just received the broadcast of the initial CDFs \(F_{u}^{0}(\tau)\). We first show that the CDF \(F_{u\to v_{l}}^{r+1}(\tau)\) for any neighbor \(v_{i}\) is stable for \(\tau\in]-\infty,\hat{\tau}_{r}+t_{\min}[\) under the given assumptions. The following sequence of equations starts by considering these values of \(\tau\) for \(F_{u\to v_{l}}^{r+1}(\tau)\):  
\[\forall\tau\in]-\infty,\hat{\tau}_{r}+t_{\min}[:F_{u\to v}^{r+1}(\tau)\] (A5) \[=f_{uv}(\tau)*F_{v}^{r}(\tau)\] (A6) \[=\int_{-\infty}^{\infty}f_{uv}(\tau-t)F_{v}^{r}(t)dt\] (A7) \[=\int_{-\infty}^{\hat{\tau}_{r}}f_{uv}(\tau-t)F_{v}^{r}(t)dt+ \int_{\hat{\tau}_{r}}^{\infty}f_{uv}(\tau-t)F_{v}^{r}(t)dt\] (A8) \[=\int_{-\infty}^{\hat{\tau}_{r}}f_{uv}(\tau-t)F_{v}^{r}(t)dt\] (A9)  
Equation (A6) is the definition of \(F_{u\to v}^{r+1}\) taken from Equation (A1). Equation (A7) is then the common definition of convolution. The second summand in Equation (A8) is equal to zero according to Equation (A2), which leads to Equation (A9). We now have to verify that all used values in the CDF are stable in Equation (A9). The considered values of \(t\) in \(F_{v}^{r}(t)\) are smaller than \(\hat{\tau}_{r}\) and are therefore stable by assumption. The link PDF \(f_{uv}(\tau)\) is always stable. The stability of Equation (A9) proves the stability of \(F_{u\to v}^{r+1}(\tau)\) for \(\tau\in]-\infty,\hat{\tau}_{r}+t_{\min}[\). For each neighbor of \(u\), the node \(u\) will update its own CDF \(F_{u}^{r+1}(\tau)\) (ADPAD line 16).