A simple network of nodes moving on the circle
Authors
Cheliotis, D
Kontoyiannis, I
Loulakis, M
Toumpis, S
Publication Date
2020Journal Title
Random Structures and Algorithms
ISSN
1042-9832
Publisher
Wiley
Volume
57
Issue
2
Pages
317-338
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Cheliotis, D., Kontoyiannis, I., Loulakis, M., & Toumpis, S. (2020). A simple network of nodes moving on the circle. Random Structures and Algorithms, 57 (2), 317-338. https://doi.org/10.1002/rsa.20932
Abstract
Two simple Markov processes are examined, one in discrete and one in
continuous time, arising from idealized versions of a transmission protocol for
mobile, delay-tolerant networks. We consider two independent walkers moving
with constant speed on either the discrete or continuous circle, and changing
directions at independent geometric (respectively, exponential) times. One of
the walkers carries a message that wishes to travel as far and as fast as
possible in the clockwise direction. The message stays with its current carrier
unless the two walkers meet, the carrier is moving counter-clockwise, and the
other walker is moving clockwise. In that case, the message jumps to the other
walker. The long-term average clockwise speed of the message is computed. An
explicit expression is derived via the solution of an associated boundary value
problem in terms of the generator of the underlying Markov process. The average
transmission cost is also similarly computed, measured as the long-term number
of jumps the message makes per unit time. The tradeoff between speed and cost
is examined, as a function of the underlying problem parameters.
Keywords
ergodicity, generator, Markov process, network routing, stochastic networks
Embargo Lift Date
2100-01-01
Identifiers
External DOI: https://doi.org/10.1002/rsa.20932
This record's URL: https://www.repository.cam.ac.uk/handle/1810/288114
Rights
Attribution 4.0 International (CC BY)
Licence URL: http://creativecommons.org/licenses/by/4.0/
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk