Broadcasting with random faults (Q1111578)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Broadcasting with random faults |
scientific article |
Statements
Broadcasting with random faults (English)
0 references
1988
0 references
A communication network can be modeled by a graph. The problem is to broadcast a message that originates from a given node to the remaining nodes as fast as possible, in the presence of random edge faults. It is shown that if the number of edge faults is at most proportional to the total number of edges, there are networks for which the broadcast can be done in time O(log n), with high probability, where n is the number of nodes in the graph.
0 references
communication network
0 references
message
0 references
random edge faults
0 references
total number of edges
0 references
0 references
