Near-Optimal Resilient Labeling Schemes

In Algorithm 1, the oracle first constructs a greedy $(2f+2,2f+1)$-ruling set $S$. For every node $v$, let $b(v)$ be a single bit indicating whether $v\in S$, and let $distS(v)$ be an $O(\log f)$-bit value which is the distance between $v$ and $S$.

The oracle then partitions the nodes into groups of size $\mathrm{\Theta }(f)$. To later allow the distributed algorithm to reconstruct the same groups, the oracle uses the same algorithm the nodes will later use, i.e., Algorithm 3. However, for the description in this section, any partitioning with the same guarantees would give the desired result in Theorem 3 below.

Finally, the oracle applies an error-correcting code to each index of the labels of all nodes in each group. The new label it assigns to each node $v$ is a concatenation of its $b(v)$ and $distS(v)$ values, along with the encoded label.

Different codes $𝙲$ result in different overheads of ${\mathrm{\ell }}^{\prime }$ compared to $\mathrm{\ell }$. A simple repetition code takes the string $\mathrm{𝚒𝚗𝚏𝚘}$ of length $s$ and repeats it for $s$ blocks to create the resulting codeword $𝚠=𝙲(\mathrm{𝚒𝚗𝚏𝚘})$, which is trivially decodable given any $s-1$ blocks erasures. Splitting $𝚠$ back to $s$ pieces implies that ${𝚠}_i$ equals $\mathrm{𝚒𝚗𝚏𝚘}$ for every node $v_i$ in the group. Taking $f=F$, this results in ${\mathrm{\ell }}^{\prime }=1+O(\log f)+s\cdot \mathrm{\ell }=O(\log F)+s\cdot \mathrm{\ell }$. Since the group size $s$ is always $\mathrm{\Theta }(f)=\mathrm{\Theta }(F)$, we get a multiplicative overhead of $O(F)$ and an additive overhead of $O(\log F)$. To reduce the multiplicative overhead to $O(1)$, we use a code with better parameters. Formally, a binary code $𝙲$ maps strings of $k$ bits into strings of $N$ bits called codewords. The ratio $\rho =N/k$ is the code’s rate. The relative distance, $\delta$, ensures the Hamming distance (number of indices where the strings differ) between any two codewords is at most $\delta N$. Such a code can correct $\delta N-1$ erasures.

Given the bound $F$ on the number of label erasures, we need to choose a value of $f$ to work with. Then, given a group of size $s$ such that $f+1\le s\le 3f+1$, we need to choose values for $\rho$ and $M$ that determine the code ${𝙲}_M$. We set these parameters as follows. We let $f=80F$, and for every such $s$ we choose $\rho =1/4$. To choose $M$, notice that Lemma 2 gives that for any $M>0$, the number of bits we can encode is $k_M={\rho }_M{N}_M$. We choose the smallest $M$ such that $k_M$ is at least $s$.

The next theorem proves that the overhead for the number of bits held by each node per coded bit is constant and that, given the coded blocks,it is possible to decode the original string of bits if up to $F$ blocks are erased. The proof is presented in Appendix A.

For later use by the distributed algorithm in our resilient labeling scheme, we denote by $decode(v,\{(u,𝚠(u))\mid u\in Group(v)\})$ the function that takes as input a node $v$ and the values $𝚠(u)$ for all the nodes $u$ in $Group(v)$ (along with their IDs so that they can be ordered correctly) and produces the bit of $v$ in the string $𝚛$ which was encoded into $𝚠$, by Theorem 3.

In Algorithm 2, nodes restore a greedy ruling set $S$ as follows. Before the algorithm starts, each non-faulty node $w$ sets its value $b(w)$ to the first bit of its label. At the beginning of the algorithm, non-faulty nodes in $S$ broadcast a bit “1” for $2f+1$ rounds. Here, every node that receives a bit “1” during these rounds forwards it to all of its neighbors. Faulty nodes $u$ that receive a bit during these rounds sets $b(u)=0$, as this indicates that $u\in B_{2f+1}(v)$ for some such $v\in S$ and thus $u\notin S$.

Next, each faulty node propagates its ID through a distance of $2f+1$. Faulty nodes $u$ that do not receive any other ID set $b(u)=1$, as this means no other faulty nodes are in $B_{2f+1}(u)$ and thus $u\in S$.

Now, every remaining faulty node $u$ propagate a message of the form $ID(u)\circ dist$ through a distance of $f+1$, where $dist$ starts at 0 and is increased by 1 by each node along the way, corresponding to the length of the path. For each node $w$, let $dis{t}_u(w)$ be the smallest $dist$ value received for $u$, representing the actual distance between $w$ and $u$.

Each node $w\in B_{f+1}(u)$ receives the message and checks if it is possible that $u\in S$ by verifying whether $distS(w)=dis{t}_u(w)$. If this equality does not hold, $w$ propagates a message with $ID(u)$ through a distance of $f+1$. Since $dist(w,u)\le f+1$, if $u\in S$, then $distS(w)=dis{t}_u(w)$. If $w$ propagates $ID(u)$, then this is not the case, so when $u$ receives its own ID, it can conclude that it is not in $S$ and sets $b(u)=0$.

Now, we are left with faulty nodes $v\in S$ and faulty nodes $u\notin S$. We will prove that $u$ is an alternative node for a faulty node $v\in S$. Thus, every faulty node $v\in S$ must have the lowest ID among faulty nodes in $B_{f+1}(v)$ and can deduce that it is in $S$ and set $b(v)=1$. Similarly, every faulty node $u\notin S$ must have a faulty node $v\in S$ within $B_{f+1}(u)$ such that , allowing $u$ to deduce it is not in $S$ and set $b(u)=0$.

Following is the formal algorithm and proof.

To prove that the algorithm restores the set $S$, we prove that every node $w\in V$ holds $b(w)$ at the end of Algorithm 2, such that $\{w\mid b(w)=1\}=S$. By Step 2, this holds for all non-faulty nodes, so it remains to prove it for faulty nodes. In what follows, we go over each step in the algorithm where nodes may set their output (Steps 2,2,2, and 2), and we show that any node which sets its output during that step does so correctly.

In Step 2, every non-faulty node $v\in S$ broadcasts a bit “1” for $2f+1$ rounds. By the definition of a $(2f+2,2f+1)$-ruling set, every two nodes $v^{\prime },v^{\prime \prime }\in S$ satisfy that $dist(v^{\prime },v^{\prime \prime })\ge 2f+2$. Thus, if a faulty node $u$ receives a bit “1” from $v\in S$ during these $2f+1$ rounds, it implies that $u\in B_{f+1}(v)$. Hence, $u\notin S$ since $v\in S$. So, for any node $u$ that sets $b(u)=0$ in Step 2, its output is correct.

Afterwards, in Step 2, each faulty node propagates a message with its ID through a distance of $2f+1$. Every faulty node $u$ that does not receive any other ID during these rounds and did not receive a “1” during Step 2 sets $b(u)=1$, because this implies that there is no other faulty node in $B_{2f+1}(u)$ and hence it must hold that $u\in S$. So, it is correct that $u$ sets $b(u)=1$ in Step 2.

Then, in Step 2, every node $u$ that is still faulty propagates a message of the form $ID(u)\circ dist$ through a distance of $f+1$, where $dist$ starts at $0$ and is increased by $1$ before the message is propagated further. This corresponds to the length of the path that this message traverses. Every node $w\in B_{f+1}(u)$ receives the above message and checks if it is possible that $u\in S$ by verifying whether $distS(w)=dis{t}_u(w)$. We denote by $dist(u)$ the value of $dist$ from the message $ID(u)\circ dist$ that $w$ receives. If equality does not hold, then $w$ propagates a message with $ID(u)$ through a distance of $f+1$. Since $dist(u,w)\le f+1$, if $u\in S$, then for every other node $v^{\prime }\in S$ such that $dist(w,v^{\prime })\le f+1$, it holds that $2f+2\le dist(u,v^{\prime })\le dist(u,w)+dist(w,v^{\prime })\le f+1+dist(w,v^{\prime })$. Thus, $dist(w,v^{\prime })\ge f+1$, and since $distS(w)={\min }_{v\in S}\{dist(q,v)\}$ we have $distS(w)=dis{t}_u(w)$. But if $w$ propagates $ID(u)$, then this is not the case, so $u\notin S$. Thus, it is correct that $u$ sets $b(u)=0$ in Step 2.

First we prove that every node $u$ that is still faulty at the beginning of this step and every node $v\in X(u)$ are alternative nodes. By definition of alternative nodes, we need to prove that $dist(u,v)\le f$ and that $v$ and $u$ have at most $f-2$ nodes $w\in B_{f+1}(v)\cup B_{f+1}(u)$ with $dist(u,w)\ne dist(v,w)$.

First, since $v\in X(u)$, it must be that $dist(u,v)\le f$. Second, we prove that $v$ and $u$ have at most $f-2$ nodes $t\in B_{f+1}(v)\cup B_{f+1}(u)$ with $dist(u,t)\ne dist(v,t)$. Assume, towards a contradiction, that there are at least $f-1$ nodes $t\in B_{f+1}(v)\cup B_{f+1}(u)$ with $dist(v,t)\ne dist(u,t)$. Since $u$ is still faulty in Step 2, there are at most $f-2$ nodes $q\ne u,v$ in $B_{f+1}(u)$ with $dist(u,q)\ne dist(v,q)$, because otherwise $u$ would receive a message with $ID(u)$ from such a non-faulty node during Step 2 and would set $b(u)=0$ in Step 2. Therefore, there exists a node $s\in B_{f+1}(v)\setminus B_{f+1}(u)$ that is still faulty in Step 2. We consider two cases, obtaining a contradiction in both, and conclude that the assumption is incorrect. Thus, $v$ and $u$ have at most $f-2$ nodes $t\in B_{f+1}(v)\cup B_{f+1}(u)$ with $dist(u,t)\ne dist(v,t)$.

An illustration of this case is presented in Figure 1.

In this case, every node $t\ne u,v$ on $P_{v,u}$ satisfies that $dist(u,t)\ne dist(v,t)$, except at most one node $a$ (such a node $a$ exists if $dist(u,v)$ is even and $a$ is exactly in the middle of $P_{v,u}$). Additionally, every node $t$ on $P_{v,s}$ satisfies that $dist(t,v)\ne dist(t,u)$, as otherwise $dist(u,s)\le dist(u,t)+dist(t,s)=dist(v,t)+dist(t,s)=dist(v,s)\le f+1$, which contradicts the assumption that $dist(u,s)\ge f+2$. Denote by $P^{\prime }$ the path $P_{u,v}\circ P_{v,s}$ at a distance of at most $f+1$ from $u$. There are $f$ nodes on $P^{\prime }$ that are neither $u$ nor $v$. Additionally, excluding the node $a$, we have $f-1$ nodes $q$ on $P^{\prime }$ with $dist(v,q)\ne dist(u,q)$, and they are all in $B_{f+1}(u)$. This contradicts the assumption that there are at most $f-2$ such nodes. Therefore, this case in not possible.

An illustration of this case is presented in Figure 2.

We consider $r$ to be the closest node to $u$ in $P_{v,u}\cap P_{v,s}$. In this case, every node $t\ne u,v$ on $P_{v,u}$ satisfies that $dist(u,t)\ne dist(v,t)$, except at most one node $a$, as we proved in the previous case. Therefore, it is also correct for $P_{u,r}$. Additionally, every node $t$ on $P_{r,s}$ satisfies that $dist(t,v)\ne dist(t,u)$, as otherwise $dist(u,s)\le dist(u,t)+dist(t,s)=dist(v,t)+dist(t,s)=dist(v,s)\le f+1$, contradicting the assumption that $dist(u,s)\ge f+2$.

Denote by $P^{\prime }$ the path $P_{u,r}\circ P_{r,s}$ at a distance of at most $f+1$ from $u$. There are $f+1$ nodes on $P^{\prime }$ that are not $u$. Additionally, excluding the node $a$, we have $f$ nodes $q$ on $P^{\prime }$ with $dist(v,q)\ne dist(u,q)$, and they are all in $B_{f+1}(u)$. This contradicts the assumption that there are at most $f-2$ such nodes. Therefore, this case in not possible.
This completes the proof that every node $u$ that is still faulty at the beginning of this step and every node $v\in X(u)$ are alternative nodes.

Now, we prove that if $u$ sets $b(u)=0$ in this step, then it satisfies that $u\notin S$. In this case, since $u$ sets $b(u)=0$, there exists a node $v\in X(u)$ with . Since $v$ is an alternative node for $u$ with , it follows that $u\notin S$ by Lemma 6.

Finally, we prove that every faulty node $u$ that sets $b(u)=1$ satisfies that $u\in S$. By the definition of a $(2f+2,2f+1)$-ruling set, there exists a node $v\in S$ such that $dist(u,v)\le 2f+1$ (which may be $u$ itself). We claim that $v\in B_f(u)$. Assume otherwise, i.e., that $dist(u,v)\ge f+1$. Notice that $v,u$ have at least $|P_{v,u}|-2$ nodes $j$ with $dist(v,j)\ne dist(u,j)$ on $P_{v,u}$, since there are $|P_{v,u}|-1$ nodes $j\ne u,v$ on $P_{v,u}$, and at most one of them has $dist(v,j)=dist(u,j)$ (such a node $j$ exists if $dist(u,v)$ is even and $j$ is exactly in the middle of $P_{v,u}$). Therefore, if $dist(u,v)\ge f+1$, consider nodes on the path $P_{u,v}$ that are at a distance of at most $f+1$ from $u$. There are at least $f-1$ such nodes $j\ne u,v$ with $dist(u,j)\ne dist(v,j)$, and so at least one of them is not faulty, which would lead to $u$ setting $b(u)=0$ in Step 2. But, $u$ is faulty at the beginning of Step 2, which leads to a contradiction.

Thus, $v\in B_f(u)$. Additionally, $v\in X(u)$ because in Step 2, $u$ is still faulty, and therefore, in Step 2, $u$ does not set $b(u)=0$, so $v$ must also still be faulty in Step 2. Since $dist(u,v)\le 2f+1$ and $v$ is still faulty in Step 2, $u$ receives a message with $ID(v)$ in Step 2. Note that if $v$ is not faulty in Step 2, then either it is non-faulty to begin with, in which case $u$ would have already set $b(u)=0$ in Step 2, or $v$ sets $b(v)=1$ in Step 2. The latter is impossible because $dist(u,v)\le 2f+1$ and $u$ is still faulty in Step 2. Thus, $v$ is still faulty in Step 2, which means that $v$ would receive a message from $u$ in Step 2 and not set $b(v)=1$ in Step 2. Thus, $v$ is also still faulty in Step 2, and since $dist(u,v)\le f$, then $v\in X(u)$.

Thus, since $u$ sets $b(u)=1$, every node $w\in X(u)$ satisfies $ID(u)\le ID(w)$. Since, $w\in X(u)$, then as we proved, $w$ is an alternative node for $u$. By Lemma 6, this implies that $w$ cannot be in $S$. Since $v\in X(u)\cap S$, it must hold that $v=u$. Thus $u\in S$, as needed.

This completes the proof that, at the end of Algorithm 2, we set $b(w)$ for every node $w\in V$ correctly, satisfying $\{w|b(w)=1\}=S$. Finally, we sum the number of rounds the algorithm takes. In every broadcast in the algorithm, we have at most $f$ different messages (each of which fits in $O(\log n)$ bits). Moreover, a node passes such a message only once. Thus, each broadcast takes $O(f)$ rounds. Since there are only a constant number of steps with such broadcasts, the algorithm completes in $O(f)$ rounds. $◀$

Algorithm 3 constructs the required partition as follows. Initially, each node $v\in S$ computes a BFS tree to depth $2f+1$ by propagating its ID. Nodes that receive multiple root IDs choose the smallest and use that tree only. The rest of the algorithm operates within each tree independently.

Within each tree, each node $u$ divides the nodes in its subtree into groups of size $f+1\le s\le 3f+1$, with a remainder of up to $f$ nodes. This remaining number is sent to its parent $parent(u)$, who handles dividing the remainders of its children similarly. The $\mathrm{𝙲𝚘𝚖𝚙𝚞𝚝𝚎𝙶𝚛𝚘𝚞𝚙𝚜}(u)$ procedure sorts $u$’s children by increasing IDs, appends itself, and then forms groups by summing the remaining values of its children. Once a group reaches the desired size, a new group starts from the next child. Each child receives its group ID from $u$. When a node receives its group allocation, it may need to inform some of its children to ensure that remaining nodes from its subtree join this group as well. This is handled by the $\mathrm{𝚁𝚎𝚕𝚊𝚢𝙶𝚛𝚘𝚞𝚙𝚜}(u)$ procedure, in which node $u$ relays the group ID. During this process, $u$ also sets the local variable $H_u$ which is used for constructing low-congestion shortcuts for communication among the nodes of each group. Finally, if there is a small remainder at the root $v$, the root appends these nodes to one of the groups created in $\mathrm{𝙲𝚘𝚖𝚙𝚞𝚝𝚎𝙶𝚛𝚘𝚞𝚙𝚜}(v)$ or, if no such group was constructed by $v$, it appends them to a group with the closest node from this group to $v$. This is done by $v$ obtaining the required group ID and relaying it to the relevant remaining nodes.

Following is the formal algorithm and proof.