𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Broadcasting with linearly bounded transmission faults

✍ Scribed by L. Ga̧sieniec; A. Pelc

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
838 KB
Volume
83
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider broadcasting with a linearly bounded number of transmission failures. For a constant parameter 0 < CI < 1 we assume that at most ai faulty transmissions can occur during the first i time units of the communication process, for every natural number i. Every informed node can transmit information to at most one neighbor in a unit of time. Faulty transmissions have no effect. We investigate worst-case optimal non-adaptive broadcasting time under this fault model. for several communication networks. We show, e.g., that for the n-node line network this time is linear in n, if x < l/2, and exponential otherwise. For the hypercube and the complete graph, broadcasting in the linearly bounded fault model can be performed in time logarithmic in the number of nodes.

📜 SIMILAR VOLUMES

Broadcasting in synchronous networks wit
Broadcasting in synchronous networks with dynamic faults
✍ Chlebus, B. S.; Diks, K.; Pelc, A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 876 KB

The problem of broadcasting in a network is to disseminate information from one node to all other nodes by transmitting it over communication links that connect nodes. We consider the time of broadcasting in the presence of at most k dynamic link failures. If a node knows source information, then in

Graphs with Linearly Bounded Ramsey Numb
Graphs with Linearly Bounded Ramsey Numbers
✍ G.T. Chen; R.H. Schelp 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 439 KB

A graph \(G\) of order \(n\) is \(p\)-arrangeable if its vertices can be ordered as \(v_{1}, v_{2}, \ldots, v_{n}\) such that \(\left|N_{L_{i}}\left(N_{R_{i}}\left(v_{i}\right)\right)\right| \leqslant p\) for each \(1 \leqslant i \leqslant n-1\), where \(L_{i}=\left\{v_{1}, v_{2}, \ldots, v_{i}\righ

Broadcasting with a Bounded Fraction of
Broadcasting with a Bounded Fraction of Faulty Nodes
✍ Leszek Gąsieniec; Andrzej Pelc 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 312 KB

We consider the problem of broadcasting a message from one processor (called the source) to n other processors. We adopt the 1-port half-duplex model in which every processor (node) can communicate with at most one other node in a unit of time and during this period one of the communicating nodes ca