Back to Search
Start Over
Fast radio broadcasting with advice
- Source :
- Theoretical Computer Science, Theoretical Computer Science, Elsevier, 2010, 411 (14-15), pp.1544-1557. ⟨10.1016/j.tcs.2010.01.004⟩, Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2008, SIROCCO 2008, Jun 2008, Villars-sur-Ollon, Switzerland. pp.291-305, ⟨10.1007/978-3-540-69355-0_24⟩, Theoretical Computer Science, 2010, 411 (14-15), pp.1544-1557. ⟨10.1016/j.tcs.2010.01.004⟩, Structural Information and Communication Complexity ISBN: 9783540693260, SIROCCO
- Publication Year :
- 2010
- Publisher :
- Elsevier BV, 2010.
-
Abstract
- International audience; We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with {\em advice}. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: $O(n)$ bits of advice are sufficient but $o(n)$ bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
- Subjects :
- Theoretical computer science
General Computer Science
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
02 engineering and technology
Broadcasting
01 natural sciences
Theoretical Computer Science
Broadcasting (networking)
Computer Science::Networking and Internet Architecture
0202 electrical engineering, electronic engineering, information engineering
Advice
Deterministic broadcasting
Computer Science::Information Theory
Distributed algorithm
business.industry
Radio network
Ask price
010201 computation theory & mathematics
Order (business)
Broadcast communication network
020201 artificial intelligence & image processing
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
business
Constant (mathematics)
Radio broadcasting
Algorithm
Advice (complexity)
Computer Science(all)
Computer network
Subjects
Details
- ISBN :
- 978-3-540-69326-0
- ISSN :
- 03043975 and 18792294
- ISBNs :
- 9783540693260
- Volume :
- 411
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....d98bacad2e8ac60203af2b8592d9a8de