Broadcasting with random faults (Q1111578)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Broadcasting with random faults |
scientific article; zbMATH DE number 4075132
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Broadcasting with random faults |
scientific article; zbMATH DE number 4075132 |
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
