Search Results

We study the reliability of the following simple mechanism for spreading information in a communication network in the presence of random message loss. Initially, some nodes have information that they want to distribute throughout the network. Each node that has received the information tries to broadcast it to all its neighbors. However, due to interference or communication failures, each transmission between two nodes is broken independently with some fixed probability. This transmission mechanism is the basis for the extrema propagation technique, proposed and analyzed in [Carlos Baquero et al., 2012; Baquero et al., 2009; Jacek Cicho{ń} et al., 2012]. Extrema propagation is a simple but powerful method of spreading the extreme values stored by the nodes. In a fully reliable environment, only the number of rounds equal to the network diameter is required for all nodes to be informed. It was shown empirically in [Carlos Baquero et al., 2012] that it also performs well in the presence of link failures and message loss. Extrema propagation is an algorithmic framework that was adopted for designing efficient method for distributed data aggregation, such as estimation of cardinalities, sums, and averages, estimation of data distribution via histograms and random sampling (cf. [Baquero et al., 2009; Karol Gotfryd and Jacek Cichoń, 2023]). In this paper, we propose a formal network model in which random transmission failures occur and analyze the operation time of the extrema propagation technique for any connected network graph. We provide new general probabilistic upper bounds on the number of rounds needed to spread the extreme values that depend only on the number of nodes, the diameter of the network, and the probability of successful transmission. For some special families of graphs, we also derive specific, more accurate estimates. Our theoretical and experimental results confirm the reliability and efficiency of the extrema propagation technique in faulty or noisy environments.