Owner: @Alexander Mozeika
Reviewer: 🟢@Marvin Jones 🟢@Álvaro Castro-Castilla
We would like to understand how to reduce probability of a communication failure, i.e. when a message sent by node is “lost” somewhere in the network and not broadcasted. The latter is a main concern as a naive approach of retransmission increases the delay and bandwidth, and reduces anonymity (see ‣). We have identified two approaches with a potential to improve communication failure property. In the first approach, sender node uses multiple independent linear paths, i.e. linear trees, to send a message. However, initial analysis suggests that to reduce communication failure in the latter one must increase the number of communication paths significantly which would have detrimental effect on the bandwidth of a sending node. In the second approach, where sender node is root of a branching tree, bandwidth of a sending node is only weakly affected by the number communication paths.
First, we assume that a fraction of nodes in the network is adversarial and compute the probability of broadcast and anonymity failures for broadcasting on linear trees. We note that if each communication paths has at least one adversarial node then this is considered to be broadcasting failure and if there is at least one path where all nodes are adversarial then this considered to be anonymity failure. Probabilities are parametrised by the fraction of adversarial nodes, number of paths and number of nodes per path. Second, we compute failure probabilities for broadcasting on branching trees. Assuming the same number of paths, we compare results for linear and branching trees and we find that the linear tree design has better broadcast failure properties than the branching tree design, but worse anonymity failure properties. Finally, we assume that in addition to adversarial nodes we have also “faulty” nodes in the network. The latter are unable to relay a messages and their faultiness is a result of some “natural” process. Here we find only quantitative difference with the scenario when only adversarial nodes are considered, but we expect that the model which accounts for “natural” failures to be more realistic.
<aside> 💡
Details of mathematical derivations, with references to literature, and additional numerical results are provided in the Appendix.
</aside>
This document investigates methods to reduce communication failures in network messaging by comparing two primary designs: linear trees and branching trees. The study focuses on minimizing broadcast failures (lost messages) and anonymity failures (privacy breaches) while considering bandwidth constraints.
The analysis uses probabilistic models and recursive equations to compute failure probabilities under adversarial and faulty node conditions. For linear trees, broadcast and anonymity failures are derived based on path length and the number of independent paths. For branching trees, recursive methods determine critical thresholds where failures become inevitable.
A two-variable model is introduced to separate natural faults from adversarial behavior, improving realism. Simulations validate theoretical results, showing trade-offs:
The findings guide design choices based on network priorities (e.g., reliability vs. privacy) and constraints (e.g., node bandwidth). The appendix includes detailed derivations and simulation results.
Communication on Linear Trees. The node sends a message through $K$ communication paths where each path is a linear tree constructed from exactly $L$ nodes.
We assume that a node sends a message through $K$ communication paths where each path is a linear tree constructed from exactly $L$ nodes (see figure above). We assumed that $L\times K$ nodes were sampled (with replacement) from the population of $N$ nodes where $N_F$ nodes are “faulty”. If a path contains at least one faulty node then communication failure occurred. If all $K$ paths have communication failure then broadcast failure occurred.
If nodes in communication paths are sampled with replacement from the $N$ network nodes with $N_F<N$ faulty nodes then the probability that a node is faulty is $q=N_F/N$. The probability of broadcast failure is given by
$$ \mathrm{P}_b=\left[1-(1-q)^L\right]^{K}. $$
We note that in the limit $L\rightarrow\infty$, such that $K/L\rightarrow0$, the probability of broadcast failure $\mathrm{P}_b\rightarrow1$ and in the limit $K\rightarrow\infty$, such that $L/K\rightarrow0$, the probability $\mathrm{P}_b\rightarrow0$.