Rapid Almost-Complete Broadcasting in Faulty Networks
<|reference_start|>Rapid Almost-Complete Broadcasting in Faulty Networks: This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The model of fractional dynamic faults with threshold is considered: in every step either a fixed number $T$, or a fraction $\alpha$, of sent messages can be lost depending on which quantity is larger.   As the main result we show that in complete graphs and hypercubes it is possible to inform all but a constant number of vertices, exhibiting only a logarithmic slowdown, i.e. in time $O(D\log n)$ where $D$ is the diameter of the network and $n$ is the number of vertices.   Moreover, for complete graphs under some additional conditions (sense of direction, or $\alpha<0.55$) the remaining constant number of vertices can be informed in the same time, i.e. $O(\log n)$.<|reference_end|>
@article{královič2007rapid,
    title={Rapid Almost-Complete Broadcasting in Faulty Networks},
    author={Rastislav Kr'aloviv{c}, Richard Kr'aloviv{c}},
    journal={arXiv preprint arXiv:cs/0703122},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0703122},
    primaryClass={cs.DC}
}