Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-24T19:42:48.051Z Has data issue: false hasContentIssue false
  • English
  • Français

Degree-dependent threshold-based random sequential adsorption on random trees

Part of: Time-dependent statistical mechanics (dynamic and nonequilibrium) Special processes Operations research and management science Computer system organization

Published online by Cambridge University Press:  20 March 2018

Thomas M. M. Meyfroyt
Thomas M. M. Meyfroyt*
Affiliation:
Eindhoven University of Technology
*
* Postal address: Eindhoven University of Technology, MetaForum 4.086, P.O. Box 513, 5600 MB Eindhoven, The Netherlands. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a special version of random sequential adsorption (RSA) with nearest-neighbor interaction on infinite tree graphs. In classical RSA, starting with a graph with initially inactive nodes, each of the nodes of the graph is inspected in a random order and is irreversibly activated if none of its nearest neighbors are active yet. We generalize this nearest-neighbor blocking effect to a degree-dependent threshold-based blocking effect. That is, each node of the graph is assumed to have its own degree-dependent threshold and if, upon inspection of a node, the number of active direct neighbors is less than that node's threshold, the node will become irreversibly active. We analyze the activation probability of nodes on an infinite tree graph, given the degree distribution of the tree and the degree-dependent thresholds. We also show how to calculate the correlation between the activity of nodes as a function of their distance. Finally, we propose an algorithm which can be used to solve the inverse problem of determining how to set the degree-dependent thresholds in infinite tree graphs in order to reach some desired activation probabilities.

Keywords

Analytical modelcounter-based gossip protocolinteracting particle systemrandom sequential adsorptionjamming limitrandom tree graph

MSC classification

Primary: 82C22: Interacting particle systems 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Secondary: 68M10: Network design and communication 90B18: Communication networks
Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 1 , March 2018 , pp. 302 - 326
Copyright
Copyright © Applied Probability Trust 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Baccelli, F. and Blaszczyszyn, B. (2009). Stochastic Geometry and Wireless Networks, Vol. 1, Theory, Foundation and Trends in Networking. Now Publishers, Breda. Google Scholar
[2] Bermolen, P., Jonckheere, M. and Moyal, P. (2017). The jamming constant of uniform random graphs. Stoch. Process. Appl. 127, 2138–2178. CrossRefGoogle Scholar
[3] Bermolen, P., Jonckheere, M., Larroca, F. and Moyal, P. (2014). Estimating the spatial reuse with configuration models. Preprint. Available at https://arxiv.org/abs/1411.0143. Google Scholar
[4] Coladon, T., Vučinić, M. and Tourancheau, B. (2015). Improving trickle fairness: locally-calculated redundancy constants. In Proceedings of the International Conference on Protocol Engineering (ICPE) and International Conference on New Technologies of Distributed Systems (NTDS), IEEE, pp. 1–6. Google Scholar
[5] Dehling, H. G., Fleurke, S. R. and Külske, C. (2008). Parking on a random tree. J. Statist. Phys. 133, 151–157. Google Scholar
[6] Dhara, S., van Leeuwaarden, J. S. H. and Mukherjee, D. (2016). Generalized random sequential adsorption on Erdős–Rényi random graphs. J. Statist. Phys. 164, 1217–1232. Google Scholar
[7] Evans, J. W. (1993). Random and cooperative sequential adsorption. Rev. Mod. Phys. 65, 1281–1329. Google Scholar
[8] Fleurke, S. R. and Külske, C. (2010). Multilayer parking with screening on a random tree. J. Statist. Phys. 139, 417–431. CrossRefGoogle Scholar
[9] Hui, J. and Kelsey, R. (2016). Multicast protocol for low power and lossy networks (MPL). Preprint 7731, Internet RFC. Google Scholar
[10] Kermajani, H. and Gomez, C. (2014). On the network convergence process in RPL over IEEE 802.15.4 multihop networks: improvement and trade-offs. Sensors 14, 11993–12022. Google Scholar
[11] Kulpa, W. (1997). The Poincaré-Miranda theorem. Amer. Math. Monthly 104, 545–550. Google Scholar
[12] Levis, P., Patel, N., Culler, D. and Shenker, S. (2004). Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In Proceedings of the First Symposium on Networked Systems Design and Implementation, ACM, New York, pp. 15–28. Google Scholar
[13] Meyfroyt, T. M. M., Stolikj, M. and Lukkien, J. J. (2015). Adaptive broadcast suppression for Trickle-based protocols. In Proceedings of the 16th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), IEEE, 9 pp. Google Scholar
[14] Meyfroyt, T. M. M., Borst, S. C., Boxma, O. J. and Denteneer, D. (2015). On the scalability and message count of trickle-based broadcasting schemes. Queueing Systems 81, 203–230. Google Scholar
[15] Ni, S.-Y., Tseng, Y.-C., Chen, Y.-S. and Sheu, J.-P. (1999). The broadcast storm problem in a mobile ad hoc network. In Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), ACM, New York, pp. 151–162. Google Scholar
[16] Ostilli, M. (2012). Cayley trees and Bethe lattices: a concise analysis for mathematicians and physicists. Physica A 391, 3417–3423. Google Scholar
[17] Penrose, M. D. and Sudbury, A. (2005). Exact and approximate results for deposition and annihilation processes on graphs. Ann. App. Prob. 15, 853–889. Google Scholar
[18] Rényi, A. (1958). On a one-dimensional problem concerning random space filling. Magyar Tud. Akad. Mat. Kutató Int. Közl. 3, 109–127. Google Scholar
[19] Sanders, J., Jonckheere, M. and Kokkelmans, S. (2015). Sub-Poissonian statistics of jamming limits in ultracold Rydberg gases. Phys. Rev. Lett. 115, 043002. CrossRefGoogle ScholarPubMed
[20] Sudbury, A. (2009). Random sequential adsorption on random trees. J. Statist. Phys. 136, 51–58. Google Scholar
[21] Vallati, C. and Mingozzi, E. (2013). Trickle-F: fair broadcast suppression to improve energy-efficient route formation with the RPL routing protocol. In Proceedings of Sustainable Internet and ICT for Sustainability (SustainIT), IEEE, 9 pp. Google Scholar
[22] Winter, T. et al. (2012). RPL: IPv6 routing protocol for low-power and lossy networks. Preprint 6550, Internet RFC. Google Scholar