Over the last decades, wireless communication found many applications and has transformed technology. On the theoretical side, wireless systems were studied by numerous works, many of which consider the single-hop radio networks (SHRN) model of Chlamtac and Kutten [7], which abstracts a simple broadcast channel. The classical model of SHRN assumes that the communication is noiseless, guaranteeing that (if no "collisions" occur) the message broadcast in a round will be received correctly by all the parties. In contrast, recently, Censor-Hillel, Haeupler, Hershkowitz, and Zuzic [6],
Protecting Single-Hop Radio Networks from Message Drops initiated the study of the radio networks model under stochastic message drops (a.k.a, stochastic erasures). In their model, each party only gets the message that was broadcast with probability 1 -ϵ, independently, for some small constant ϵ. Otherwise, the round is "erased" for this party, meaning that it is received as a silent round, as if nothing was broadcast.
While the (noiseless) radio networks model is, by now, mostly well understood, and while noise is inherent in almost all communication systems, the relative power of noisy radio networks is far less explored. In this work we study the power of the SHRN model under the message drop noise of [6].
Our main result is that the model of SHRN with message drops is as powerful as that of (noiseless) SHRN, in the sense that any protocol that was designed to work over the latter can be made to work over the former with a small overhead to the communication. An informal statement of our main result is in Theorem 1 (see Theorem 2 for a formal statement, the assumed model is discussed next).
▶ Theorem 1. Let n ∈ N be the number of participants, ϵ ∈ (0, 1) be the noise rate, and Γ be a non-empty alphabet set. For any protocol Π of length T ≤ 2 n over the (n, Γ)-broadcast channel, there is a protocol Π ′ with O(T ) rounds over the (n, ϵ, Γ)-noisy broadcast channel that simulates 1 Π, and errs with probability polynomially small in T .
We mention that our scheme works for protocols of length T ≤ 2 n , as, if T is much larger than 2 n , there will be rounds where the messages received by all parties are erased (see Section 2.4). We also mention that our scheme uses a combinatorial building block called a tree code (see Section 2.2), and like other works that use tree codes, it is not computationally efficient, as no efficient tree code construction is known. Whether or not longer protocols can be handled with constant rate, and whether computationally efficient schemes are possible, are two intriguing questions we leave open.
We next overview the noise model of [6] used by Theorem 1 (for formal definitions, see Section 3): A protocol over the (n, ϵ, Γ)-noisy broadcast channel is a communication protocol between n communicating parties that proceeds in synchronous rounds. In each round, each party can decide to either broadcast a symbol from Γ or stay silent. If more than one party broadcasts in a given round (a collision), or none of the parties broadcast (a silent round), then the "⊥" symbol is received by all the parties 2 . Otherwise, exactly one of the parties broadcasts a symbol, and each party receives the broadcast symbol with probability 1 -ϵ, and ⊥ with probability ϵ, independently 3 . A protocol over the (n, Γ)-broadcast channel is a protocol over the (n, 0, Γ)-noisy broadcast channel, i.e., one where erasures do not occur. 1 By "Π ′ that simulates Π", we mean that a transcript for Π can be retrieved from a transcript for Π ′ , see Theorem 2. 2 The name collision-as-silence is because the same ⊥ symbol is received in both collision and silent rounds. This model is, perhaps, the most common model in the literature. Another very popular model is the collision detection model, where collision and silence are perceived as different symbols. Theorem 1 is stated for the collision-as-silence model, but applies to the collision detection model as well. 3 Modeling erasures as the same symbol as collisions/silences only makes our result stronger. As explained in Section 2.3, this makes our erasure model closer to the corruption model.
The corruption noise model
One of the original motivations for our work was exploring the power of the SHRN model under stochastic corruption noise, a noise model that received quite a bit of attention over the last few years (see, e.g., [10,11]). In this model, in every round, each party receives the correct symbol output by the channel with probability 1 -ϵ, and receives one of the other symbols with probability ϵ, independently 4 . Observe that protecting protocols against corruptions is at least as hard as protecting them against message drops.
An encouraging piece of evidence, indicating that it may be possible to make SHRN protocols resilient to corruption noise with small overhead, was recently given by Efremenko, Kol, and Saxena [10], who designed such a scheme for a restricted set of protocols called non-adaptive protocols. Still, our initial belief was that such a scheme is impossible in the general case of adaptive protocols. Non-adaptive (a.k.a, oblivious or static) protocols are a restricted set of protocols where it is known ahead of time which party broadcasts in what round, while adaptive protocols allow the parties to decide whether or not they wish to broadcast at a given round based on their input and their received transcript up until the current round.
While non-adaptive protocols are useful, they do not fully utilize the power of the wireless channel, and communication-efficient protocols for some central problems are, in fact, adaptive (e.g., the celebrated Decay protocol for computing the size of a network [3]). This additional power of adaptive protocols is what makes their conversion to noise-resilient ones more challenging, and, indeed, the [10] scheme may fail when applied to adaptive protocols Π.
When starting this project, we identified two inherent reasons (see Section 2.1) for the failure of [10] when applied to adaptive protocols and hoped to show that these must lead to a blowup of Ω(log n) in the communication. As most interactive coding lower bounds for multi-party protocols also extend to the message drop model (e.g., [4,11]), as a first step, we attempted to convince ourselves that no constant rate simulation scheme exists even for the SHRN model with message drop noise.
To our surprise, we were able to overcome both problems in the message drop model and design a scheme that also works for adaptive protocols. As far as we know, the scheme converting noiseless to noise-resilient protocols we construct in our proof of Theorem 1 is the first constant overhead scheme that handles adaptive protocols in any multi-party setting.
We are still very interested in the more general question of making SHRN protocols resilient to corruption noise, as we believe it is a basic and "clean" coding question. Our result can be interpreted as saying that (at least for protocols that are not extremely long) either a high-rate scheme is possible or a novel lower bound approach is required.
Interactive coding. Interactive error correcting codes encode interactive communication protocols designed to work over noiseless channels to protocols that also work over noisy channels. The study of interactive codes was initiated by a seminal paper of Schulman [25] that considered two-party protocols, which was also the topic of many follow-up works.
Interactive codes for multi-party distributed channels received quite a bit of attention over the last few years. These include codes for peer-to-peer channels [24,21,20,1,4,16,17] and codes for various wireless channels [5,10,6,11,12,2,8]. Coding for wireless systems. The models of wireless communication considered in the context of noise-resilience differ on a few axes. The first axis is the adaptivity of the simulation protocol: in some papers the target simulation protocol is allowed to be adaptive and in others it must be non-adaptive. (Of course, if the noiseless protocols considered are adaptive, the simulation needs to be adaptive. However, simulations of non-adaptive noiseless protocols by adaptive noise-resilient protocols have been considered). The second axis is whether single or multi-hop networks are considered. Finally, the last axis is whether the noise is modeled as stochastic erasures (message drops) or stochastic corruptions (change of symbols). Non-adaptive simulations. The study of noise in wireless systems can be traced back to [14] that answered an open problem of [15] by giving an O(n log log n) length communication protocol for the bit exchange problem (all n parties have an input bit and all parties want to know the input of all the other parties). The underlying model was the noisy broadcast channel, which is a non-adaptive, single-hop model with corruption errors. A matching lower bound for this problem was later given by [18]. The communication complexity of other specific n-bit functions, like the OR, majority, and parity functions, were studied under related models by [27,22,13,23,18]. The non-adaptive single-hop model was studied under erasure noise by [19], where an O(n log * n) protocol is given for the bit exchange problem, breaking the Ω(n log log n) lower bound proved for corruption errors.
The general case of simulating any non-adaptive protocol by an noise resilient nonadaptive protocol was very recently studied by [9]. Their main result is that, for protocols of length polynomial in n, such a simulation requires Θ( √ log n) multiplicative overhead in the communication complexity. Adaptive simulations. The work of [10] gave a scheme for converting any non-adaptive noiseless protocol to an adaptive noise-resilient one with only a constant multiplicative overhead, over a single-hop network with corruption errors (in particular, implying an adaptive noise-resilient bit exchange protocol with O(n) communication). Multi-hop radio networks. The work of [10] (and our current work) consider the setting where the parties are connected in a clique (a single-hop network), as it is assumed that when a party transmits, all other parties can hear the transmission. As mentioned above, this topology is the single most extensively studied, as it represents the simplest broadcast channel. However, wireless systems can have arbitrary topologies. In contrast to [10], in [11] it is shown that such a scheme is impossible over general multi-hop networks, where each of the n communicating parties is associated with a node in the graph, and when a party broadcasts, its message is only received by its neighbors in the graph (if there are no collisions). Specifically, [11] shows that in some networks, the cost of noise-resilience is Ω(log n), even for simulating non-adaptive protocols by adaptive protocols. A matching O(log n)-overhead scheme for converting any noiseless protocol to a noise resilient one over any network is also given by [11].
The recent work of [6], considered general radio networks under message drop noise. They show that any protocol over any network can be converted to a noise resilient one with a multiplicative O(∆ log 2 ∆) overhead to the communication, where ∆ is the maximum degree of a node in the network. For the special case in which the noiseless protocol we wish to convert is non-adaptive, a scheme with an improved overhead of poly(log ∆, log log n) is shown [6]. For networks with small ∆, this implies an efficient simulation of noiseless protocols. However, for networks with large ∆, the [6] simulation can have a huge overhead. This is not for no reason, as the Ω(log n) lower bound of [11] mentioned above also applies to the message drop noise and implies that there exist network topologies with large ∆ for which an Ω(log ∆) overhead is necessary. Our result shows for the important single-hop topology, these communication overheads can be avoided altogether.
In this section, we give a detailed sketch of our protocol.
As mentioned in Section 1.2, one of the main motivations for our work was studying the rate of interactive codes over the SHRN model with corruptions. The restricted case where the protocol Π to be simulated is non-adaptive was studied by [10], but their scheme fails for adaptive protocols. We next explain the inherent reasons for this failure and then outline our solutions for erasure noise.
The [10] scheme utilizes the rewind-if-error framework, which was initially designed for the two-party setting [25]. Rewind-if-error coding schemes consist of many iterations, where each iteration consists of two phases: a simulation phase, where a small number of rounds of the noiseless protocol Π are executed, and a consistency check phase where the parties attempt to check if they have the same received transcript or whether an error occurred (e.g., by comparing hashes of their received transcripts). If the check phase passes, parties continue the simulation, otherwise they rewind and re-simulate the last few rounds.
A careful examination of the [10] scheme shows that it breaks down when applied to adaptive protocols for the following two fundamental reasons: Repeated rewinds. The first problem is that with noise rate ϵ, we should expect about ϵn parties to experience message drops in every round of the simulation phase. Since ϵ is constant, ϵn ≫ 1. This implies that the consistency check phase will almost always fail and trigger a rewind, and no progress will ever be made. This situation can be trivially corrected by repeating each broadcast symbol O(log n) times, and thereby effectively reducing the noise rate to less than 1 n . However, this is unaffordable for a constant overhead simulation. We note that this repeated rewinds problem is avoided by [10] as, although the total number of parties n is large, the assumed non-adaptivity of Π can be used to determine a small subset S of parties that critically need to know the simulated transcript. These are the parties that will broadcast in the rounds immediately following the current one. The remaining parties broadcast later in the future and therefore have more time to decode the symbol broadcast in the current round. Then, [10] show that it is enough to make sure that parties in S are not experiencing message drops, which helps reduce overhead down to a constant. Since in the adaptive case, it is possible that any of the n parties broadcasts next, this approach cannot be implemented. Message certification. An even bigger problem we encounter when attempting to run the [10] scheme on adaptive protocols is that it crucially uses the fact that the symbol received from the channel in every round can be certified by at least one of the parties: Since Π is
Protecting Single-Hop Radio Networks from Message Drops assumed to be non-adaptive, it can also be assumed that a single party broadcasts in every round (collisions and silences can be eliminated ahead of time). Furthermore, this party (and all other parties) knows that it is the only one to broadcast. Therefore, if party i broadcast the symbol σ in round t of Π and some claimed transcript of Π has a symbol different from σ in round t, party i can "object" to this transcript to trigger a rewind.
The adaptive setting is different though. Consider, for example, the case where Π is adaptive and in some rounds has multiple parties broadcasting simultaneously, causing a collision. We call such collisions intended collisions. Suppose, however, that in round t, party i was the only one to broadcast, but the claimed transcript for Π has ⊥ in round t.
Since party i may no longer know that it is the only one to broadcast in this round, it may deem it possible that others have broadcast as well, leading to an intended collision, and thus will not object. The other, silent, parties may not object either as they may think that this is a collision or a silent round.
To explain how our scheme handles the first (and easier) repeated rewinds problem described above, consider the following protocol Π that exhibits it (the second, message certification problem, does not occur): The protocol is played over an underlying complete binary tree of depth T < 2 n . Each of the n parties gets as input, one symbol b v ∈ {0, 1, ⋆} for each vertex v in the tree, where the inputs are sampled as follows: First, we select one of the root-to-leaf paths in the tree uniformly at random and call it the "correct path". We assign each of the vertices v on this path to exactly one of the n parties uniformly at random. Here, by "assigning vertex v to party i" we mean that party i gets a bit b v ∈ {0, 1} for vertex v. If vertex v is not assigned to party i, party i gets b v = ⋆. Additionally, each of the vertices v outside this path is assigned to many parties, say, to a set of n 2 parties selected uniformly at random.
In the noiseless protocol Π, all parties start from the root of the tree, and, upon reaching node v, a party that was not assigned v (has b v = ⋆) stays silent, and a party that was assigned v broadcasts its bit b v . Since each of the vertices on the correct path was assigned to exactly one party, exactly one party broadcasts a bit, and all parties then progress to the child of v indicated by this bit (that is, if 0 is broadcast they update v to be the left child of v, otherwise to the right child). This is done until a leaf is reached, which is also the output of the protocol.
Observe that since on every vertex of the correct path a single party broadcasts (and the parties know that this is the case), the message certification problem does not occur. However, since any of the n parties may potentially be the one to broadcast in the next round, the repeated rewinds problem occurs.
To avoid repeated rewinds in our simulation of Π, we make sure that parties never go off the correct path (i.e., no party ever reaches a vertex v that is not on the correct path) by guaranteeing that the parties never broadcast when it is not their turn to broadcast. To this end, our policy for the parties is that they always play it safe and never broadcast unless they know the entire transcript so far.
Of course, it may be the case that the received transcript of the party who should broadcast next contains erasures, causing it to refrain from broadcasting. Since no other party broadcasts, this will be a silent round and all parties will receive ⊥. Upon receiving ⊥, parties do not update their current node v in the tree. Thus, no progress is made in this round, where progress is measured as the number of steps taken on the correct path (the depth of v in the tree). Note, however, that indeed in this protocol parties never go off the correct path.
To allow progress to resume, we need to ensure that the erasures in the transcript of the party that should broadcast next are resolved (hopefully, within a few rounds). To this end, we pick one of the parties (say, the first party) to be the leader. After every communication round, this leader re-broadcasts the symbol it received from the channel on a tree code [26]. A tree code is essentially an error correcting code that can be computed "online" and ensures that the messages sent until round t will eventually be decoded correctly, where the probability of correct decoding greatly increases with the number of rounds that have passed since round t. Thus, parties that suffer an erasure will be able to recover the missing symbol over the next few iterations by observing what was received from the leader on the tree code. This means that, while progress may pause, it will resume within a few rounds.
A harder-to-simulate protocol Π Now let us address the second (and more severe) problem of message certification. Observe that in our simulation of the above protocol Π we did not encounter this problem. The reason is that on every vertex on the correct path a single party is scheduled to broadcast. We now consider the more general case where some of the vertices on the correct path are given to more than one party. For concreteness, say that a quarter of the vertices v on the correct path are given to exactly 2 parties, and an additional quarter is given to n 2 parties (that is, in total, there is an intended collision on half of the vertices on the correct path). Additionally, assume that the underlying tree is ternary (instead of binary), and the children of every non-leaf vertex are labeled by {0, 1, ⊥}. In a case of an intended collision, the ⊥ child of the current vertex should be taken.
Observe that the play-it-safe simulation protocol we had before has to change: When designing it, we assumed that there are no collisions on the correct path, thus progress was paused when a ⊥ symbol was received (that is, the parties did not update their current vertex v in the tree). As intended collisions are now possible, we ask that, upon receiving ⊥, the parties update v to the ⊥ child of v.
Observe however, that since the parties are unable to differentiate intended collisions from erasures, as both are received as ⊥, they may go off the correct path and will need to eventually detect the error and rewind. We note that working in the erasure model typically means that a party that does not have the correct transcript knows that it does not have the correct transcript. However, as is evident here, this reasoning does not apply to our erasure model. In this sense, our model is closer to the corruptions model than other erasure models.
In our simulation, parties can go off the correct path in round t if the party that was supposed to broadcast in round t (say party i) did not do so as it did not know the full transcript so far. By not broadcasting, party i potentially converts the output of the channel in round t from a bit to ⊥ (this happens when party i was supposed to be the only one I C A L P 2 0 2 3
Protecting Single-Hop Radio Networks from Message Drops to broadcast) or from ⊥ to a bit (this happens when one additional party was supposed to broadcast). Recall that, owing to the usage of a tree code, party i eventually learns the complete transcript until the missed round t. When this happens, we can have party i object in the next consistency check in order to trigger a rewind. However, because the rate of erasures is constant and parties broadcast very often (recall that a quarter of the vertices on the correct path are given to n 2 parties), there are likely to be too many missed rounds and such objections will once again cause repeated rewinds.
To implement a rewind-if-error mechanism without repeated rewinds, we observe that rewinds are required only when the output symbol was changed due to party i (a party that was scheduled to broadcast in round t) not broadcasting in round t. Note that this only happens if the output symbol in round t is not a collision. In this case, we say that party i is criticalfoot_1 for round t. We use the policy that party i only objects to round t if it is critical to round tfoot_2 . Note that this policy does not cause repeated rewinds: if many parties were supposed to broadcast in round t, none of them is critical (this round will be a collision round even if one of these parties will not broadcast). Otherwise, if few parties were supposed to broadcast in round t, then there is a good chance that round t is not erased in any of the received transcripts of these parties.
To be able to implement the policy, party i needs to know if it was critical to the round t that it missed. Observe that if round t was a collision round even without party i broadcasting, then party i is not critical for round t, and no rewind is necessary. It is not hard to see that this is in fact the only case where a party who missed a round is not critical for this round. This means that testing criticality boils down to the ability to differentiate a collision round from a silent round.
To differentiate collision rounds from silent rounds, we use a known radio networks collision detection trick. Assume for the purposes of this sketch that there is some player, say the leader, that is known to not broadcast in this round 7 . We "run" the round twice, once in a black-box way (without the leader broadcasting), and once again while having the leader broadcast. If the round was a silent round, then the parties receive a ⊥ in the first run, and a bit (non-⊥ symbol) in the second, while if the round was a collision, they will receive ⊥ in both the runs. As they receive a different combination of symbols, they can distinguish between collisions and silencesfoot_4 . Note that the argument above assumes sender collision-detection, i.e., the parties that are transmitting also receive a symbol in that round. However, this assumption is not needed, see Footnote 10 and Remark 3.
Now consider the situation where the leader receives a bit and re-transmits it, but, due to erasures, some parties receive a ⊥. By updating their current node v using this ⊥, these parties may fall off the correct path. As mentioned in Section 2.3, this type of error occurs as the channel does not distinguish between erasures and collisions/silences.
To circumvent this problem, we convert our collision-as-silence-as-erasures channel to a collision-as-silence-not-as-erasures channel. This is done by having the leader broadcast a special symbolfoot_5 other than 0, 1, and ⊥, in the case it receives ⊥. As the other parties know that the leader never broadcasts ⊥, they can deduce that any ⊥ they may receive from it is due to an erasure. On the other hand, if they receive the special symbol, they can conclude that the round is a collision/silence.
The simulation scheme we discuss so far is in the rewind-if-error framework. In this sketch we attempted to show that whenever the parties go off the correct path due to erasures, at least one of the parties is able to detect the problem and object in the next check phase.
To implement a check phase, we ask parties that wish to object to broadcast a bit (say, 1), and ask all other parties to keep silent. Then, the collision detection subroutine described above allows the parties to tell whether 0, 1, or more than 1 parties were broadcasting, and thus also allows them to tell whether there exists an objecting party and a rewind should take place.
In this paper, we study the broadcast channel with random erasures, assuming the collisionas-silence-as-erasures model. To define the model and throughout this paper, we will use the following notation. For a string s, we shall use |s| to denote the length of s. For i ∈ [|s|], let s i denote the i th coordinate of s and s <i , s ≤i denote the prefix of the first i -1 and i coordinates of s, respectively. For two strings s, t over the same alphabet, denote by ∆(s, t) the Hamming distance between s and t, by LCP(s, t) the longest common prefix of the strings s and t, and by s∥t the concatenation of s and t. The (n, ϵ, Γ)-noisy broadcast channel is defined by a number n ≥ 0 of parties, an error parameter ϵ > 0, and an alphabet set Γ satisfying |Γ| > 1. We shall refer to player 1 as the leader Ld, use ⊥ to denote a special symbol not in Γ (this symbol will represent collisions, silences, and deletions), and define Γ c = Γ ∪ {⊥}. We also define the (n, Γ)-broadcast channel to be the noiseless version of this channel, i.e., when ϵ = 0.
A (deterministic) protocol Π over the (n, ϵ, Γ)-noisy broadcast channel is defined as:
Here, T = ∥Π∥ is the number of rounds (or the length) of the protocol, X i is the input space for player i, Y is the output space of the protocol, M i j :
→ Γ c is the function player i uses to determine what message to send in round j, and out : Γ T c → Y is the function the leader uses to determine the output from its received transcript. As usual, we define a randomized protocol to be a distribution over (deterministic) protocols.
The protocol Π starts with all players i ∈ [n] having an input x i ∈ X i and proceeds in T rounds, maintaining the invariant that before round j, for all j ∈ [T ], all players i have a transcript
. In round j, player i broadcasts
Now, the symbol π i j received by player i in round j equals combine z 1 , • • • , z n , with probability 1 -ϵ, and equals ⊥, with probability ϵ, independently for all i ∈ [n] and j ∈ [T ]. 10In the latter case, we say the message to player i in round j was erased by the noise. Player i appends π i j to π i <j to get a transcript π i ≤j and continues the execution of the protocol. After T rounds, the leader outputs Π Ld (X) = out(π Ld ≤T ) ∈ Y. (Note that using only O(max{T, log n}) additional transmissions, the leader can communicate the output to all the other parties in a reliable manner by encoding with a standard error correcting code.) We shall sometimes omit Ld when the channel is noiseless, as in this case, all the players receive the same transcript and can compute the output.
We formalize Theorem 1 as Theorem 2 (below). (Note that by having the parties repeat every round of the original protocol Π constantly many times and taking the majority of the outputs, we get the channel noise rate to be smaller than 10 -10 ).
▶ Theorem 2 (Formal Version of Theorem 1). There exists a constant C such that the following holds: Fix ϵ = 10 -10 , n > 0, an alphabet set Γ satisfying |Γ| > 1. For any protocol Π of length T ≤ 2 n in the (n, Γ)-broadcast channel, there is a protocol Π ′ over the (n, ϵ, Γ)-noisy broadcast channel, with ∥Π ′ ∥ ≤ CT , and such that for all inputs X = x 1 , x 2 , • • • , x n for the players, we have:
where the probability is over the noise in the channel.
We note that when n is small, so is T , so Π can be simulated by simply repeating each round sufficiently many times. As such, without loss of generality, we may assume that n is large.
The proof of Theorem 2 spans the rest of this paper. In this section we give the simulation protocol Π ′ , and in Appendix B we give its analysis.
Let n, ϵ, Γ be as in the theorem statement and assume without loss of generality that Γ = [|Γ|]. Fix a protocol Π. Observe that fixing Π also fixes T,
, etc. as in Equation ( 1). As a randomized protocol is simply a distribution over deterministic protocols, we can assume without loss of generality, that the protocol Π is deterministic. We also assume without loss of generality that the output of Π is just its transcript. In order to define the protocol Π ′ , we first set up some notation.
Define the sets P Ld = [n] (all parties including the leader), and P = {2, 3, . . . , n} (all parties excluding the leader).
As motivated in Section 2, our protocol shall implicitly implement a collision detection model, having two separate symbols for collisions and silences. We shall use a special symbol ⊥ C / ∈ Γ to denote a collision and ⊥ S / ∈ Γ to denote a silence. Define Γ cs = Γ ∪ {⊥ C , ⊥ S }. Additionally let R / ∈ Γ be a special symbol indicating that the leader wants to rewind a round, and denote by Γ csr = Γ cs ∪ {R}. We shall treat both ⊥ C and ⊥ S as ⊥ in our protocol, and output a string in Γ T cs . We also redefine the message functions, M i j , to take inputs from Γ j-1 cs instead of Γ j-1 c , treating both ⊥ C and ⊥ S as ⊥, e.g., M i j (x i , ⊥ C ∥⊥ S ) = M i j (x i , ⊥∥⊥). For simplicity, we shall pad the protocol Π with ⊥ infinitely many times and correspondingly define, for all i ∈ [n], j > T , the value M i j (•, •) = ⊥. Our protocol will use a (Γ csr , Γ, R TC , 0.4)-tree code TC, where R TC ≥ max 10 5 , 10R is a sufficiently large constant and R is as promised by Theorem 5. This tree code will only be written to by the leader, and will be used to log the leader's simulated transcript. In our protocol, when we say the leader writes s ∈ Γ csr to the tree code, we mean that it computes and broadcasts TC(ρ∥s), where ρ is the string of all the symbols it wrote to the tree code before the current s. We shall also use D-TC to denote the tree code decoding function from Definition 6.
We give a formal description of our protocol Π ′ in Algorithm 1.
▶ Remark 3. Recall from Footnote 10 that we are assuming a broadcast model with sender collision-detection. In other words, we assume that players that are talking (broadcasting a symbol other than ⊥) also receive an output symbol from the channel. We next claim that our simulation protocol Π ′ can be made to work over the channel with no sender collision-detection, that is, when only players that listen (broadcast ⊥), get the output symbol from the channel. Input: Each party i ∈ P Ld holds an input x i ∈ X i . Output: The leader outputs π ∈ Γ T cs , that represents a transcript for Π. 1: for t ∈ 10 5 T do 2:
Each player i ∈ P Ld runs parse on τ i to get output π i , r i , where: τ i , for i ∈ P, is the concatenation of all messages received by player i at Line 8 up to this point (possibly none). τ Ld is the concatenation of all messages broadcast (as opposed to received) by the leader at Line 8 up to this point (possibly none).
3:
The parties run detect-collisions, using z i as the input for player i ∈ P. Let w i be the output for player i ∈ P Ld .
The leader represents w Ld ∈ Γ cs as an element of Γ 4 and broadcasts it in 4 rounds.
Let wi be the symbol decoded by player i ∈ P, or ⊥ if the player fails to decode.
Each player i ∈ P sets a flag e i ∈ {1, ⊥} as follows:
The parties run detect-collisions, using e i as the input for player i ∈ P. Let e Ld be the output for the leader.
The leader writes s Ld ∈ Γ csr to the tree code, where
9: end for 10: The leader runs parse on τ Ld to get output π Ld , r Ld , where τ Ld is as in Line 2. The leader then outputs π Ld ≤T .
Algorithm 2 Algorithm detect-collisions, that distinguishes between collisions and silence.
Input: Each player i ∈ P has a symbol z i ∈ Γ c that it wishes to broadcast in this round.
Output: Each player i ∈ P Ld outputs a guess w i ∈ Γ cs for the combined symbol. 11: In one round of communication, each player i ∈ P broadcasts z i and the leader broadcasts ⊥. Let u i be the symbol heard by player i ∈ P Ld . 12: In one round of communication, each player i ∈ P broadcasts z i and leader broadcasts 1.
Let u i be the symbol heard by player i ∈ P Ld . 13: Each player i ∈ P Ld returns w i , where
This property means that we can make several very useful claims, which we use throughout the rest of this paper.
▶ Lemma 8. For all t ∈ [T ′ ], all i ∈ [n], and all instantiations N of N,
As a player i ∈ [n] sets z i as a deterministic function of x i and π i at Line 3, we also directly get the following corollary.
▶ Corollary 9. For all t ∈ [T ′ ], all i ∈ [n], and all instantiations N of N,
Likewise, we can also analyse the behaviour of Algorithm 2, during the two calls at Line 4 and Line 7, to see the way the noise can affect the executions of this algorithm. ▶ Lemma 10. For all t ∈ [T ′ ], all i ∈ [n], and all instantiations N of N,
▶ Lemma 11. For t ∈ [T ′ ] and any instantiation N of N, we have:
We also show some properties of the symbol s Ld , and how it relates to the transcript that players maintain. ▶ Lemma 12. For all t ∈ [T ′ ] and any instantiation N of N such that e Ld t (N ) = ⊥ S and w Ld t (N ) = combine-CD ⊥, z 2 t (N ), . . . , z n t (N ) , we have
We also analyse the behaviour of Algorithm 3, and in particular how π and ρ behave in that algorithm. ▶ Lemma 13. For all t ∈ [T ′ ] and all instantiations N of N,
Next, we define and analyze some events based on the variable N. The event E wo t,r
For t ∈ [T ′ ], r ∈ [R ′ ], the event E wo t,r occurs if the communication in round r in iteration t is erased for a significant fraction of the players (it is "wiped out"). Formally, we have:
The event
the event E dc t,i occurs if the communication in the first execution of detect-collisions, i.e., at least one of rounds 1 and 2, in iteration t is erased for player i. Formally, we have:
The event E or t For t ∈ [T ′ ], we define the event E or t to occur if the communication in the second execution of detect-collisions (which effectively computes a logical OR of the e i 's), i.e., in at least one of rounds 7 and 8 in iteration t is erased for the leader. Formally, we have: E or t := (∃r ∈ {7, 8} : N t,r,Ld = 1).
The event E tc t ′ ,t,i
For 0 ≤ t ′ < t ≤ T ′ and i ∈ [n], define the following event concerning the rounds 9 to R ′ in each iteration, i.e., the rounds where the leader broadcasts on the tree code:
We now define sets of "bad" iterations for a given execution. Intuitively, these are iterations where our protocol does not make progress. For an instantiation N of N, we have:
▶ Lemma 15. It holds that:
1. Pr(B wo (N) ̸ = ∅) ≤ 2.25 -n .
2. Pr B dc (N) ∪ B or (N) ≥ T ′ 50 ≤ e -T ′ 100 .
We note that our assumption that T ≤ 2 n is only used in Item 1 of Lemma 15.
We now define and show results about players "critical" to the protocol, i.e., those needed to make sure we make progress in our simulation. For a set S of integers and an integer k define S ≤k to be the set consisting of the k smallest elements of S. If |S| ≤ k, we define S ≤k = S. For a transcript π ∈ Γ * cs , we define the set S(π) to be the set of all non-leader players who would broadcast in the noiseless protocol when their received transcript is π. Formally,
▶ Definition 16 (Critical Players). For π ∈ Γ * cs , we define the set of players that are π-critical as Crit(π) = S(LCP(π, Π)) ≤2 .
We note that this definition is made for analysis purposes and no single player can necessarily compute the set Crit(•).
Next, we define the set of possible augmented transcripts and bad intervals.
▶ Definition 17. For 0 ≤ t ′ ≤ t ≤ T ′ and an instantiation N ≤t ′ of N ≤t ′ , define the set:
▶ Definition 18. Let N be an instantiation of N. We define B † (N ) to be the set of all intervals (t ′ , t] satisfying 0 ≤ t ′ < t ≤ T ′ for which there exists π ∈ Aug t (N ≤t ′ ) and i ∈ Crit(π) such that E tc t ′ ,t,i occurs when N = N . We also define: To finish this subsection, we show that B(•) has all the iterations where a critical player fails to decode the tree code.
▶ Lemma 20. For any instantiation N of N and all t / ∈ B(N ), for all i ∈ Crit(π Ld t (N )), we have π i t (N ) = π Ld t (N ).
We now define the potential function that we shall use in the analysis. For t ∈ {0} ∪ [T ′ ] and an instantiation N of N, we define:
Our definition clearly implies Φ 0 (N ) = 0 and Φ t (N ) ≤ LCP π Ld t+1 (N ), Π for all N . Moreover, as either one symbol is appended to or removed from the end of π Ld in every iteration, we have that Φ t (N ) ≥ Φ t-1 (N ) -1 for all N and t ∈ [T ′ ]. In Lemma 25 we will now show that if t is not in one of the bad sets defined above, then the potential increases by at least 1. But first, we state some helpful lemmas.
Care needs to be taken while defining an error model for corruptions, as some definitions may allow for signaling-based protocols[20].
We mention that this definition differs slightly from the technical sections, but implements a similar idea.
Observe that a priori, it is not clear if the parties know they are critical. We deal with this later in this section. We also note that the notion of critical parties does not appear in the algorithm description and is used only in the analysis.
This assumption can easily be removed by, e.g, running the round an extra time where only the leader will broadcast.
We note that noise can erase the symbol broadcast by the leader in the second run and effectively erase a silence out to look like a collision. We distinguish between these and regular collisions using the method described in Section 2.4.
The actual proof does not require an additional symbol. Rather, we encode every symbol by two symbols.
We remark that in the literature (e.g.,[6]), the broadcast channel (single-hop radio networks) is often defined such that a player that broadcasts a symbol (other than ⊥) in a round does not receive any symbol from the channel in that round (in other words, there is no sender collision-detection). However, for simplicity of presentation, in this paper we assume this stronger model. We explain how to make our protocol work with no sender collision-detection in Remark 3.
We stress that Line 25 still uses τ i and not τ Ld .