Abstract
We describe a modeling framework and collection of foundational composition results for the study of probabilistic distributed algorithms in synchronous radio networks. Existing results in this setting rely on informal descriptions of the channel behavior and therefore lack easy comparability and are prone to error caused by definition subtleties. Our framework rectifies these issues by providing: (1) a method to precisely describe a radio channel as a probabilistic automaton; (2) a mathematical notion of implementing one channel using another channel, allowing for direct comparisons of channel strengths and a natural decomposition of problems into implementing a more powerful channel and solving the problem on the powerful channel; (3) a mathematical definition of a problem and solving a problem; (4) a pair of composition results that simplify the tasks of proving properties about channel implementation algorithms and combining problems with channel implementations. Our goal is to produce a model streamlined for the needs of the radio network algorithms community.
This work has been support in part by Cisco-Lehman CUNY A New MAC-Layer Paradigm for Mobile Ad-Hoc Networks, AFOSR Award Number FA9550-08-1-0159, NSF Award Number CCF-0726514, and NSF Award Number CNS-0715397.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abramson, N.: The Aloha system - Another approach for computer communications. In: The Proceedings of the Fall Joint Computer Conference, vol. 37, pp. 281–285 (1970)
Roberts, L.G.: Aloha packet system with and without slots and capture. In: ASS Note 8. Advanced Research Projects Agency, Network Information Center, Stanford Research Institute (1972)
Kleinrock, L., Tobagi, F.: Packet switching in radio channels. IEEE Transactions on Communications COM-23, 1400–1416 (1975)
Hajek, B., van Loon, T.: Decentralized dynamic control of a multiaccess broadcast channel. IEEE Transactions on Automation and Control AC-27, 559–569 (1979)
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences 45(1), 104–126 (1992)
Chlamtac, I., Weinstein, O.: The wave expansion approach to broakodcasting in multihop radio networks. IEEE Transactions on Communications 39, 426–433 (1991)
Clementi, A., Monti, A., Silvestri, R.: Round robin is optimal for fault-tolerant broadcasting on wireless networks. Journal of Parallel and Distributed Computing 64(1), 89–96 (2004)
Kowalski, D., Pelc, A.: Broadcasting in undirected ad hoc radio networks. In: The Proceedings of the International Symposium on Principles of Distributed Computing, pp. 73–82 (2003)
Kowalski, D., Pelc, A.: Time of deterministic broadcasting in radio networks with local knowledge. SIAM Journal on Computing 33(4), 870–891 (2004)
Chockler, G., Demirbas, M., Gilbert, S., Lynch, N., Newport, C., Nolte, T.: Consensus and collision detectors in radio networks. Distributed Computing 21, 55–84 (2008)
Wu, S.H., Smolka, S.A., Stark, E.W.: Composition and behaviors of probabilistic I/O automata. In: The Proceedings of the International Conference on Concurrency Theory (1994)
Segala, R.: Modeling and verification of randomized distributed real-time systems. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (June 1995)
Cheung, L.: Reconciling Nondeterministic and Probabilistic Choices. PhD thesis, Radboud University Nijmege (2006)
Newport, C., Lynch, N.: Modeling radio networks. Technical report, MIT CSAIL (2009)
Bar-Yehuda, R., Goldreich, O., Itai, A.: Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection. Distributed Computing 5, 67–71 (1991)
Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C.: Interference-resilient information exchange. In: The Proceedings of the Conference on Computer Communication (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Newport, C., Lynch, N. (2009). Modeling Radio Networks. In: Bravetti, M., Zavattaro, G. (eds) CONCUR 2009 - Concurrency Theory. CONCUR 2009. Lecture Notes in Computer Science, vol 5710. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04081-8_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-04081-8_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04080-1
Online ISBN: 978-3-642-04081-8
eBook Packages: Computer ScienceComputer Science (R0)