Rapid Almost-Complete Broadcasting in Faulty Networks
| dc.creator | Královič, Rastislav | |
| dc.creator | Královič, Richard | |
| dc.date | 2007-03-23 | |
| dc.date.accessioned | 2026-07-07T07:53:48Z | |
| dc.date.available | 2026-07-07T07:53:48Z | |
| dc.description | 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 $α$, 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 $α<0.55$) the remaining constant number of vertices can be informed in the same time, i.e. $O(\log n)$. | |
| dc.description | Conference: Sirocco 2007 | |
| dc.identifier | https://arxiv.org/abs/cs/0703122 | |
| dc.identifier | http://arxiv.org/abs/cs/0703122 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/126358 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | C.2.1 | |
| dc.title | Rapid Almost-Complete Broadcasting in Faulty Networks | |
| dc.type | text |