Expander Graphs. Next we show an analog of Theorem 1.7 in to the bounded error
rate setting.

######  Theorem 4.12.

[Mobile-Resilient Compilers for Expander Graphs] Assume $G$ is a
$\phi$-expander with minimum degree $k=\widetilde{\Omega}(1/\phi^{2})$. Then,
for any algorithm $\mathcal{A}$ that runs in $r$ CONGEST rounds, there is an
equivalent algorithm $\mathcal{A}^{\prime}$ which is resilient to round-error-
rate $f$, for $f=\widetilde{O}(k\phi^{2})$ that runs in
$\widetilde{O}(r/\phi)$ CONGEST rounds.

Let $c^{\prime\prime}$ be the constant of Lemma 3.12, and let
$f=\frac{k\phi^{2}}{c\log^{c^{\prime}}{n}}$ for sufficiently large constants
$c,c^{\prime}$, in particular with regards to $c^{\prime\prime}$. We assume
$\mathcal{A}$ is an $r$ round algorithm, and let $r^{\prime}$ be the round
complexity of an $r$ round algorithm compiled Theorem 4.1 against round-error
rate of at most $(4c^{\prime\prime}+2)f$. We slightly adapt the tree packing
algorithm used in Theorem 1.7, to have the part of computing the weak tree
packing to be resilient to many faults. This is done very simply by repeating
each round in this computation for $O(r^{\prime}\cdot\phi/\log{n})$ rounds,
and then running the algorithm of Theorem 4.1, such that it is resilient to
round-error rate of $(4c^{\prime\prime}+2)f$.

##### The Algorithm.

We define a padded-round as a round of communication where each node $u$ sends
to each neighbor $v$ a message $m(u,v)$ repeatedly for
$s=r^{\prime}\cdot\phi/\log{n}$ rounds. The received message of $v$ from $u$
is defined as the majority value seen by $v$ during these $s$ rounds, or $0$
if a majority does not exist. The following protocol is defined by a series of
padded rounds:

In the first padded-round, for every edge $(u,v)\in E$ with
$\mathrm{id}(u)>\mathrm{id}(v)$, let $u$ choose a color $c(u,v)$ sampled
uniformly at random in $[k]$ and send this color to $v$. Let $c(u,v)$ be the
received message of $u$ from $v$ in this padded-round. $u$ sets the color of
the edge $(u,v)$ to the received value $c(v,u)$. For every $i\in[k]$, define
the directed subgraph:

$G_{i}=\\{(u,v)~{}\mid~{}\mathrm{id}(u)>\mathrm{id}(v),c(u,v)=i\\}\cup\\{(v,u)~{}\mid~{}\mathrm{id}(u)>\mathrm{id}(v),c(v,u)=i\\}.$

Let $N_{i}(u)$ be the outgoing neighbors of $v$ in $G_{i}$. Each node $u$
proceeds to do the following padded-round BFS procedure in each $G_{i}$: Set a
variable $I_{i,0}(u)=\mathrm{id}(u)$ and $\mathrm{parent}_{i}(u)=\bot$ for
each color $i\in[k]$. For $\ell=1,\dots,z=4c^{\prime\prime}\log{n}/\phi$
padded-rounds, in parallel for all colors $[k]$, each node $u$ sends to each
(outgoing) neighbor $v\in N_{i}(u)$ the value $I_{i,\ell-1}(u)$. Let
$L_{i,\ell}$ be the set of messages $u$ receives from neighbors $\\{v\in
N(u)\mid c(u,v)=i\\}$. Each node $u$ sets
$I_{i,\ell}(u)=\max_{\mathrm{id}(v)\in
L_{i,\ell}\cup\\{\mathrm{id}(u)\\}}(\mathrm{id}(v))$, and if this value
strictly increases, then it sets $\mathrm{parent}_{i}(u)$ to be the neighbor
from which this value has arrived, oriented towards the other endpoint. In the
final padded-round, each node $u$ sends in parallel for each $i$ a message to
$\mathrm{parent}_{i}(u)$, to orient the edge $\mathrm{parent}_{i}(u)$ towards
itself. Each node that receives an edge orientation request, locally sets the
orientation of that edge towards itself.

##### Analysis

A color $i\in[k]$ is denoted as _good_ if the adversary did not control any
edge of $G_{i}$ for more than $s/2$ rounds during the tree computation phase.
Otherwise, the color $i$ is defined as _bad_.

In particular, in any good color, the adversary did not change the outcome of
any of the BFS procedures, and the guarantees of Lemmas 3.13 and 3.14 hold for
the altered algorithm and altered notion of good color, as formalized in the
following lemma:

######  Lemma 4.13.

For each good color $i\in[k]$, the output directed subgraph $G^{\prime}_{i}$
defined by $\\{\mathrm{parent}_{i}(u)\\}_{u\in V}$ is a directed spanning tree
of depth $4c^{\prime\prime}\log n/\phi$ oriented towards the node with the
largest ID in the network, $v_{r}=\mathrm{argmax}_{v}\mathrm{id}(v)$.

###### Proof.

For each good color $i\in[k]$, we have that $G_{i}=G[p]$ where each edge in
$G$ is sampled independently with probability
$p=1/k=O(\frac{\phi\log{n}}{f})$. Note that since the adversary does not
affect the padded-received message of any of the $G_{i}$ edges, all edges in
$G_{i}$ are bidirectional.

By Theorem 3.11 for $\alpha=\phi$, $\gamma=O(\frac{f}{\phi^{3}})$ such that
$p=\min\\{1,\ln n/(\alpha^{2}\gamma)\\}$, then w.h.p. a subgraph obtained by
sampling by taking each edge in $G$ with probability $p$ has conductance at
least $\phi/4$. By the union bound, all graphs $G_{i}$ have conductance
$\geq\phi/4$, w.h.p. Therefore, by Lemma 3.12 the graph $G_{i}$ has diameter
at most $4c^{\prime\prime}\cdot\log n/\phi$.

Since $i$ is good, the adversary did not control any of the edges of $G_{i}$
throughout the entire algorithm. Since
$v_{r}=\mathrm{argmax}_{v}\mathrm{id}(v)$, and all the message $v_{r}$
receives are real IDs of nodes, it never changes the value
$\mathrm{parent}_{i}(v_{r})=\bot$. Let $V_{i}(j)$ be nodes of distance $j$
from $v_{r}$ in $G_{i}$. Let $V_{i}(-1)=\\{\bot\\}$. We show by induction on
$j\geq 0$ that for any $u\in V_{i}(j)$, it holds that
$I_{i,j}(u)=\mathrm{id}(v_{r})$ and $\mathrm{parent}_{i}(u)\in V_{i}(j-1)$.
Clearly, $I_{i,0}(v_{r})=\mathrm{id}(v_{r})$ and as
$\mathrm{parent}_{i}(v_{r})=\bot$, the claim holds for $j=0$. Assume this is
the case for $j-1$. We note that
$V\setminus\left(\bigcup_{a=0}^{j-1}V_{a}\right)$ has not seen the value
$\mathrm{id}(v_{r})$ before round $j$, as they are of distance at least $j$
from $v_{r}$ in $G_{j}$. By induction, all $u\in V_{j-1}$ set
$I_{i,j-1}(u)=v_{r}$, therefore any node $u\in V_{j}$ receives a message from
a node $v\in V_{j-1}$ with the value $\mathrm{id}(v_{r})$ and sets its parent
to be in $V_{j-1}$. The induction holds and the claim follows. ∎

We conclude with the following claim:

######  Lemma 4.14.

The collection of subgraphs $\\{G^{\prime}_{i}\\}_{i\in[k]}$ is a _weak_
-$(k,\mathsf{D}_{\mathsf{TP}},\eta)$ Tree-Packing with
$\mathsf{D}_{\mathsf{TP}}=O(\log n/\phi)$ and $\eta=2$.

###### Proof.

The total number of corrupted messages is at most
$(4c^{\prime\prime}+2)r^{\prime}f$. For a color to be bad, there has to be at
least $r^{\prime}(\phi/\log{n})/2$ corrupted messages associated with it.
Since we assume $f=\widetilde{O}(k\phi^{2})=\widetilde{O}(r^{\prime}\phi)$,
there are at most
$\frac{(4c^{\prime\prime}+2)r^{\prime}f}{r^{\prime}(\phi/\log{n})/2}=\frac{(4c^{\prime\prime}+2)\cdot
f}{(\phi/\log{n})/2}\leq k/10$ bad colors, where the last inequality follows
from choosing large enough constants $c,c^{\prime}$ for $f$. Therefore, there
are at least $0.9k$ good colors. By Lemma 4.13, for every good color $i$, the
subgraph $G^{\prime}_{i}$ corresponds to a spanning tree of depth at most
$\mathsf{D}_{\mathsf{TP}}$ and rooted at $v_{r}$. Since each directed edge is
committed to a single color, we get that $\eta\leq 2$ (even among the bad
subgraphs). ∎

###### Proof of Theorem 4.12.

The round complexity of this procedure is at most
$(4c^{\prime\prime}+2)r^{\prime}$. By Lemma 4.14, the first phase of the
algorithm computes a weak-$(k,\mathsf{D}_{\mathsf{TP}},\eta)$ tree packing. In
the second phase, we run $\mathcal{A}$ compiled by 4.13 on round-error rate
$(4c^{\prime\prime}+2)f$. Since its round complexity of the second phase is
$r^{\prime}$ and since there are at most $(4c^{\prime\prime}+2)r^{\prime}f$
corrupted messages in total, we are guaranteed that the output is the same as
in $\mathcal{A}$. ∎

##  5 Mobile Resilience using Fault-Tolerant Cycle Covers

In this section we show a $f$-mobile-resilient algorithms. We use the same
techniques as in [60] for the unicast case, and extend this approach to obtain
a general compiler using cycle covers. We also note that this approach is also
a direct generalization of the approach of the compiler of [59] against a
$1$-mobile byzantine adversary.

######  Definition 8 (Low-Congestion FT Cycle-Covers).

For a given graph $G=(V,E)$, an $f$-FT
$(\mathrm{cong},\mathrm{dilation})$-Cycle Cover is a collection of
paths202020For our purposes, it is instructive to view it as a collection of
$f$ edge-disjoint paths, between each neighboring pair $u,v$. This is
equivalent to $(f-1)$ cycles covering the edge $(u,v)$.
$\mathcal{P}=\bigcup_{e\in E}\mathcal{P}(e)$ where each $\mathcal{P}(e=(u,v))$
consists of $k$ edge-disjoint $u$-$v$ paths, with the following properties:
(i) $\max_{P\in\mathcal{P}}|P|\leq\mathrm{dilation}$ and (ii) each $e\in E$
appears on at most $\mathrm{cong}$ paths in $\mathcal{P}$ (i.e.,
$\mathrm{load}(\mathcal{P})\leq\mathrm{cong}$).

######  Theorem 5.1 (Existence of Low-Congestion FT-Cycle Covers, [40]).

Every $f$-edge connected graph $G=(V,E)$ admits an $f$-FT
$(\mathrm{cong},\mathrm{dilation})$-Cycle Cover with
$\mathrm{cong},\mathrm{dilation}=D^{O(f)}\log(n)$. Moreover, in the fault-free
setting these cycles can be computed in $\mathrm{cong}+\mathrm{dilation}$
rounds.

For an $f$-FT cycle cover $\mathcal{P}$, we define the _path-conflict graph_
to be a graph $H=(E,E_{H})$ with a vertex $v_{e}$ for every edge $e\in E$, and
where $\\{v_{e_{1}},v_{e_{2}}\\}\in E_{H}$ if and only if there are paths
$P_{1}\in P(e_{1})$ and $P_{2}\in P(e_{2})$ that share at least one edge.

######  Lemma 5.2.

Let $\mathcal{P}$ be an $f$-FT $(\mathrm{cong},\mathrm{dilation})$-Cycle
Cover. There exists a coloring of the edges of $E$,
$\mathrm{Col}:E\rightarrow[f\cdot\mathrm{dilation}\cdot\mathrm{cong}+1]$, such
that for two distinct edges $e_{1},e_{2}\in E$, if
$\mathrm{Col}(e_{1})=\mathrm{Col}(e_{2})$, then any two paths $P_{1}\in
P(e_{1})$ and $P_{2}\in P(e_{2})$ are edge-disjoint.

###### Proof.

We note that in the _path-conflict graph_ $H$, the degree of each vertex
$v_{e}$ in $H$ is at most $f\cdot\mathrm{dilation}\cdot\mathrm{cong}$, since
for each $v_{e}$ there are $f$ paths of size at most $\mathrm{dilation}$, and
for each such edge $e$, there are at most $\mathrm{cong}$ other paths in
$\mathcal{P}$ containing $e$. Therefore, there exist a coloring $\mathrm{Col}$
of the vertices by $(f\cdot\mathrm{dilation}\cdot\mathrm{cong}+1)$ colors so
that no two adjacent vertices have the same color.

In the graph $G$, coloring each edge of $e\in E$ by the color
$\mathrm{Col}(v_{e})$, we obtain a coloring such that if two edges
$e_{1},e_{2}$ share the same color, then all paths $P(e_{1})$ and $P(e_{2})$
are edge disjoint. ∎

We call an edge coloring $\mathrm{Col}$ with the above properties of Lemma 5.2
good cycle coloring. We note that in a fault-free network, a good cycle
coloring can be computed for an $f$-FT
$(\mathrm{cong},\mathrm{dilation})$-Cycle Cover by simulating a
$(\Delta+1)$-coloring in the the _path-conflict graph_ $H$ (as defined in
Lemma 5.2). Next, we show that $G$ can simulate a round in $H$ using
$O(\mathrm{dilation}\cdot\mathrm{cong}^{2})$ rounds.

######  Lemma 5.3.

For a $\mathcal{P}$ be an $f$-FT $(\mathrm{cong},\mathrm{dilation})$-Cycle
Cover, a CONGEST-round of its _path-conflict graph_ can be simulated in
$O(\mathrm{dilation}\cdot\mathrm{cong}^{2})$ CONGEST-rounds in $G$ under a
fault-free assumption.

###### Proof.

In the first step, for each edge $(u,v)$, the vertex $u$ sends through all
paths $P(u,v)$ the identifier $\mathrm{id}(u)\circ\mathrm{id}(v)$. This can be
done in $O(\mathrm{dilation}\cdot\mathrm{cong})$ rounds, by a standard
pipelining argument. Following this step, the endpoints of each edge $e$ knows
entire list $W_{e}$ of edge identifiers $(u,v)$ such that $e\in P(u,v)$. In
the second step, each edge $e\in E$ sends back through each of these paths the
entire list $W_{e}$. Since for any $e$ the list $|W_{e}|\leq\mathrm{cong}$,
this can be done in $O(\mathrm{cong}^{2}\cdot\mathrm{dilation})$ rounds using
a standard pipelining argument. Given this, each node $u$ knows for each
incident edge $(u,v)$ the neighbors of $(u,v)$ in the _path-conflict graph_.
To simulate a CONGEST round in this graph, each node transmits in reverse the
communication it received in the second step, but for each edge identifier
$(u^{\prime},v^{\prime})$ it received, it also sends the message $(u,v)$ would
send to $(u^{\prime},v^{\prime})$ in the simulated CONGEST round on $H$. The
claim follows. ∎

######  Corollary 5.4.

For a $\mathcal{P}$ be an $f$-FT $(\mathrm{cong},\mathrm{dilation})$-Cycle
Cover, a good coloring can be found in
$\widetilde{O}(\mathrm{cong}^{2}\cdot\mathrm{dilation})$ rounds of $G$.

###### Proof.

By Lemma 5.3, we can simulate the deterministic $(\Delta+1)$-coloring
algorithm of [36], which runs in $\widetilde{O}(1)$ congest rounds. If a
vertex $v_{e}\in H$ is assigned the color $c(e)$, the edge $e$ colors itself
with $c(e)$. By definition of the _path-conflict graph_ , any edge pair
$e_{1},e_{2}$ share an edge if and only if their paths intersect. Therefore, a
vertex coloring on $H$ such that two adjacent vertices share the same color
implies a good coloring on the edges of $G$ w.r.t. the path cover
$\mathcal{P}$. ∎

######  Theorem 5.5 ($f$-Mobile Resilient Simulation via FT Cycle-Covers).

Assume that a $k$-FT $(\mathrm{cong},\mathrm{dilation})$-Cycle Cover is known
in a distributed manner, and a good cycle coloring is known for the edges, and
let $\mathcal{A}$ be an $r$-round algorithm in the fault-free setting. Then,
there is an equivalent $f$-mobile-resilient algorithm $\mathcal{A}^{\prime}$
with round complexity of $r^{\prime}$ for $f\leq k/c$ for a sufficiently large
constant $c$ and $r^{\prime}=\mathrm{dilation}\cdot\mathrm{cong}\cdot r$.

By combining Theorem 5.1 and 5.5, we obtain Theorem 1.4. The rest of the
section is devoted for proving Thm. 5.5.

##### Simulation of the $i^{th}$ Round of Alg $\mathcal{A}$.

Assume the network simulated rounds $1,\dots,i-1$, and each node $v$ is given
as input the some outgoing messages
$m_{i}(v,u_{1}),\dots,m_{i}(v,u_{\deg(v)})$ for every neighbor $u_{i}$, where
our goal is for every node $v$ to output
$m_{i}(u_{1},v),\dots,m_{i}(u_{\deg(v)},v)$.

The network runs the following protocol: For any $j\in[k]$, let
$E_{j}=\\{e\mid\mathrm{Col}(e)=j-1\\}$. The network performs
$j=1,\dots,f\cdot\mathrm{dilation}\cdot\mathrm{cong}+1$ iterations. In each
iteration, for $t=1,\dots,(2f\cdot\mathrm{dilation}+\mathrm{dilation}+1)$, in
parallel for each $(u,v)\in E_{j}$, node $u$ sends $m_{i}(u,v)$ repeatedly
over each path $P\in P(e)$, and whenever an edge in in $P(u,v)$ receives a
message, the receiving endpoint propagates it forward to the next edge in the
path. Let $m_{i}(u,v,\ell,t)$ be the message $v$ receives over the last edge
of $P_{\ell}$ exactly $t$ rounds after the start of iteration
$\mathrm{Col}(u,v)$. Let
$M_{i}(u,v)=\\{m_{i}(u,v,\ell,t)\medspace|\medspace\ell\leq
k\land\mathrm{dilation}\leq t\leq
2f\cdot\mathrm{dilation}+\mathrm{dilation}+1\\}$ be the multi-set of messages
$v$ receives between rounds $\mathsf{D}_{\mathsf{TP}}$ and
$2f\cdot\mathrm{dilation}+\mathrm{dilation}+1$. For each neighbor $u$, the
node $v$ outputs the majority value over $\mathsf{MAJ}(M_{i}(u,v))$.

######  Lemma 5.6.

Let $(u,v)\in E_{j}$. Then $\mathsf{MAJ}(M_{i}(u,v))=m_{i}(u,v)$.

###### Proof.

The number of rounds in iteration $j$ is
$t=2f\mathrm{dilation}+\mathrm{dilation}+1$. Therefore, there are at most
$(2f\mathrm{dilation}+\mathrm{dilation}+1)f$ faults. Let $L_{i}(u,v)$ be the
number of messages in $M_{i}$ that are not equal to $m_{i}(u,v)$. Since any
fault changes the value of at most one $m_{i}(u,v,\ell,t)\in M_{i}$, then
$L_{i}(u,v)\leq(2f\mathrm{dilation}+\mathrm{dilation}+1)f$. But the number of
$m_{i}(u,v,\ell,t)$ that $v$ receives is
$(2f\mathrm{dilation}+\mathrm{dilation}+1-\mathrm{dilation})\cdot
k=(2f\mathrm{dilation}+1)\cdot(2f+1)=2f(f\mathrm{dilation}+\mathrm{dilation}+1)+1\geq
2L_{i}(u,v)+1$. Therefore, at least $L_{i}(u,v)+1$ of the messages are equal
to $m_{i}(u,v)$, meaning $\mathsf{MAJ}(M_{i}(u,v))=m_{i}(u,v)$. ∎

Theorem 5.5 follows, since in each round $i$, and each pair of adjacent nodes
$u,v$, $v$ successfully receives $m_{i}(u,v)$.

## Acknowledgments

We are very grateful to Yanic Maus for his extremely valuable comments and
suggestions, and for the time and effort he invested in carefully reading our
paper. This project is funded by the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No. 949083), and by the Israeli Science Foundation (ISF), grant No.
2084/18.

## References

  * [1] Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish.  A trade-off between information and communication in broadcast protocols.  J. ACM, 37(2):238–256, 1990.
  * [2] Anindo Bagchi and S. Louis Hakimi.  Information dissemination in distributed systems with faulty units.  IEEE Transactions on Computers, 43(6):698–710, 1994.
  * [3] Joshua Baron, Karim El Defrawy, Joshua Lampkins, and Rafail Ostrovsky.  How to withstand mobile virus attacks, revisited.  In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014, pages 293–302. ACM, 2014.
  * [4] Zuzana Beerliová-Trubíniová and Martin Hirt.  Perfectly-secure MPC with linear communication complexity.  In Ran Canetti, editor, Theory of Cryptography, Fifth Theory of Cryptography Conference (TCC), volume 4948 of Lecture Notes in Computer Science, pages 213–230. Springer, 2008.
  * [5] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson.  Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract).  In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 1–10, 1988.
  * [6] Piotr Berman and Juan A. Garay.  Cloture votes: n/4-resilient distributed consensus in t+1 rounds.  Math. Syst. Theory, 26(1):3–19, 1993.
  * [7] Piotr Berman, Juan A. Garay, and Kenneth J. Perry.  Towards optimal distributed consensus (extended abstract).  In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 410–415. IEEE Computer Society, 1989.
  * [8] Douglas M Blough and Andrzej Pelc.  Optimal communication in networks with randomly distributed byzantine faults.  Networks, 23(8):691–701, 1993.
  * [9] François Bonnet, Xavier Défago, Thanh Dang Nguyen, and Maria Potop-Butucaru.  Tight bound on mobile byzantine agreement.  Theor. Comput. Sci., 609:361–373, 2016.
  * [10] Gabriel Bracha.  Asynchronous byzantine agreement protocols.  Information and Computation, 75(2):130–143, 1987.
  * [11] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  J. ACM, 32(4):824–840, 1985.
  * [12] Ran Canetti and Amir Herzberg.  Maintaining security in the presence of transient faults.  In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO ’94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, pages 425–438. Springer, 1994.
  * [13] Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler.  Making asynchronous distributed computations robust to channel noise.  In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 50:1–50:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [14] Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn.  Distributed connectivity decomposition.  In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014, pages 156–165. ACM, 2014.
  * [15] Keren Censor-Hillel and Tariq Toukan.  On fast and robust information spreading in the vertex-congest model.  Theoretical Computer Science, 2017.
  * [16] Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, and Roman Smolensky.  The bit extraction problem of t-resilient functions (preliminary version).  In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 396–407. IEEE Computer Society, 1985.
  * [17] Julia Chuzhoy, Merav Parter, and Zihan Tan.  On packing low-diameter spanning trees.  In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 33:1–33:18, 2020.
  * [18] Brian A. Coan and Jennifer L. Welch.  Modular construction of a byzantine agreement protocol with optimal message bit complexity.  Inf. Comput., 97(1):61–85, 1992.
  * [19] Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, and Alex Samorodnitsky.  On the round complexity of randomized byzantine agreement.  In 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, pages 12:1–12:17, 2019.
  * [20] Graham Cormode and Donatella Firmani.  A unifying framework for $l_{0}$-sampling algorithms.  Distributed Parallel Databases, 32(3):315–335, 2014.
  * [21] Danny Dolev.  The byzantine generals strike again.  J. Algorithms, 3(1):14–30, 1982.
  * [22] Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung.  Perfectly secure message transmission.  In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 36–45. IEEE Computer Society, 1990.
  * [23] Danny Dolev, Michael J. Fischer, Robert J. Fowler, Nancy A. Lynch, and H. Raymond Strong.  An efficient algorithm for byzantine agreement without authentication.  Information and Control, 52(3):257–274, 1982.
  * [24] Danny Dolev and Ezra N. Hoch.  Constant-space localized byzantine consensus.  In Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, pages 167–181, 2008\.
  * [25] Shlomi Dolev, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky, and Moti Yung.  Proactive secret sharing with a dishonest majority.  In Vassilis Zikas and Roberto De Prisco, editors, Security and Cryptography for Networks - 10th International Conference, SCN 2016, Amalfi, Italy, August 31 - September 2, 2016, Proceedings, volume 9841 of Lecture Notes in Computer Science, pages 529–548. Springer, 2016.
  * [26] Karim Eldefrawy, Rafail Ostrovsky, and Moti Yung.  Theoretical foundations for mobile target defense: Proactive secret sharing and secure multiparty computation.  In Pierangela Samarati, Indrajit Ray, and Indrakshi Ray, editors, From Database to Cyber Security - Essays Dedicated to Sushil Jajodia on the Occasion of His 70th Birthday, volume 11170 of Lecture Notes in Computer Science, pages 470–486. Springer, 2018.
  * [27] Pesech Feldman and Silvio Micali.  An optimal probabilistic protocol for synchronous byzantine agreement.  SIAM J. Comput., 26(4):873–933, 1997.
  * [28] Michael J Fischer.  The consensus problem in unreliable distributed systems (a brief survey).  In International Conference on Fundamentals of Computation Theory, pages 127–140. Springer, 1983.
  * [29] Mattias Fitzi and Ueli Maurer.  From partial consistency to global broadcast.  In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 494–503, 2000.
  * [30] Matthew K. Franklin, Zvi Galil, and Moti Yung.  Eavesdropping games: a graph-theoretic approach to privacy in distributed systems.  J. ACM, 47(2):225–243, 2000.
  * [31] Juan A. Garay.  Reaching (and maintaining) agreement in the presence of mobile faults (extended abstract).  In Gerard Tel and Paul M. B. Vitányi, editors, Distributed Algorithms, 8th International Workshop, WDAG ’94, Terschelling, The Netherlands, September 29 - October 1, 1994, Proceedings, volume 857 of Lecture Notes in Computer Science, pages 253–264. Springer, 1994.
  * [32] Juan A. Garay and Yoram Moses.  Fully polynomial byzantine agreement for _n_ > 3t processors in _t_ \+ 1 rounds.  SIAM J. Comput., 27(1):247–290, 1998.
  * [33] Ran Gelles.  Coding for interactive communication: A survey.  Found. Trends Theor. Comput. Sci., 13(1-2):1–157, 2017.
  * [34] Ran Gelles, Ankur Moitra, and Amit Sahai.  Efficient and explicit coding for interactive communication.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 768–777. IEEE Computer Society, 2011.
  * [35] Mohsen Ghaffari.  Distributed broadcast revisited: Towards universal optimality.  In Automata, Languages, and Programming - 42nd International Colloquium, (ICALP), volume 9135, pages 638–649. Springer, 2015.
  * [36] Mohsen Ghaffari and Fabian Kuhn.  Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1009–1020. IEEE, 2021.
  * [37] Oded Goldreich, Silvio Micali, and Avi Wigderson.  How to play any mental game or A completeness theorem for protocols with honest majority.  In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 218–229. ACM, 1987.
  * [38] Yael Hitron and Merav Parter.  Broadcast CONGEST algorithms against adversarial edges.  CoRR, abs/2004.06436, 2020.
  * [39] Yael Hitron and Merav Parter.  Broadcast CONGEST algorithms against adversarial edges.  In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 23:1–23:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [40] Yael Hitron and Merav Parter.  General CONGEST compilers against adversarial edges.  In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 24:1–24:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [41] Yael Hitron, Merav Parter, and Eylon Yogev.  Broadcast CONGEST algorithms against eavesdroppers.  In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 27:1–27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [42] Yael Hitron, Merav Parter, and Eylon Yogev.  Secure distributed network optimization against eavesdroppers.  In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, Cambridge, Massachusetts, USA, 2023.
  * [43] William M. Hoza and Leonard J. Schulman.  The adversarial noise threshold for distributed protocols.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 240–258. SIAM, 2016.
  * [44] Damien Imbs and Michel Raynal.  Simple and efficient reliable broadcast in the presence of byzantine processes.  arXiv preprint arXiv:1510.06882, 2015.
  * [45] Kamal Jain.  Security based on network topology against the wiretapping attack.  IEEE Wirel. Commun., 11(1):68–71, 2004.
  * [46] David R. Karger.  Random sampling in cut, flow, and network design problems.  In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 648–657. ACM, 1994.
  * [47] Jonathan Katz and Chiu-Yuen Koo.  On expected constant-round protocols for byzantine agreement.  In Annual International Cryptology Conference, pages 445–462. Springer, 2006.
  * [48] Muhammad Samir Khan, Syed Shalan Naqvi, and Nitin H. Vaidya.  Exact byzantine consensus on undirected graphs under local broadcast model.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 327–336, 2019.
  * [49] Chiu-Yuen Koo.  Broadcast in radio networks tolerating byzantine adversarial behavior.  In Soma Chaudhuri and Shay Kutten, editors, Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 275–282. ACM, 2004.
  * [50] Leslie Lamport, Robert E. Shostak, and Marshall C. Pease.  The byzantine generals problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982.
  * [51] Frank Thomson Leighton, Bruce M Maggs, and Satish B Rao.  Packet routing and job-shop scheduling ino (congestion+ dilation) steps.  Combinatorica, 14(2):167–186, 1994.
  * [52] Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg.  Minimum-weight spanning tree construction in _O_(log log _n_) communication rounds.  SIAM J. Comput., 35(1):120–131, 2005.
  * [53] Alexandre Maurer and Sébastien Tixeuil.  On byzantine broadcast in loosely connected networks.  In Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, pages 253–266, 2012\.
  * [54] CSJA Nash-Williams.  Edge-disjoint spanning trees of finite graphs.  Journal of the London Mathematical Society, 1(1):445–450, 1961\.
  * [55] Rafail Ostrovsky and Moti Yung.  How to withstand mobile virus attacks (extended abstract).  In Luigi Logrippo, editor, Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 19-21, 1991, pages 51–59. ACM, 1991.
  * [56] Merav Parter.  Small cuts and connectivity certificates: A fault tolerant approach.  In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [57] Merav Parter and Eylon Yogev.  Distributed algorithms made secure: A graph theoretic approach.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1693–1710. SIAM, 2019.
  * [58] Merav Parter and Eylon Yogev.  Low congestion cycle covers and their applications.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1673–1692, 2019.
  * [59] Merav Parter and Eylon Yogev.  Secure distributed computing made (nearly) optimal.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 107–116, 2019.
  * [60] Arpita Patra, Ashish Choudhary, C. Pandu Rangan, Kannan Srinathan, and Prasad Raghavendra.  Perfectly reliable and secure message transmission tolerating mobile adversary.  Int. J. Appl. Cryptogr., 1(3):200–224, 2009.
  * [61] Marshall Pease, Robert Shostak, and Leslie Lamport.  Reaching agreement in the presence of faults.  Journal of the ACM (JACM), 27(2):228–234, 1980.
  * [62] Andrzej Pelc.  Reliable communication in networks with byzantine link failures.  Networks, 22(5):441–459, 1992.
  * [63] Andrzej Pelc and David Peleg.  Broadcasting with locally bounded byzantine faults.  Inf. Process. Lett., 93(3):109–115, 2005.
  * [64] David Peleg.  Distributed Computing: A Locality-sensitive Approach.  SIAM, 2000.
  * [65] Sridhar Rajagopalan and Leonard J. Schulman.  A coding theorem for distributed computation.  In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 790–799. ACM, 1994.
  * [66] Irving S. Reed and Gustave Solomon.  Polynomial codes over certain finite fields.  Journal of the Society for Industrial and Applied Mathematics (SIAM), 8(2):300 – 304, 1960.
  * [67] Nicola Santoro and Peter Widmayer.  Time is not a healer.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 304–313. Springer, 1989.
  * [68] Nicola Santoro and Peter Widmayer.  Distributed function evaluation in the presence of transmission faults.  In Algorithms, International Symposium SIGAL ’90, Tokyo, Japan, August 16-18, 1990, Proceedings, pages 358–367, 1990.
  * [69] Leonard J. Schulman.  Communication on noisy channels: A coding theorem for computation.  In 33rd Annual Symposium on Foundations of Computer Science (FOCS), pages 724–733. IEEE Computer Society, 1992.
  * [70] Daniel A. Spielman.  Lecture notes in spectral graph theory, November 2009.
  * [71] Kannan Srinathan, Prasad Raghavendra, and C. Pandu Rangan.  On proactive perfectly secure message transmission.  In Information Security and Privacy, 12th Australasian Conference, ACISP, volume 4586 of Lecture Notes in Computer Science, pages 461–473. Springer, 2007.
  * [72] Sam Toueg, Kenneth J Perry, and TK Srikanth.  Fast distributed agreement.  SIAM Journal on Computing, 16(3):445–457, 1987.
  * [73] Salil P. Vadhan.  Pseudorandomness.  Foundations and Trends in Theoretical Computer Science, 7(1-3):1–336, 2012.
  * [74] Christian Wulff-Nilsen.  Fully-dynamic minimum spanning forest with improved worst-case update time.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1130–1143, 2017.
  * [75] Andrew Chi-Chih Yao.  How to generate and exchange secrets (extended abstract).  In FOCS, 1986.
  * [76] Moti Yung.  The ”mobile adversary” paradigm in distributed computation and systems.  In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 171–172. ACM, 2015.

##  Appendix A Translation of Fault-Free Algorithms into $f$-Mobile-Secure
Algorithms

In this section we prove Theorem 1.3 by presenting a simulation result that
translates any low-congestion (fault-free) algorithm $\mathcal{A}$ into an
equivalent $f$-mobile-secure algorithm $\mathcal{A}$. The connectivity
requirements and the round overhead match those obtained by [42] for the
$f$-_static_ setting. The additional benefit of our compiler is that in
contrast to [42], it provides perfect, rather than statistical, security
guarantees. Similarly to [42], the key task is in exchanging
$\widetilde{O}(f\cdot\mathrm{cong})$ secrets to all nodes in the graph, that
are hidden from the adversary. This calls for providing $f$-mobile-secure
algorithms for unicast and broadcast task. In Subsec. A.1, we describe the
adaptation of secure unicast to the mobile setting. Subsec. A.2 describes the
modified $f$-mobile-secure broadcast algorithm. Finally, Subsec. A.3 presents
the final $f$-mobile compiler, with prefect-security guarantees.

Throughout, we use the following lemma, which follows by Theorem 2.1.

######  Lemma A.1.

Let $t,r,f$ be input integers. Then, there is an $r+t$ round procedure that
allows each neighbors pair $u,v$ to output a list $\mathcal{K}(u,v)$ of $r$
many $B$-bit words for $B=O(\log n)$ such that the following holds: the
$f$-mobile adversary learns nothing, on all but the $\mathcal{K}(u,v)$ sets of
at most $f^{\prime}$ edges, where
$f^{\prime}=\lfloor(f\cdot(t+1))/(r+t)\rfloor$. Moreover, for $t\geq 2fr$, it
holds that $f^{\prime}=f$.

###### Proof.

Let each neighboring pair $u,v$ exchange $r+t$ random messages
$\mathcal{R}(u,v)=\\{R_{1}(u,v),\ldots,R_{r+t}(u,v)\\}$. Each $u,v$ apply the
algorithm of Thm. 2.1 with $n=r+t$ and $k=O(\log n)$ to compute the set
$\mathcal{K}(u,v)$ of $r$ words of length $B=O(\log n)$. An edge $(u,v)$ is
good if the adversary eavesdrops the edge, during this $r+t$ round procedure,
for at most $t$ rounds. Otherwise, the edge is bad. By Theorem 2.1, it holds
that the adversary learns nothing on the $\mathcal{K}(u,v)$ set of a good
edge. Since the adversary controls at most $f$ edges in each round, it
eavesdrops over at most $f(r+t)$ edges. By averaging, there are at most
$\lfloor f(r+t)/(t+1)\rfloor$ bad edges. ∎

###  A.1 Secure Unicast with Mobile Adversaries

In the static-secure unicast problem, a given source node $s$ is required to
send a (secret) message $m^{*}$ to a designated target $t$, while leaking no
information to an eavesdropper adversary controlling a fixed (i.e, static)
subset of edges $F\subseteq G$ in the graph. Recently, [41] observed that the
secure network coding algorithm of Jain [45] to the problem can be implemented
in an optimal number of CONGEST rounds and with minimal congestion.

######  Theorem A.2 ((Static) Secure-Unicast, [41, 45]).

Given a $D$–diameter graph $G$, there is an $O(D)$-round $1$-congestion
algorithm $\mathsf{StaticSecureUnicast}$ that allows a sender $s$ to send a
message $m^{*}$ to a target $t$, while leaking no information to an
eavesdropper adversary controlling $F^{*}$ edges in the graph, provided that
$s$ and $t$ are connected in $G\setminus F^{*}$.

We start by observing that Jain’s unicast algorithm, upon slight
modifications, can become secure against mobile eavesdropper adversary,
provided that the set of edges $F_{i}$ controlled by the adversary in round
$i$ does not disconnect the graph. In fact, our requirements on the
$\\{F_{i}\\}$ sets can be relaxed even further. We show the following which
matches the known bounds for the static setting.

######  Lemma A.3 (Mobile Secure-(Multi) Unicast).

Given a $D$–diameter graph $G$, there is an $O(D)$-round $2$-congestion
algorithm $\mathsf{MobileSecureUnicast}$ that allows a sender $s$ to send a
message $m^{*}$ to a target $t$, while leaking no information to a mobile
eavesdropper adversary controlling distinct set of edges $F_{i}$ in every
round $i$ of the algorithm, provided that $s$ and $t$ are connected in
$G\setminus F_{1}$ (where possible $F_{i}=E(G)$ for every $i\geq 2$).
Moreover, there is an algorithm $\mathsf{MobileSecureMulticast}$ which can
solve $R$ secure unicast instances $(s_{j},t_{j},m_{j})$ in parallel using
$O(D+R)$ rounds. The security holds provided that each pair $s_{j}$ and
$t_{j}$ are connected in $G\setminus F_{j}$, for every $j\in\\{1,\ldots,R\\}$.

Mobile-Secure-Unicast Alg. $\mathsf{MobileSecureUnicast}$. The algorithm
starts with a preliminary round in which nodes exchange random $O(\log n)$-bit
messages $K(u,v)\in\mathbb{F}_{q}$ over all graph edges $(u,v)\in E$, for a
prime $q\in\operatorname{poly}(n)$. These messages are next used as OTP keys
for encrypting the messages of Alg. $\mathsf{StaticSecureUnicast}$ applied
with the input $s,t$ and the secret message $m^{*}$. For every $(u,v)\in E$,
letting $m_{i}(u,v)$ be a non-empty message sent from $u$ to $v$ in round $i$
of Alg. $\mathsf{StaticSecureUnicast}$, then in corresponding round $i$ of
Alg. $\mathsf{MobileSecureUnicast}$ (i.e., round $i+1$) $u$ sends $v$ the
message $m_{i}(u,v)+K(u,v)$. The correctness follows immediately and it
remains to prove security.

######  Claim 3.

Let $F^{*}$ be the set of edges controlled by the adversary in the first round
of Alg. $\mathsf{MobileSecureUnicast}$. Then, provided that $s$ and $t$ are
connected in $G\setminus F^{*}$, the adversary learns nothing on the secret
message $m^{*}$. This holds even if the adversary controls all the edges in
the graph in every round $i\geq 2$.

###### Proof.

The security uses the fact that Jain’s unicast algorithm of Lemma A.2 sends
exactly one message on each edge $(u,v)$ (in exactly one direction, either
from $u$ to $v$ or vice-versa). For a subset of edges $E^{\prime}\subseteq E$,
let $\mathcal{K}(E^{\prime})=\\{K(u,v)\\}_{(u,v)\in E^{\prime}}$.

First observe that the security is immediate, by the OTP guarantees, if all
keys in $\mathcal{K}(E)$ are hidden from the adversary. This holds as every
key $K(u,v)$ is used exactly once, as we send at most one message from $u$ to
$v$ throughout the entire algorithm. Since the adversary controls only the
edges $F^{*}$ in the first round, it fully knows $\mathcal{K}(F^{*})$, and has
_no_ information on all the remaining keys $\mathcal{K}(E\setminus F^{*})$

Consider the worst case scenario where the adversary controls all edges in $G$
in every round $i\geq 1$ when simulating Alg. $\mathsf{MobileSecureUnicast}$.
Since the adversary knows the keys $\mathcal{K}(F^{*})$, it knows all the
messages sent throughout the edges of $F^{*}$ in Jain’s algorithm. All
remaining messages sent through edges in $E\setminus F^{*}$ are distributed
uniformly at random (by the OTP security). Therefore, the view obtained by the
mobile adversary in this case is equivalent to the view obtained by a static
adversary controlling $F^{*}$. The security follows by Lemma A.2. ∎

###### Proof of Lemma A.3.

By Claim Claim 3, it remains to handle the multi-unicast problem, where the
instance consists of $R$ triplets $\\{(s_{i},t_{i},m_{i}\\}_{i=1}^{R}$. Alg.
$\mathsf{MobileSecureMulticast}$ starts with a phase of $R$ rounds in which
random messages are exchanged over all graph edges. For every $(u,v)\in E$,
denote these messages as a list of $R$ keys: $K_{1}(u,v),\ldots,K_{R}(u,v)$.
For a subset of edges $E^{\prime}$, let
$\mathcal{K}_{i}(E^{\prime})=\\{K_{i}(u,v)\\}_{(u,v)\in E^{\prime}}$. For
every $i\in\\{1,\ldots,R\\}$, let $\mathcal{A}_{i}$ denote that application of
Alg. $\mathsf{StaticSecureUnicast}$ with input $(s_{i},t_{i},m_{i})$ in which
messages are encrypted (and decrypted) with the keys of $\mathcal{K}_{i}(E)$.
The algorithm runs all $R$ algorithms $\\{\mathcal{A}_{i}\\}$ in parallel.
Using the standard random delay approach of Theorem 1.9, this can be done
within $\widetilde{O}(D+R)$ rounds. This completes the description of the
algorithm.

The correctness is immediate and we consider security in the worst case
setting where that adversary controls all edges in round $i\geq R+1$. That is,
$F_{i}=E$ for every $i\geq R+1$. In the random delay approach, each of the $R$
algorithms proceed at a speed of phases, each consisting of $O(\log n)$
rounds. We note that such a scheduling might be risky in the general secure-
mobile setting, as a single round is now simulated in $\ell=O(\log n)$ rounds
which allows the adversary to control $f\cdot\ell$ faults rather than $f$
faults (when the algorithm runs in isolation). This concern does not appear in
the context of Jain’s algorithm due to the fact that it has congestion of
exactly $1$. For the reason, we can assume (as in Claim 3), that the adversary
controls all edges in rounds $i\geq R+1$ and consequently the fact that a
round is now completed within $O(\log n)$ rounds cannot further increase the
power of the adversary.

Specifically, for every algorithm $\mathcal{A}_{i}$ the adversary knows all
keys of $\mathcal{K}_{i}(F_{i})$ and it knows nothing on the keys
$\mathcal{K}_{i}(E\setminus F_{i})$. Since there is at most one message of
$\mathcal{A}_{i}$ on each edge, the adversary learns nothing on the messages
exchanged over $E\setminus F_{i}$ and fully knows the messages exchanged over
$F_{i}$. Consequently, the view of the adversary in the simulation of
$\mathcal{A}_{i}$ is analogous to the view of the static adversary controlling
the edges in $F_{i}$. The security then holds by the security guarantees of
Alg. $\mathsf{StaticSecureUnicast}$ (Lemma A.2). ∎

###  A.2 $f$-Mobile-Secure Broadcast

We next show that the $f$-static secure broadcast algorithm of [41] can be
slightly modified to provide $f$-mobile security with the same round
complexity.

######  Theorem A.4 ($f$-Mobile-Secure Broadcast).

For every $(2f+3)(1+o(1))$ edge-connected $n$-vertex $D$-diameter graph $G$,
there exists a randomized $f$-mobile-secure broadcast algorithm
$\mathsf{MobileBroadcast}$ for sending w.h.p a $b$-bit message $m^{*}$ that
runs in $\widetilde{O}(D+\sqrt{f\cdot b\cdot n}+b)$ rounds. The edge
congestion of the algorithm is $\widetilde{O}(\sqrt{f\cdot b\cdot n}+b)$.

This matches the bounds provided by [41] for the $f$-static-secure setting. We
first provide a quick high-level description of the static-secure algorithm of
[41] and then highlight the required modifications. For the sake of clarity,
we provide a simplified description assuming that all nodes know the network
topology.

As in the $f$-static setting of [41], our $f$-mobile-secure algorithm is also
based on the distributed computation of a tree collection denoted as
_fractional tree packing_ [14].

######  Definition 9 (Fractional Tree Packing).

A _fractional tree-packing_ of a graph $G$ is a collection of spanning trees
$\mathcal{T}$, and a weight function $w:\mathcal{T}\rightarrow(0,1]$, such
that for every edge $e\in E$, $\sum_{T_{i}\in\mathcal{T}:e\in
T_{i}}w(T_{i})\leq 1$. The size of the fractional tree packing $\mathcal{T}$
is denoted by $\chi(\mathcal{T})=\sum_{T_{i}\in\mathcal{T}}w(T_{i})$.

We use the distributed computation of fractional tree packing, due to Censor-
Hillel, Ghaffari, and Kuhn [14], slightly adapted to our setting by [41].

######  Lemma A.5 (A slight adaptation of Theorem 1.3 [14]).

Given a $D$-diameter $\lambda$ edge-connected $n$-node graph, and an integer
parameter $\lambda^{\prime}\leq\frac{\lambda-1}{2}(1-o(1))$, one can compute a
fractional tree packing $\mathcal{T}$ and a weight function
$w:\mathcal{T}\rightarrow(0,1]$, such that:

  1. 1.

for every $T_{i}\in\mathcal{T}$,
$w(T_{i})=\frac{n_{i}}{\lceil\log^{8}n\rceil}$ for some positive integer
$n_{i}\geq 1$,

  2. 2.

$\chi(\mathcal{T})\in[\lambda^{\prime},\lambda^{\prime}(1+o(1))]$,

  3. 3.

the round complexity of the algorithm is
$\widetilde{O}(D+\sqrt{\lambda^{\prime}\cdot n})$ and the edge-congestion is
$\widetilde{O}(\sqrt{\lambda^{\prime}\cdot n})$.

We are now ready to provide the complete description of Alg.
$\mathsf{MobileBroadcast}$ given a source $s$ holding a broadcast message
$m^{*}$ of $b$-bits (where possibly $b=\Omega(\log n)$).

##### Step (0): Fractional Tree Decomposition and Landmarks Selection.

Apply the fractional tree-packing algorithm of Lemma A.5 with
$\lambda^{\prime}=f+1$. Denote the output tree packing by $\mathcal{T}$ and
its size by $\chi(\mathcal{T})$. By the end of this computation, all nodes
also know the weights $n_{1},\ldots,n_{|\mathcal{T}|}$ of the trees in
$\mathcal{T}$ (see Lemma A.5(1)). Decompose each tree $T_{i}\in\mathcal{T}$
into fragments $T_{i,j}$ of size $s=\Theta(\min\\{\sqrt{f\cdot b\cdot
n},n\\})$ (as in [42]). Let $L\subseteq V$ be a subset of nodes, denoted as
_landmarks_ , obtained by sampling each node with probability $p=\Theta(\log
n/s)$. The identities of the sampled nodes $L$ are broadcast to all the nodes
in $O(D+|L|)$ rounds. For every fragment $T_{i,j}$, let $\ell_{i,j}$ be some
chosen node in $L\cap V(T_{i,j})$, denoted as the _leader_ of the fragment,
which exists with high probability. This leader can be chosen in $O(s)$ rounds
by a simple convergecast over each fragment, simultaneously. This entire step
can be done in a non-secure manner, as it does not leak any information on the
broadcast message, $m^{*}$.

Step (1): Secure Secret Transmission to Landmarks. The source node $s$ secret
shares its $b$-bit broadcast message $m^{*}$ into

$\widehat{f}=\chi(\mathcal{T})\cdot\lceil\log^{8}n\rceil\mbox{~{}~{}shares},$
(12)

denoted as $M^{*}=(m_{1},\ldots,m_{\widehat{f}})$, where each share $m_{i}$
has $b$ bits. Note that by Lemma A.5(1), $\widehat{f}$ is an integer. Then
algorithm then applies Alg. $\mathsf{MobileSecureMulticast}$ of Lemma A.3 to
securely send the landmarks $L$ the collection of all $\widehat{f}$ shares.

Step (2): Local Secret Exchange. The step consists of $r=3f\cdot
b\cdot\lceil\log^{8}n\rceil$ rounds, in each round, random $O(\log n)$-bit
messages $R_{j}(u,v)$ are exchanged over all edges $(u,v)\in G$. At the end of
this step, each neighboring pair $u,v$ locally apply the algorithm of Theorem
2.1 to compute a collection of $r^{\prime}=b\cdot\lceil\log^{8}n\rceil$ secret
keys $\mathcal{K}(u,v)=\\{K_{j}(u,v)\\}_{j=1}^{r^{\prime}}$. In the analysis,
we show that the adversary knows nothing on the $\mathcal{K}(u,v)$ sets of all
but $f$ many (undirected) edges. The third step, described next, is simulated
exactly as in the static-secure algorithm of [41], with the only distinction
that the messages are OTP encrypted with the keys of $\mathcal{K}(u,v)$.

Step (3): Shares Exchange in each Fragment. Recall that by Lemma A.5(1),
$w(T_{i})=\frac{n_{i}}{\lceil\log^{8}n\rceil}$ for some positive integer
$n_{i}\geq 1$ for every tree $T_{i}\in\mathcal{T}$. Our goal is to propagate a
distinct collection of $n_{i}$ shares in $M^{*}$ over each tree $T_{i}$. To do
that, the landmark nodes partition locally and canonically the shares of
$M^{*}$ into disjoint subsets $M^{*}_{1},\ldots,M^{*}_{k}$ such that
$|M^{*}_{i}|=n_{i}$ for every $i\in\\{1,\ldots,k=|\mathcal{T}|\\}$. Note that
by Equation 12, $\sum_{T_{i}\in\mathcal{T}}n_{i}=\widehat{f}$. The leader
$\ell_{i,j}$ of each fragment $T_{i,j}$ sends all the shares in $M^{*}_{i}$
over its fragment, as follows. Every edge $(u,v)$ encrypts its $j^{th}$
message using the key $K_{j}(u,v)\in\mathcal{K}(u,v)$, for every
$j\in\\{1,\ldots,r^{\prime}\\}$. We show in the analysis, that each edge is
required to send at most $r^{\prime}$ messages and therefore it indeed has
sufficiently many keys in $\mathcal{K}(u,v)$. Finally, each node $v$ recovers
the $b$-bit broadcast message, by setting $m^{*}=\oplus_{i=1}^{k}\oplus_{m\in
M^{*}_{i}}m~{}.$ This completes the description of the algorithm.

Analysis. The correctness is immediate by the $f$-static-secure description of
[41], noting that each node indeed receives all needed shares, w.h.p., to
recover the broadcast message $m^{*}$. We now turn to address the round
complexity and congestion analysis. In Step (0) the computation of the
fractional tree packing can be done in $\widetilde{O}(D+\sqrt{f\cdot n})$
rounds by Lemma A.5(3) with $\lambda^{\prime}=f+1$. By [41], the fragmentation
of the trees takes $s=\widetilde{O}(\min\\{\sqrt{f\cdot b\cdot n},n\\})$
rounds. Picking the leader of each fragment takes $O(s)$ rounds, as well.

Step (1) takes $\widetilde{O}(D+f\cdot b\cdot|L|)$ rounds, by Lemma A.3.
Since, w.h.p., $|L|=\widetilde{O}(\sqrt{n/(f\cdot b)})$, it takes
$\widetilde{O}(D+\sqrt{f\cdot b\cdot n})$ rounds. As for Step (3), since
$w(T_{i})\leq 1$, it holds that $n_{i}\leq\lceil\log^{8}n\rceil$ for every
$T_{i}\in\mathcal{T}$. Therefore, Step (3) propagates $r^{\prime}$-bit
messages, for $r^{\prime}=b\cdot\lceil\log^{8}n\rceil$, over the edge-disjoint
fragments of size $O(s)$. This can be done in
$\widetilde{\Theta}(b+\sqrt{f\cdot b\cdot n})$ rounds via standard pipeline.
Note that edge congestion of this step is bounded by $r^{\prime}$, and that
the edge congestion in the entire algorithm is bounded by
$\widetilde{O}(b+\sqrt{f\cdot b\cdot n})$.

Security. It remains to show that the algorithm is $f$-mobile-secure. Recall
that the eavesdropper is assumed to know $G$, therefore Step (0) can be
implemented in a non-secure manner. Step (1) is $f$-mobile-secure by Lemma
A.3.

We turn to consider Step (3) in which the shares in $M^{*}$ are sent over the
tree fragments of $\mathcal{T}$. By the above, Step (3) sends at most
$r^{\prime}$ messages along each edge and therefore the number of keys in
$\mathcal{K}(u,v)$ is sufficient. By Lemma A.1, we get that the adversary
knows nothing on the keys in $\mathcal{K}(u,v)$ of all but $F^{*}\subseteq G$
edges, where $|F^{*}|\leq f$. Consequently, the adversary learns nothing from
the messages exchanged over the edges in $E\setminus F^{*}$ during this step.
We next show that there exists at least one share in $M^{*}$ that the
eavesdropper did not learn, and therefore it knows nothing on $m^{*}$. Since
the tree fragments of each $T_{i}\in\mathcal{T}$ are edge-disjoint, the number
of shares in $M^{*}$ sent over an edge $e$ is bounded by:

$\sum_{e\in T_{i}}|M^{*}_{i}|=\sum_{e\in
T_{i}}n_{i}\leq\lceil\log^{8}n\rceil~{},$

where the last inequality follows by the fractional tree packing guarantee
that $\sum_{e\in T_{i}}w(T_{i})\leq 1$, and using the fact that
$w(T_{i})=\frac{n_{i}}{\lceil\log^{8}n\rceil}$ for every
$T_{i}\in\mathcal{T}$. Therefore, the number of shares exchanged over the
edges in $F^{*}$ and possibly observed by the eavesdropper can be bounded by:

$|F^{*}|\cdot\lceil\log^{8}n\rceil<\chi(\mathcal{T})\cdot\lceil\log^{8}n\rceil=\widehat{f}=|M^{*}|~{},$

where the first inequality is by Lemma A.5(2) (with $\lambda^{\prime}=f+1$),
and the last equality follows by Equation 12.

###  A.3 Congestion-Sensitive Compiler with $f$-Mobile Security

We are now ready to describe our $f$-mobile compilers. While the round
overhead of our compiler match those obtained by [42] they differ from it in
two major points. First, our compilers provide $f$-mobile rather than
$f$-static security; The compiler consists of the following three steps:

Step 1: Local Secret Exchange. Step 1 consists of $\ell=\Theta(r)$ rounds in
which all neighboring pairs exchange random field elements
$R_{j}(u,v)\in\mathbb{F}_{q}$ for every $j\in\\{1,\ldots,\ell\\}$. Using
Theorem 2.1, at the end of this phase, each pair $(u,v)\in E$ holds $r$ keys
$\\{K_{i}(u,v)\\}_{i=1}^{r}$ such that the adversary learns nothing on the
keys of all but at most $4f$ _bad_ edges212121I.e., corresponding to the edges
occupied by the adversary for at least $t+1=\Theta(r)$ rounds in that phase..

Step 2: Global Secret Exchange. The second step shares a collection of
$b=O(f\cdot\mathrm{cong}\cdot\log n)$ random bits, denoted as
$R\in\\{0,1\\}^{b}$, to the entire network, while guaranteeing that the
adversary learns nothing on $R$. This is done by applying our $f$-mobile-
secure broadcast algorithm $\mathsf{MobileBroadcast}$ of Theorem A.4. Let
$\mathcal{H}=\\{h:\\{0,1\\}^{p}\rightarrow\\{0,1\\}^{q}\\}$ be a family of
$c$-wise independent hash functions for $c=4f\cdot\mathrm{cong}$ and
$p,q=O(\log n)$ (see Lemma 1.11). At the end of this step, all nodes use $R$
to choose random function $h^{*}\in\mathcal{H}$.

Step 3: Round-by-Round Simulation of Alg. $\mathcal{A}$. For every
$i\in\\{1,\ldots,r\\}$, let $m_{i}(u,v)$ be the message sent from $u$ to $v$
in round $i$ of (the fault-free) Alg. $\mathcal{A}$. We assume, w.l.o.g., that
all the messages $\\{m_{i}(u,v)\\}_{(u,v)\in E,i\in\\{1,\ldots,r\\}}$ are
_distinct_. This can be easily done222222I.e., assuming that the bandwidth of
the CONGEST model is $c\log n$ for some constant $c$. Otherwise, we can
simulate each round using a constant number of rounds. by appending to each
message $m_{i}(u,v)$ the round-number and the edge-ID. As Algorithm
$\mathcal{A}$ has bounded congestion, some of these $m_{i}(u,v)$ messages are
empty, however, the compiled algorithm must still exchange messages on all
edges in every round. We let every vertex $u$ act differently according to
whether $m_{i}(u,v)$ is empty, but in a way that is indistinguishable to the
adversary. If $m_{i}(u,v)$ is _not_ empty, then $u$ pads the message
$m_{i}(u,v)$ with $0$’s of length $B^{\prime}$, by letting $m=m_{i}(u,v)\circ
0^{B^{\prime}-B}$ and sending the message
$\widehat{m}_{i}(u,v)=h^{*}(m)+K_{i}(u,v)$ to $v$. Otherwise, if $m_{i}(u,v)$
is empty, then $u$ simply sends a uniformly random string length $B^{\prime}$.

While the adversary will not be able to distinguish between real messages and
random messages, the receiver $v$ will indeed be able to distinguish between
the two, by applying following decoding procedure for each received message
$\widehat{m}_{i}(u,v)$: Iterate over all possible messages of length $O(\log
n)$ and let $m^{\prime}_{i}(u,v)$ be the first (lexicographically) message $m$
satisfying that $h^{*}(m)=\widehat{m}_{i}(u,v)+K_{i}(u,v)$. Note that all
nodes, and in particular, $v$, know $h^{*}$. If $m^{\prime}_{i}(u,v)$ ends
with $B^{\prime}-B$ 0’s, then $v$ knows that the message was not empty, w.h.p,
and thus sets the final message $\widehat{m}_{i}(u,v)$ to be the first $B$
bits of $m^{\prime}_{i}(u,v)$. Otherwise, $v$ knows that a random string was
sent, and thus sets $\widehat{m}_{i}(u,v)$ to be an empty message. The summary
of this protocol is given below.

$f$-Mobile Secure Simulation of Alg. $\mathcal{A}$: Step (1): Local Secret
Exchange. 1. Exchange $\ell=\Theta(r)$ random messages over all edges
$(u,v)\in E$. 2. Each node $u,v$ locally applies Theorem 2.1 to compute $r$
keys $\mathcal{K}(u,v)=\\{K_{i}(u,v)\\}_{i=1}^{r}$ for every $(u,v)\in E$.
Step (2): Global Secret Exchange. 1. Let an arbitrary vertex $s$ compute a
random $R\in\\{0,1\\}^{b}$ for $b=\Theta(f\cdot\mathrm{cong}\cdot\log n)$. 2.
Apply Alg. $\mathsf{MobileBroadcast}$ to securely share the (secret) message
$R$. Step (3): Round by Round Simulation, Sim. Round $i$ of $\mathcal{A}$: Let
$m_{i}(u,v)$ be the unique message the $u$ needs to send to $v$ in round $i$.
1. If $m_{i}(u,v)$ is not empty set $\widehat{m}_{i}(u,v)\leftarrow
h^{*}(m_{i}(u,v)\circ 0^{B^{\prime}-B})+K_{i}(u,v)$. 2. Otherwise, set
$\widehat{m}_{i}(u,v)$ to be a uniformly random message of length
$B^{\prime}$. 3. $u$ sends $\widehat{m}_{i}(u,v)$ to $v$. Receiving round $i$
Let $\widehat{m}_{i}(u,v)$ be the message received by $v$ from $u$. 1. Compute
$m^{\prime}\leftarrow\widehat{m}_{i}(u,v)+K_{i}(u,v)$. 2. Compute $m$ as the
first lexicographically message satisfying $h^{*}(m)=m^{\prime}$. 3. If $m$
does not end with $B^{\prime}-B$ $0$’s, then drop the message (i.e., no
message from $u$ has been received). 4. Otherwise, set
$\widetilde{m}_{i}(u,v)$ to be the first $B$ bits of $m$.

##### Proof of Theorem 1.3.

We next turn to analyze the correctness of the construction.

######  Lemma A.6 (Correctness of Simulation).

W.h.p., for every rounds $i\in[r]$ and every pair of vertices $(u,v)\in E$, it
holds that:

  * •

If $m_{i}(u,v)$ is not empty $\widetilde{m}_{i}(u,v)=m_{i}(u,v)$.

  * •

If $m_{i}(u,v)$ is empty then $v$ drops the received message.

###### Proof.

Fix a round $i$ and a pair $(u,v)$. If $m_{i}(u,v)$ is not empty, then $u$
sends $\widehat{m}_{i}(u,v)\leftarrow h^{*}(m_{i}(u,v)\circ
0^{B^{\prime}-B})+K_{i}(u,v)$. The vertex $v$ gets $\widehat{m}_{i}(u,v)$ and
since it knows $K_{i}(u,v)$ and $h^{*}$ (as it knows the seed $R$), w.h.p. it
can obtain the message $m^{\prime}=m_{i}(u,v)\circ 0^{B^{\prime}-B}$ (by
checking $h^{*}(m^{\prime})+K_{i}(u,v)=\widehat{m}_{i}(u,v)$) as $m^{\prime}$
ends with $B^{\prime}-B$ 0’s, $v$ sets $\widetilde{m}_{i}(u,v)=m_{i}(u,v)$, as
desired.

If $m_{i}(u,v)$ is empty, then $u$ sends a random string
$m=\widehat{m}_{i}(u,v)$ of $B^{\prime}=B+3\log(nr)$ bits. To decrypt the
message, the receiver $v$ first computes $m^{\prime}=m+K_{i}(u,v)$ which is
still a random uniform string in $\\{0,1\\}^{B^{\prime}}$. Since all non-empty
messages have $B^{\prime}-B=3\log(nr)$ bits of $0$s, there are at most $2^{B}$
distinct such messages, and $h^{*}$ maps these messages into at most $2^{B}$
values in $\\{0,1\\}^{B^{\prime}}$. Since $m^{\prime}$ is sampled uniformly at
random in $\\{0,1\\}^{B^{\prime}}$, the probability that it is in the set of
these at most $2^{B}$ values is $2^{B-B^{\prime}}=(nr)^{-3}$. Hence, w.h.p.,
$(h^{*})^{-1}(m^{\prime})$ will not end with $B^{\prime}-B$ bits of $0$, and
$v$ drops the message, as desired. ∎

######  Lemma A.7 (Security of Simulation).

Alg. $\mathcal{A}^{\prime}$ is $f$-mobile-secure.

###### Proof.

By running the first phase and using Lemma A.1, the adversary knows nothing on
the keys $\mathcal{K}(u,v)$ of all but $4f$ edges, denoted hereafter by
$F^{*}$. Hence, the adversary learns nothing on the messages exchanged in Step
(3) over the edges in $E\setminus F^{*}$. In fact, those messages are
distributed uniformly at random in the view of the adversary. Since the empty-
messages of $\mathcal{A}$ are replaced by pure random messages, it remains to
show that the adversary learns nothing on the at most
$|F^{*}|\cdot\mathrm{cong}$ _non-empty_ messages going through $F^{*}$ in Alg.
$\mathcal{A}$.

We show that the security on these messages holds even if the adversary knows
all keys $\mathcal{K}(u,v)$ for every $(u,v)\in F^{*}$. By the security of the
broadcast algorithm of Theorem A.4, the adversary knows nothing on the random
seed $R$. Since the algorithm views a collection of at most
$f^{\prime}=f\cdot\mathrm{cong}$ values:
$h^{*}(m_{1}),\ldots,h^{*}(m_{f^{\prime}})$ where all messages
$m_{1},\ldots,m_{f^{\prime}}$ are distinct, by the properties of the
$f^{\prime}$-wise independent hash family $\mathcal{H}$, we get that these
values are distributed independently and uniformly at random. Consequently,
all messages observed by the adversary in the last phase, are pure random
messages. The security then holds. ∎

The proof of Theorem 1.3 follows. The number of rounds of the simulated
algorithm is

$\widetilde{O}(D+f\cdot\sqrt{\mathrm{cong}\cdot n}+f\mathrm{cong}+r\cdot\log
n)=\widetilde{O}(r+D+f\cdot\sqrt{\mathrm{cong}\cdot n}+f\cdot\mathrm{cong}),$

as desired. The correctness and security follow directly from Lemmas A.6 and
A.7, respectively.

##  Appendix B Proof of Lemma 4.2

In this section, we prove Lemma 4.2 by adapting Subsection 3 to be resilient
to an average number of faults per round rather than $f$ faults per round. The
adaptation is almost a word-for-word re-analysis of Subsection 3.

Let $t\geq\mathsf{D}_{\mathsf{TP}}\cdot\log^{\bar{c}}{n}$ for some large
enough constant $\bar{c}$ be an integer known to all nodes, and let
$\tau=\frac{t}{2\log{n}}$. Let $d=O(\frac{k}{\eta\log{n}})$be an integer known
to all nodes, such that we are guaranteed $|\\{(u,v)\in
E(G)\medspace|\medspace m(u,v)\neq\widetilde{m}(u,v)\\}|\leq d$.

##### Algorithm $\mathsf{ModifiedECCSafeBroadcast}$:

Let $\ell$ be an integer such that $k\geq c^{\prime\prime}\ell$ for a
sufficiently large $c^{\prime\prime}>0$, and let $\tau$ be an input integer.
The broadcast message held by the root $v_{r}$ consists of a list
$[\alpha_{1},\dots,\alpha_{\ell}]\in[q]$ where $q=2^{p}$ for some positive
integer $p$ and $q\geq k$. Let $C$ be a $[\ell,k,\delta_{C}]_{q}$-code for
$\delta_{C}=(k-\ell+1)/k$, known as the Reed Solomon Code. The root encodes
the broadcast message $[\alpha_{1},\dots,\alpha_{\ell}]$ into a codeword
$C([\alpha_{1},\dots,\alpha_{\ell}])=[\alpha^{\prime}_{1},\dots,\alpha^{\prime}_{k}]$.
Next, the algorithm runs $k$ RS-compiled $\mathsf{D}_{\mathsf{TP}}$-hop
broadcast algorithms, in parallel. That is, for every $T_{j}\in\mathcal{T}$,
let $\Pi(T_{j})$ be a $\mathsf{D}_{\mathsf{TP}}$-hop broadcast algorithm in
which the message $\alpha^{\prime}_{j}$ starting from the root $v_{r}$,
propagates over $T_{j}$ for $\mathsf{D}_{\mathsf{TP}}$ hops (hence taking
$O(\mathsf{D}_{\mathsf{TP}}+\log q)$ rounds). Then the nodes wait until a
total of $\tau$ rounds have elapsed since the start of the procedure. Let
$\Pi_{RS}(T_{j})$ be the RS-compilation of that algorithm, denoted hereafter
as RS-broadcast algorithm. All $k$ RS-broadcast algorithms are implemented in
parallel by using the scheduling scheme of Lemma 3.3.

Let $\alpha^{\prime}_{j}(u)$ be the value that a node $u$ receives from
$T_{j}$ (or $\alpha^{\prime}_{j}(u)=0$ if it received no value) at the end of
this execution. To determine the broadcast message
$[\alpha_{1},\dots,\alpha_{\ell}]$, each $u$ calculates first the closest
codeword $\alpha(u)$ to
$\alpha^{\prime}(u)=[\alpha^{\prime}_{1}(u),\dots,\alpha^{\prime}_{k}(u)]$.
Its output is then given by
$\widetilde{\alpha}(u)=[\widetilde{\alpha}_{1}(u),\dots,\widetilde{\alpha}_{\ell}(u)]=C^{-1}(\alpha(u))$.

######  Lemma B.1.

Consider the execution of Alg. $\mathsf{ModifiedECCSafeBroadcast}$ in the
presence of at most $td$ corrupted messages, with a given broadcast message
$[\alpha_{1},\dots,\alpha_{\ell}]\in[q]^{\ell}$, a distributed knowledge of a
_weak_ $(k,\mathsf{D}_{\mathsf{TP}},\eta)$ tree packing for
$k\geq\max\\{c^{\prime\prime}\cdot\ell,c^{*}d\eta\log{n}\\}$ for large
constants $c^{\prime\prime},c^{*}$, and assuming that
$\tau=\Omega((\mathsf{D}_{\mathsf{TP}}+\log{q})\eta)$. Then
$\widetilde{\alpha}(u)=[\alpha_{1},\dots,\alpha_{\ell}]$ for every node $u$.
In addition, the round complexity is $\Theta(\tau)$ $1$-CONGEST rounds.

###### Proof.

Let $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ be the collection of
$\mathsf{D}_{\mathsf{TP}}$-spanning trees rooted at a common root $v_{r}$. By
the definition of weak tree-packing, we have that $|\mathcal{T}^{\prime}|\geq
0.9k$.

By Lemma 3.3, all $k$ algorithms $\\{\Pi_{RS}(T_{j})\\}_{j=1}^{k}$ can be
performed in $\Theta(\tau)$ rounds, such that all but $c\cdot
d\cdot\eta(t/\tau)$ end correctly, for some constant $c$. Therefore, at least
$|\mathcal{T}^{\prime}|-c\cdot d\cdot\eta\log{n}\geq(1-1/c^{\prime})k$
algorithms are valid, by taking $k\geq c^{*}\eta d\log{n}$ for a sufficiently
large $c^{*}$. This implies that for at least $(1-1/c^{\prime})k$ algorithms
we have $\alpha^{\prime}_{j}(u)=\alpha^{\prime}_{j}$. (For that to happen, we
have $T_{j}\in\mathcal{T}^{\prime}$ and the RS-compiled algorithm
$\Pi_{RS}(T_{j})$ is valid. Or in other words,

$\frac{\operatorname{Hamm}(\widetilde{\alpha}(u),C(\alpha_{1},\dots,\alpha_{\ell}))}{k}\leq\frac{1}{c^{\prime}}.$

On the other hand, since $k\geq c^{\prime\prime}\ell$, the relative distance
of the code $C$ can be bounded by:

$\delta_{C}=\frac{k-\ell+1}{k}\geq 1-\frac{\ell}{k}\geq 1-1/c^{\prime\prime}.$

Therefore, for any given point $x\in\mathbb{F}_{q}^{k}$, there is at most one
codeword of relative distance less than $\delta_{C}/2$. As for sufficiently
large $c^{\prime},c^{\prime\prime}$, one obtains
$(1-\frac{1}{c^{\prime\prime}})/2\geq\frac{1}{c^{\prime}}$, we get that:

$\frac{\operatorname{Hamm}(\widetilde{\alpha}(u),C(\alpha_{1},\dots,\alpha_{\ell}))}{k}<\frac{\delta_{C}}{2}.$

We conclude that the decoding of every node is correct, i.e., that
$\widetilde{\alpha}(u)=[\alpha_{1},\dots,\alpha_{\ell}]$ for every $u$. ∎

##### Message Correction Procedure

Our algorithm works in iterations $j\in\\{1,\dots,z\\}$ for
$z=\Theta(\log{n})$. At the beginning of every iteration $j$, each node $v$
holds for each neighbor $u$, a variable $m^{\prime}_{j-1}(u,v)$, which
represents its estimate for its received message from $u$ in round $i$ of Alg.
$\mathcal{A}$. Initially, $m^{\prime}_{0}(u,v)=m^{\prime}(u,v)$.

Next, every node $v$ locally defines two multi-sets corresponding to its
outgoing messages and and its $j$-estimated incoming messages:

$\mathrm{Out}(v)=\\{m(v,u_{1}),\dots,,m(v,u_{\deg(v)})\\}\mbox{~{}and~{}}\mathrm{In}_{j}(v)=\\{m^{\prime}_{j}(u_{1},v),\dots,m^{\prime}_{j}(u_{\deg(v)},v)\\}.$

Let $S_{j}(v)$ be a stream formed by inserting each element in
$\mathrm{Out}(v)$ with frequency $1$, and each element in $\mathrm{In}_{j}(v)$
with frequency $-1$. Let $S_{j}=S_{j}(v_{1})\cup\dots,\cup S_{j}(v_{n})$ be
the stream formed by concatenating all $n$ individual streams.

Each subgraph $T\in\mathcal{T}$ runs an RS-compiled sub-procedure,
$L0_{RS}(T,S_{j},\tau)$, which is defined by applying the RS-compiler of
Theorem 3.2 for the following (fault-free) $L0(T,S_{j},\tau)$ procedure, which
is well defined when $T$ is a spanning tree. In the case where $T$ is an
arbitrary subgraph, the execution of $L0(T,S_{j})$ which is restricted to
$\widetilde{O}(\mathsf{D}_{\mathsf{TP}})$ rounds, will result in an arbitrary
outcome.

Procedure $L0(T,S_{j},\tau)$. The node $v_{r}$ first broadcasts
$\widetilde{O}(1)$ random bits $R_{j}(T)$ over the edges232323In the case
where $T$ is _not_ a spanning tree, $v_{r}$ might have no neighbors in $T$.
Nevertheless, the correctness will be based on the $0.9k$ spanning trees in
$\mathcal{T}$. of $T$. Then, each node $v$ initializes $s=O(\log{n})$ mutually
independent $\ell_{0}$-sampler sketches on $S_{j}(v)$ with randomness
$R_{j}(T)$ using Theorem 3.4. Let $[\sigma_{1}(v),\ldots,\sigma_{t}(v)]$ be
the $\ell_{0}$-sampling sketches obtained for $S_{j}$ with the randomness
$R_{j}(T)$. The sum of sketches $\sigma_{1}(S_{j}),\dots,\sigma_{t}(S_{j})$ is
then computed in a bottom-up manner on $T$ from the leaves to the root
$v_{r}$. Using these $s$ sketches, the root $v_{r}$ locally samples a list of
values $A_{j}(T)=[a_{1}(T),\dots,a_{s}(T)]$. The nodes terminate after exactly
$\tau$ rounds from the start of the protocol.

This concludes the description of $L0(T,S_{j},\tau)$ and hence also its RS-
compilation $L0_{RS}(T,S_{j},\tau)$. Our algorithm implements the collection
of the $k$ RS-compiled algorithms
$\\{L0_{RS}(T,S_{j},\tau)\\}_{T\in\mathcal{T}}$, in _parallel_ , by employing
the RS-scheduler of Lemma 3.3.

Detecting Dominating Mismatches. A _positive_ element $a\in A(T)$ is denoted
as an _observed-mismatch_. For every observed-mismatch
$a\in\bigcup_{T\in\mathcal{T}}A_{j}(T)$, denote its _support_ in iteration
$j$, by $\operatorname{supp}_{j}(a)=|\\{(\ell,T)\medspace|\medspace
a=a_{\ell}(T),T\in\mathcal{T},\ell\in\\{1,\ldots,t\\}\\}|$. The root $v_{r}$
then selects a sub-list $\mathsf{DM}_{j}$ of _dominating_ observed mismatches,
i.e., mismatches that have a sufficiently large _support_ in
$\bigcup_{T}A(T)$, based on the given threshold $\Delta_{j}$. Specifically,
for a sufficiently large constant $c^{\prime\prime}$

$\Delta_{j}=0.4c^{\prime\prime}2^{j}\eta
s\mbox{~{}and~{}}\mathsf{DM}_{j}=\\{a\in\bigcup_{T}A_{j}(T)\medspace|\medspace
a>0,\operatorname{supp}_{j}(a)\geq\Delta_{j}\\}~{}.$ (13)

The remainder of the procedure is devoted to (safely) broadcasting the list
$\mathsf{DM}_{j}$.

Downcast of Dominating Mismatches. To broadcast $\mathsf{DM}_{j}$, Alg.
$\mathsf{ModifiedECCSafeBroadcast}$ is applied with parameters $q=2^{p}$ for
$p=\lceil\max(\log{k},\log^{5}{n})\rceil$ and $\ell=|\mathsf{DM}_{j}|$. Upon
receiving $\mathsf{DM}_{j}$, each node $v$ computes its $j$-estimate
$m^{\prime}_{j}(u,v)$ as follows. If there exists a message
$m\in\mathsf{DM}_{j}$ with $\mathrm{id}(m)=\mathrm{id}(u)\circ\mathrm{id}(v)$,
then $v$ updates its estimate for the received message by setting
$m^{\prime}_{j}(u,v)=m$. Otherwise, the estimate is unchanged and
$m^{\prime}_{j}(u,v)\leftarrow m^{\prime}_{j-1}(u,v)$. This completes the
description of the $j^{th}$ iteration. Within $z=O(\log n)$ iterations, each
node $v$ sets $\widetilde{m}(u,v)=m^{\prime}_{z}(u,v)$ for every neighbor $u$.
In the analysis we show that, w.h.p., $\widetilde{m}(u,v)=m(u,v)$ for all
$(u,v)\in E$. The pseudocode of Algorithm $\mathsf{MessageCorrectionProtocol}$
is described next.

Algorithm $\mathsf{MessageCorrectionProtocol}$: Input: Weak
$(k,\mathsf{D}_{\mathsf{TP}},\eta)$ tree packing
$\mathcal{T}=\\{T_{1}\dots,T_{k}\\}$.
Output: Each node $v$ outputs $\\{\widetilde{m}(u,v)\\}_{u\in N(v)}$,
estimation for $m(u,v)$. 1. For $j=1,\dots,z=O(\log{n})$ do: • Employ protocol
$L0_{RS}(T,S_{j},\tau)$ over each $T\in\mathcal{T}$, in parallel, using Lemma
3.3. • Set $\mathsf{DM}_{j}$ as in Eq. (13). • Broadcast $\mathsf{DM}_{j}$ by
applying $\mathsf{ModifiedECCSafeBroadcast}(\tau)$. • For every $v\in V$ and
$u\in N(v)$: – If $\exists m\in\mathsf{DM}_{j}$ with
$\mathrm{id}(m)=\mathrm{id}(u)\circ\mathrm{id}(v)$:
$m^{\prime}_{j}(u,v)\leftarrow m$. – Otherwise, $m^{\prime}_{j}(u,v)\leftarrow
m^{\prime}_{j-1}(u,v)$. 2. For every $v\in V$ and $u\in N(v)$: Set
$\widetilde{m}(u,v)=m^{\prime}_{z}(u,v)$.

Analysis. For simplicity of presentation, we assume that all
$\ell_{0}$-sampler procedures succeed (by paying a $1/\operatorname{poly}(n)$
additive term in the failure probability of the protocol). Let
$\mathcal{T}^{\prime}\subseteq\mathcal{T}$ be the collection of spanning-trees
of depth at most $\mathsf{D}_{\mathsf{TP}}$, rooted at the common root
$v_{r}$.

We assume that $k\geq c^{\prime}\cdot c^{\prime\prime}\eta d\log{n}$, where
$c^{\prime\prime}$ is the constant in the number of failing algorithms in
Lemma 3.3, and $c^{\prime}>1$ is a sufficiently large constant compared to
$c^{\prime\prime}$. See Eq. (13) for the definition of $\Delta_{j}$.

A tree $T_{q}$ is denoted as $j$-_good_ if (a) $T_{q}\in\mathcal{T}^{\prime}$
and (b) $L0_{RS}(T_{q},S_{j},\tau)$ ended correctly when using the scheduler
of Lemma 3.3. Let
$\mathcal{T}^{(j)}_{\mathrm{good}}\subseteq\mathcal{T}^{\prime}$ be the
collection of good trees. Since the round complexity of each scheduler is
$\Theta(\tau)$ and the total number of faults is $td=2\tau d\log{n}$, at most
$cd\log{n}$ scheduled algorithms fail for some constant $c$. By Lemma 3.3, it
then holds that:

$|\mathcal{T}^{j}_{\mathrm{good}}|\geq\left(0.9-\frac{c^{\prime\prime}d\eta\log{n}}{k}\right)|\mathcal{T}|\geq\left(0.9-\frac{1}{c^{\prime}}\right)|\mathcal{T}|~{}.$
(14)

Finally, we say that a sent message $m(u,v)$ a $j$-_mismatch_ if $m(u,v)\neq
m^{\prime}_{j}(u,v)$. Let $B_{j}$ denote the number of $j$-mismatches.

######  Lemma B.2.

For every $j\in\\{0,\ldots,z\\}$, if $B_{j-1}\leq d/2^{j-1}$, then for any
$(j-1)$-mismatch $m$, $\operatorname{supp}_{j}(m)\geq\Delta_{j}$, w.h.p.

###### Proof.

Let $m$ be a $(j-1)$-mismatch. Since there are at most $d/2^{j-1}$ mismatches,
there are at most $2d/2^{j-1}$ non-zero entries in $S_{j}$. By Theorem 3.4, in
each sketch of a $j$-good tree $T$ the root detects a given $(j-1)$-mismatch
with probability at least $2^{j-1}/d-\epsilon(n)$ for
$\epsilon(n)=O(1/\operatorname{poly}(n))$. Therefore, for a sufficiently large
$c^{\prime}$, by Equations (13,14) and the fact that we use $s=O(\log n)$
independent $\ell_{0}$ sketches, we get:

$\mathbb{E}\left(\operatorname{supp}_{j}(m)\right)\geq\left(0.9-\frac{1}{c^{\prime}}\right)\left(\frac{2^{j}}{2d}-\epsilon(n)\right)k\cdot
s\geq 0.8\left(\frac{2^{j-1}}{2d}\right)k\geq 0.4c^{\prime\prime}\cdot
c^{\prime}2^{j}\eta\cdot s=c^{\prime}\Delta_{j}~{}.$

Moreover, the observed mismatches sampled by the good trees are mutually
independent of each other. Given $(j-1)$-mismatch $m^{\prime}$, the
probability that it is sampled by less than $\Delta_{j}$ many $j$-good trees
can be bounded by a Chernoff bound (Lemma 1.10), as follows:

$\Pr(\operatorname{supp}_{j}(m)\leq\Delta_{j})\leq\Pr\left(\operatorname{supp}_{j}(m)\leq\mathbb{E}\left(\operatorname{supp}_{j}(m)\right)/c^{\prime}\right)\leq
e^{-(1-1/c^{\prime})^{2}c^{\prime}\Delta_{j}/2}\leq\frac{1}{\operatorname{poly}(n)},$

where the last inequality holds for a sufficiently large $c^{\prime}$ (which
can be chosen sufficiently large compared to $c^{\prime\prime}$). ∎

######  Lemma B.3.

For every $j\in\\{0,\ldots,z\\}$, w.h.p. $B_{j}\leq d/2^{j}$.

###### Proof.

We prove the claim by induction on $j$. For $j=0$, the number of
$j$-mismatches at the start of the protocol is assumed to be at most $d$.
Assume that the claim holds up to $j-1$ and consider $j\geq 1$.

We say that an observed-mismatch $a$ has $j$-_high support_ if
$\operatorname{supp}_{j}(a)\geq\Delta_{j}$, and has $j$-_low support_
otherwise. An observed-mismatch $a$ is _competing_ with $m(u,v)$ if
$\mathrm{id}(a)=\mathrm{id}(u)\circ\mathrm{id}(v)$ but $a\neq m(u,v)$. Note
that assuming all sketches on $j$-good trees are successful (which indeed
holds w.h.p.), then all _competing mismatches_ with any message $m(u,v)$ must
be sampled by $j$-_bad_ trees, since they are not real $(j-1)$ mismatches.

A necessary condition for $m(u,v)$ to be a $j$-mismatch, is either that (a)
there is an observed-mismatch with $j$-high support that is competing with
$m(u,v)$, or (b) it is a $(j-1)$-mismatch and has $j$-low support. By Lemma
3.7, all $(j-1)$-mismatches have high support w.h.p., and therefore, there are
no $j$-mismatches due to condition (b).

Since the number of $j$-bad trees is at most
$c^{\prime\prime}d\eta\log{n}+0.1k$ (see Eq. (14)), at most
$\frac{(c^{\prime\prime}\eta d\log{n}+0.1k)s}{\Delta_{j}}\leq d/2^{j+1}$
competing observed-mismatches have $j$-high support. Therefore, $B_{j}\leq
d/2^{j}$ w.h.p. ∎

###### Proof of Lemma 4.2.

In the last iteration $z={O(\log{n})}$, it holds that $B_{z}=0$ (since $d\leq
n^{2}$ w.l.o.g.). In particular, at the last iteration $z$, each estimated
message is the correct message, i.e. $\widetilde{m}_{z}(u,v)=m(u,v)$. ∎

##  Appendix C Distributed Computation of a Low Depth Tree Packing

In this section, we show to compute a low depth tree packing in CONGEST. The
procedure and result is essentially the same as in [35], except we optimize
for different parameters, and use a more direct approach to analyze the
resulting packing using some modification to a well known greedy
multiplicative weights analysis. We give the details of this procedure for
completeness.

Assume a graph contains a packing $\\{T^{*}_{1},\dots,T^{*}_{k}\\}$ of
$d$-depth spanning trees with load at most $\eta$ . We describe a packing
process in CONGEST of $k$ many $O(d\log{n})$-depth spanning trees, which in
the analysis we show has load $O(\eta\log^{2}{n})$. We use the following
algorithm of [35] as a sub-procedure of our protocol:

######  Lemma C.1 ([35] Theorem 2).

Given parameter $d\geq D$, there is a CONGEST algorithm that in $O(d\log{n})$
rounds computes a $O(d\log{n})$-depth spanning tree with cost within
$O(\log{n})$ factor of the min-cost $d$-depth spanning tree.

In the remainder, denote $\alpha=O(\log(n))$ the approximation guarantee of
Lemma C.1. Our procedure is almost exactly the same as in [35]. Consider the
following process in which $k$ many $O(d\log{n})$-depth spanning trees
$T_{1},\dots,T_{k}$ are added one after the other in a sequence of $k$
iterations into the packing. For iteration $i=1,\dots,k$, let
$h^{i}_{e}=\\{j<i\medspace|\medspace e\in T_{i}\\}$ be the load of edge $e$ at
the start of iteration $i$, and let $w_{i}(e)=a^{h^{i}_{e}+1}-a^{h^{i}_{e}}$,
for $a=\log_{2}\frac{\alpha+2}{\alpha+1}$. In iteration $i$, we find using the
procedure of Lemma C.1 a $\widetilde{O}(\mathsf{D}_{\mathsf{TP}})$-depth
spanning tree, whose weight is within an $O(\log{n})$ factor of the min-cost
$\mathsf{D}_{\mathsf{TP}}$-depth spanning tree according to weight function
$w_{i}$. We add this tree to the packing, and update the weight of the edges
according to their new load. This concludes the description of the algorithm.
Let $l_{e}$ be the load of edge $e$ after the final iteration.

######  Theorem C.2.

Let $T_{1},\dots,T_{k}$ be a collection of trees obtained by a packing process
described above, where $w_{i}(T_{i})\leq\alpha w_{i}(T^{*}_{i})$ for any
$1\leq i\leq k$. Then the maximum load is at most
$\max_{e}l_{e}=O(\eta\alpha(\log{n}+\log{\alpha}))$.

###### Proof.

For any step $i$, the following holds due to our choice of $T_{i}$:

$\displaystyle\sum_{e\in T_{i}}(a^{h^{i+1}_{e}/\eta}-a^{h^{i}_{e}/\eta})$
$\displaystyle=\sum_{e\in
T_{i}}(a^{(h^{i}_{e}+1)/\eta}-a^{h^{i}_{e}/\eta})\leq\alpha\sum_{e\in
T^{*}_{i}}(a^{(h^{i}_{e}+1)/\eta}-a^{h^{i}_{e}/\eta})$
$\displaystyle=\alpha\sum_{e\in
T^{*}_{i}}a^{h^{i}_{e}/\eta}(a^{1/\eta}-1)\leq\alpha\sum_{e\in
T^{*}_{i}}a^{l_{e}/\eta}(a-1)/\eta~{}.$

We sum on $i=1,\dots,k$:

$\sum_{i=1}^{k}\sum_{e\in
T_{i}}(a^{(h^{i}_{e}+1)/\eta}-a^{h^{i}_{e}/\eta})\leq\alpha\sum_{i=1}^{k}\sum_{e\in
T^{*}_{i}}a^{l_{e}}(a-1)/\eta~{},$

where the last inequality holds since $a^{x}-1\leq x(a-1)$ for any $0\leq
x\leq 1$. By switching the order of summation, we get

$\displaystyle\sum_{e\in E}\sum_{i:e\in
T_{i}}(a^{(h^{i+1}_{e})/\eta}-a^{h^{i}_{e}/\eta})$ $\displaystyle=\sum_{e\in
E}\sum_{i:e\in T_{i}}(a^{(h^{i}_{e}+1)/\eta}-a^{h^{i}_{e}/\eta})$
$\displaystyle\leq\alpha(a-1)\sum_{e\in E}(a^{l_{e}/\eta}\cdot\sum_{i:e\in
T^{*}_{i}}(1/\eta))$ $\displaystyle\leq\alpha(a-1)\sum_{e\in
E}a^{l_{e}/\eta}~{}.$

As the left sum is a telescopic, we have:

$\displaystyle\sum_{e\in E}(a^{l_{e}/\eta}-1)\leq\alpha(a-1)\sum_{e\in
E}a^{l_{e}/\eta}$ $\displaystyle\implies\left(\sum_{e\in
E}a^{l_{e}/\eta}\right)-|E|\leq\alpha(a-1)\sum_{e\in E}a^{l_{e}/\eta}$
$\displaystyle\implies(1+\alpha-\alpha a)\sum_{e\in
E}a^{l_{e}/\eta}\leq|E|\implies(1+\alpha-\alpha a)\max_{e\in
E}a^{l_{e}/\eta}\leq|E|~{}.$

Finally, by taking $\log_{a}$ from both sides:

$\displaystyle\max_{e\in E}(l_{e}/\eta)$
$\displaystyle\leq\log_{a}|E|-\log_{a}(1+\alpha-\alpha
a)=(\log_{2}{|E|}-\log_{2}(1+\alpha-\alpha
a))/\log_{2}{\frac{\alpha+2}{\alpha+1}}$
$\displaystyle=(\log_{2}{|E|}+\log_{2}(1+\alpha))/\log_{2}{\frac{\alpha+2}{\alpha+1}}\leq(\log_{2}{|E|}+\log_{2}(1+\alpha))/(1/(2+2\alpha))$
$\displaystyle=O(\alpha(\log{n}+\log{\alpha})),$

where the last inequality holds since $2\log_{2}(1+x)\geq x$ for any $x\leq
1$. It follows that $\max_{e\in E}l_{e}=O(\eta\alpha(\log{n}+\log{\alpha}))$,
i.e. the load of the packing is $O(\eta\alpha\log{n})=O(\eta\log^{2}{n})$.

∎