Back to Search
Start Over
Communication algorithms with advice
- Source :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, 2010, 76 (3-4), pp.222-232. ⟨10.1016/j.jcss.2009.07.002⟩, Journal of Computer and System Sciences, Elsevier, 2010, 76 (3-4), pp.222-232. ⟨10.1016/j.jcss.2009.07.002⟩
- Publication Year :
- 2010
- Publisher :
- HAL CCSD, 2010.
-
Abstract
- International audience; We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is {\em quantitative}: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the {\em wakeup} with a linear number of messages in a $n$-node network, is $\Theta (n \log n)$, while the {\em broadcast} with a linear number of messages can be achieved with advice of size $O(n)$. We also show that the latter size of advice is almost optimal: no advice of size $o(n)$ can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.
- Subjects :
- Computer Networks and Communications
Distributed computing
Message complexity
Network
0102 computer and information sciences
02 engineering and technology
Broadcasting
01 natural sciences
Graph
Theoretical Computer Science
0202 electrical engineering, electronic engineering, information engineering
Size of advice
Dissemination
Mathematics
Linear number
business.industry
Applied Mathematics
Telecommunications network
Algorithm
Computational Theory and Mathematics
010201 computation theory & mathematics
Broadcast communication network
Graph (abstract data type)
020201 artificial intelligence & image processing
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
business
Advice (complexity)
Wakeup
Subjects
Details
- Language :
- English
- ISSN :
- 00220000 and 10902724
- Database :
- OpenAIRE
- Journal :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, 2010, 76 (3-4), pp.222-232. ⟨10.1016/j.jcss.2009.07.002⟩, Journal of Computer and System Sciences, Elsevier, 2010, 76 (3-4), pp.222-232. ⟨10.1016/j.jcss.2009.07.002⟩
- Accession number :
- edsair.doi.dedup.....8fd9d6750657294a5a2a6cd8bdfa991e