Download now Free registration required
The authors 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. The framework rectifies these issues by providing: a method to precisely describe a radio channel as a probabilistic automaton; a mathematical notion of implementing one channel using another channel; a mathematical definition of a problem and solving a problem; a pair of composition results that simplify the tasks of proving properties about channel implementation algorithms and combining problems with channel implementations.
- Format: PDF
- Size: 293.55 KB