Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications

Before presenting the formal description in Section 2 (Definition 2), we will provide a high-level overview of our codes. We begin with the classic definition of superimposed codes, followed by an outline of the properties of our codes, including both the newly introduced and previously established properties. We will then review the relevant literature related to our codes and compare their performance to prior results. Finally, we will conclude with a discussion on how these codes can enhance performance in pertinent distributed problems, particularly in beeping networks and multiple-access channels, as well as in other contexts.

The definition of URSC codes involves a condition on subsets of $k$ columns, which can be computationally challenging to verify due to the super-polynomial number of such subsets. A crucial step towards an efficient construction is the introduction of the Collision Bound Property, a sufficient condition for ensuring the resilience properties of $(n,\alpha )$-URSC, which applies to pairs of columns rather than subsets of $k$ columns.

Before delving into the formal definition, let us summarize the Collision Bound Property. This property divides each column into upper and lower segments – specifically $[0,{\tau }_1(n,k)]$ and $[{\tau }_1(n,k),{\tau }_2(n,k)]$, with ${\tau }_2(n,k)$ corresponding to the elongation of the code – and ensures two key inequalities: the Weight Inequality, which pertains to any individual column, and the Collision Weight Inequality, which applies to any pair of columns.

• $\mathrm{■}$

  Weight Inequality: The first inequality compares the weights of the upper and lower segments of any column. Specifically, it ensures that the weight of the upper segment is at most $\alpha$ times the weight of the lower segment. This establishes a specific dominance of the lower segment’s weight over the upper segment’s weight.

• $\mathrm{■}$

  Collision Weight Inequality: The second inequality bounds the “collision weight” of any pair of columns:

  $$\left|{\left([{𝐜}_{𝐣}]\wedge \left([{𝐜}_{{𝐣}^{\prime }}](i-1)\vee [{𝐜}_{{𝐣}^{\prime }}](i)\vee [{𝐜}_{{𝐣}^{\prime }}](i+1)\right)\right)}_{[{\tau }_1(n,k),{\tau }_2(n,k)]}\right|,$$

  defined as the number of positions in the lower segment where a column intersects with the slipped vector of any cyclic shift of the other column of the pair. This inequality ensures that this collision weight does not exceed $\alpha$ times one $(k-1)$th of the lower segment’s weight. This helps in controlling the overlap between columns, which is crucial for maintaining the superimposed code property.

The following lemma establishes the sufficiency of the Collision Bound Property in guaranteeing that a matrix $𝐌$ is an $(n,2\alpha )$-URSC.

In this subsection, we present a random construction of a binary matrix. As demonstrated in the next subsection, this construction has a high probability of satisfying the Collision Bound Property $𝒫(𝐌,\alpha ,{\tau }_1,{\tau }_2)$ and, hence, of being an $(n,2\alpha )$-URSC in view of Lemma 4. In Theorem 8 we finally obtain an $(n,\alpha )$-URSC.

In addition to $n$ and $\alpha$, the construction relies on two more parameters: an arbitrarily small constant $ϵ>0$ and a real constant $c>0$. The role of $ϵ$ is to bring the elongation of the code arbitrarily close to the asymptotic bound $O({(k/\alpha )}^2\ln n)$. The constant $c$, if sufficiently large, ensures a high probability of successful construction, as will be demonstrated in the next section.

The goal of the random construction that we are going to describe is to assign the probability $p(r)$ of having a 1 in the $r$th bit of each column, for . The ignorance of the parameter $k$ presents new significant challenges (in addition to those related to the arbitrary shifts), as we cannot use $k$ in assigning the probabilities $p(r)$, nor can we use a uniform distribution. Instead, we estimate $k$ as we descend the positions of the columns, with probabilities in the upper part tailored for smaller values of $k$ and those in the lower part for larger values of $k$. This is achieved by gradually decreasing the probabilities $p(r)$ as $r$ increases, i.e., as we move down the positions of the columns. Throughout this process, we must ensure that the two inequalities of the Collision Weight Property are satisfied, creating a subtle trade-off as explained below.

The Weight Inequality requires that the decrease in the frequency of 1’s is controlled such that the weight of the lower segment (from ${\tau }_1(n,k)$ to ${\tau }_2(n,k)$) dominates the weight of the upper segment (up to position ${\tau }_1(n,k)-1$). Conversely, the Collision Weight Inequality requires that this dominance does not lead to an excessive number of collisions in the lower segment; specifically, the number of collisions in the lower (dominating) segment must be significantly less than the weight of each column. Additionally, this inequality must be satisfied without extending ${\tau }_2(n,k)$ beyond the desired elongation.

As we will show, a carefully chosen probability function that decreases according to the square root of the inverse of the column’s position $r$, strikes the right balance among all these conflicting targets.

Finally, it is worth noting, that although each column of the matrix will have length $t=c/({\alpha }^{2+ϵ})n^2\ln n$ (since they cannot depend on $k$), it will be shown later that the code still guarantees an elongation of $\tau (n,k)=c/({\alpha }^{2+ϵ})k^2\ln n$.

Our next objective is to show that for ${\tau }_1(n,k)=\frac{c}{64}{k}^2\ln n$ and ${\tau }_2(n,k)=\frac{c}{{\alpha }^{2+ϵ}}{k}^2\ln n$, any random matrix constructed as illustrated in subsection 3.2, satisfies the Collision Bound Property $𝒫(𝐌,\alpha ,{\tau }_1,{\tau }_2)$ with high probability. (It is important to clarify that, as we will see in Section 3.4, the functions ${\tau }_1$ and ${\tau }_2$, which are defined in terms of the unknown $k$ (and $n$), do not need to be known by the construction algorithm.) Namely, we will be proving the following.

The proof of Lemma 6 is quite involved, as it requires bounding the probabilities associated with satisfying the Weight Inequality and the Collision Weight Inequality separately.

While the complete technical proof of Lemma 6 is deferred to the full version of the paper, we provide here a high-level overview of the main steps involved. The Weight Inequality requires us to control the expected weights of both the upper and lower segments of each column $[{𝐜}_{𝐣}]$. We analyze these segments as expected values over the randomized matrix construction, allowing us to bound the probability that the Weight Inequality is satisfied.

For the Collision Weight Inequality, we define a random variable to represent the number of collisions between each pair of columns $[{𝐜}_{𝐣}]$ and $[{𝐜}_{{𝐣}^{\prime }}]$ within the lower segment: $[{\tau }_1(n,k),{\tau }_2(n,k)]$. This random variable must account for any possible cyclic shift (and corresponding slipped vector) of the second column $[{𝐜}_{{𝐣}^{\prime }}]$ relative to the first column $[{𝐜}_{𝐣}]$. Specifically, for any fixed shift , this random variable is given by ${\sum }_{d=-1}^1|[{𝐜}_{𝐣}]\wedge [{𝐜}_{{𝐣}^{\prime }}](i+d)|$. Bounding the probability that this variable meets the inequality’s criteria is particularly challenging for the following reasons.

The expected value of this variable is heavily influenced by the shift magnitude of the second column of the pair, which significantly affects, within the lower interval $[{\tau }_1(n,k),{\tau }_2(n,k)]$, the probabilities $p\left((r+i+d)modt\right)$, representing the probability that the slipped vector of the shifted column hosts a 1 in its $r$th position after a shift $i$, for and $d=-1,0,1$. To address this, we analyze three separate cases based on the magnitude of probabilities $p\left((r+i+d)modt\right)$ for all $r$ in the interval ${\tau }_1(n,k)\le r\le {\tau }_2(n,k)$.

The first case handles collisions when the shift of the second column in the pair is minimal, causing all probabilities of the shifted column to be high within the positions of the lower segment. Here, we apply the rearrangement inequality (see Theorem 368 in [13]), which enables a precise estimation of the expected number of collisions for high-probability entries. This technique maximizes the sum of products of corresponding probabilities (i.e., the expected collision count) by aligning the largest probability values in both columns, yielding a tight upper bound on collisions under minimal shifts.

In the second case, we consider mid-range shifts where the probabilities in the shifted column remain within a constant factor of each other. To handle this, we develop a pairwise bounding technique that leverages the near-uniformity of probabilities across positions. This approach minimizes the dependency on exact probabilities, allowing us to obtain a balanced estimate of collisions despite moderate variations.

Finally, the third case considers the situations where the probabilities of the shifted column are very low from ${\tau }_1(n,k)$ up to some intermediate position ${\tau }^{\prime }$, with , and then become large from the next position ${\tau }^{\prime }+1$ until ${\tau }_2(n,k)$. To address this, we employ a two-segment analysis that treats the low-probability and high-probability segments separately. Specifically, we combine the techniques from Case 2 for the low-probability segment and Case 1 for the high-probability segment.

The proof of Lemma 6 is ultimately completed by combining the probability of satisfying the Weight Inequality and that of satisfying the Collision Weight Inequality.

The construction of the ultra-resilient superimposed codes is accomplished by Algorithm 1, a randomized algorithm that, in addition to the parameter $n$ and the real number , takes as input an arbitrarily small constant $ϵ>0$ and a constant $c>0$. The next lemma proves that if the constant $c$ is sufficiently large as established in Lemma 6, then Algorithm 1 outputs an $(n,2\alpha )$-URSC with elongation $\tau (n,k)=c(k^2/{\alpha }^{2+ϵ})\ln n$, for any .

We could parameterize the ultra-resilient superimposed codes also by their length $t$, e.g., we could consider codes with length shorter than in Theorem 8. More precisely, in Definition 2, we could consider any length $t$ of the code and vary the upper bound on the values of $k$ for which the elongation guarantee holds, which originally was $n$, to some parameter $\mathrm{\Delta }$, where $\mathrm{\Delta }$ is the maximum integer such that: $\mathrm{\Delta }\le n$ and $\tau (n,\mathrm{\Delta })\le t$. This lowering of the upper bound on parameter $k$ is natural, because shorter codes could not guarantee a successful position of any element in every configuration of the codewords, due to existing lower bounds on the length of the code even if $k$ is known and there are no shifts, see e.g., [10].

In general, if we cut the ultra-resilient superimposed code at some smaller length , the resulting code may not satisfy the elongation property in Definition 2 for many values of parameter $k$, because the shifts in the original and the cut codes results in different configurations. However, our construction in Section 3, still works for shorter codes, with only few minor updates in the construction algorithm and in the analysis. Mainly, we need to replace the formula for the length $t=(c/{\alpha }^{2+ϵ})n^2\ln n$ by $t=(c/{\alpha }^{2+ϵ}){\mathrm{\Delta }}^2\ln n$, and consider only parameters $2\le k\le \mathrm{\Delta }$. Note that throughout the analysis, all the probability bounds depend on the number of codewords $n$, the $\log n$ factor coming from the elongation function, and $\alpha$; all of these stay the same in the $t$-parameterized codes, hence the probabilities stay analogous (only constants may change, which we could accomodate here by taking a larger constant $c$).

This way we can prove the following extension of Theorem 8 to codes with arbitrary length $t$.

Let $G$ be an underlying beeping network with $n$ nodes, modeled as an undirected simple graph. Each node $v$ in the graph has a unique identifier from the set $\{1,\mathrm{\dots },n\}$. Without loss of generality, we will refer to both the node and its identifier as $v$. Each node is initially aware only of its own identifier, the total number of nodes $n$, and an upper bound $\mathrm{\Delta }$ on its degree (the number of neighbors).

In the uncoordinated setting, nodes are activated in arbitrary rounds, as determined by a conceptual adversary.²²2Alternatively, the uncoordinated setting can be viewed as a temporal graph, where each node becomes “visible” after its adversarial wake-up time, and each edge becomes “visible” during the earliest time interval when both of its endpoints are awake. The goal for each node $v$ is to maintain a set of identifiers $N_v^{\ast }$ that satisfies the following properties:

Inclusion:

$N_v^{\ast }$ contains all the identifiers of the neighbors of $v$ in $G$.

Safety:

$N_v^{\ast }$ does not contain the identifier of any node that is not a neighbor of $v$ in $G$.

This problem is referred to as neighborhood learning.

In a more general problem, each node has to maintain a set of input messages stored in its neighbors. This problem is often called local broadcast.

Time complexity of a given problem in uncoordinated beeping networks is typically measured as a worst-case (over graph topologies and adversarial wake-up schedules) number of rounds from the moment when all nodes become awaken until the task is achieved, see [9]. In the case of neighborhood learning and local broadcast, the task is achieved if all locally stored sets of neighbors (resp., messages in neighbors) contain all neighbors (resp., all neighbors’ messages). Note that, due to the Safety condition, when one of these two tasks is achieved, the locally stored sets of neighbors (resp., messages) do not change in the future rounds. On the other hand, to guarantee the Inclusion property under arbitrarily long delays in adversarial wake-up schedule, algorithmic solutions have to be prepared for an arbitrarily long run – therefore, periodic algorithms seem to be most practical and as such have been considered in the literature, see [9].

It needs to be noted that the time complexity bound, denote it by $𝒯$, of our algorithms, proved in the analysis, satisfies even a stronger property: for any edge in the underlying network $G$, its both end nodes put each other (resp., each other’s message) to the locally maintained set within time $𝒯$ after both of them become awaken. It means that we do not have to wait with time measurement until all nodes in the network are awaken, in case we are interested in specific point-to-point information exchange.

Let $G$ be an underlying beeping network of $n$ nodes and node degree less than $\mathrm{\Delta }$. Each node knows only its id and the integers $n$ and $\mathrm{\Delta }$. ³³3The algorithm and its analysis work also if each node knows some polynomial upper bound on $n$ and a linear upper bound on $\mathrm{\Delta }$. All nodes have the same $(n,\frac{3}{4})$-URSC $𝐌$ from Theorem 9, of length set to $t=(c/{\alpha }^{2+ϵ}){\mathrm{\Delta }}^2\ln n$ and elongation $\tau (n,k)\le (c/{\alpha }^{2+ϵ})k^2\ln n$, for some constant $c>0$, parameter $\alpha =\frac{1}{2}\cdot \frac{3}{4}=\frac{3}{8}$ and for any $k\le \mathrm{\Delta }$ (the latter is because $\tau (n,\mathrm{\Delta })=t$ and $\mathrm{\Delta }\le n$); in practice, it is enough that each node $v$ knows only the corresponding column $v$ of the code.⁴⁴4Constant $\frac{3}{4}$ is set arbitrarily – it could be any constant in the interval $(\frac{1}{2},1)$ to allow the application of Theorem 7. Additionally, each node computes in the beginning its unique block ID of length $7+2\log n$, defined next.

Now suppose that each node $v$ has a message of length $ℳ$. It splits it into a sequence of $\log n$ messages of size $ℳ/\log n$ each, say $M_v[1],\mathrm{\dots },M_v[ℳ/\log n]$. Then, it creates extended messages $M_v^{\ast }[i]$, for any $1\le i\le ℳ/\log n$, as follows: it puts a binary representation of $v$ by $\log n$ bits first, then it puts a single bit equal to $1$ for $i=1$ and to $0$ otherwise (this bit indicates whether it is the first extended message or not), and then appends $M_v[i]$. The length of $M_v^{\ast }[i]$ is $2\log n+1\le O(\log n)$.

There are two changes in Algorithm 2. First, we now treat $M_v^{\ast }[i]$ as a set of new ids on node $v$. Hence, we need a $(2n^2,3/4)$-URSC $ℳ$ from Theorem 9, but of asymptotically same length $t=O({\mathrm{\Delta }}^2\log n)$ as for neighborhood learning (as obviously $\log (2n^2)=\mathrm{\Theta }(\log n)$ and we want to use the same bound $\mathrm{\Delta }$). Second, node $v$ in its $i$th periodic procedure (recall that such a procedure is in lines 6 - 16) uses $M_v^{\ast }[imodℳ/\log n]$ as its id. Let’s denote this modified algorithm as the ultra-resilient Beeping Algorithm.

The analysis is analogous, in particular, all nodes receive all messages $M_w^{\ast }[i]$ from their neighbors $w$, they are able to decode that they are from $w$ by looking at the first $\log n$ of the decoded $M_w^{\ast }[i]$, to identify the starting message by looking at bit $\log n+1$ (and then identifying the last message from $w$ by looking for the last bit 0 at that position before getting 1 at that position), and getting the actual content by looking at the last $\log n$ bits of $M_v^{\ast }[i]$ (and concatenating contents starting from the first identified message from $w$ up to the last piece). The only differences are that now both the code $ℳ$ and block IDs are a constant factor longer, and node $v$ has to wait $ℳ/\log n$ periodic procedures to be able to decode all parts of the original message. Hence, the analog of Theorem 10 can be proved for local broadcast: