Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T07:42:41.263Z Has data issue: false hasContentIssue false
  • English
  • Français

A stochastic process on a network with connections to Laplacian systems of equations

Part of: Special processes Stochastic processes

Published online by Cambridge University Press:  21 January 2022

Amitabha Bagchi Open the ORCID record for Amitabha Bagchi [Opens in a new window] ,
Iqra Altaf Gillani Open the ORCID record for Iqra Altaf Gillani [Opens in a new window]  and
Pooja Vyavahare
Amitabha Bagchi*
Affiliation:
IIT Delhi
Iqra Altaf Gillani*
Affiliation:
IIT Delhi
Pooja Vyavahare*
Affiliation:
IIT Tirupati
*
*Postal address: Indian Institute of Technology Delhi, Department of Computer Science and Engineering, Hauz Khas, New Delhi, Delhi 110016, India.
*Postal address: Indian Institute of Technology Delhi, Department of Computer Science and Engineering, Hauz Khas, New Delhi, Delhi 110016, India.
**Postal address: Indian Institute of Technology Tirupati, Department of Electrical Engineering, Tirupati, Andhra Pradesh 517506, India.
Get access Rights & Permissions [Opens in a new window]

Abstract

We study an open discrete-time queueing network. We assume data is generated at nodes of the network as a discrete-time Bernoulli process. All nodes in the network maintain a queue and relay data, which is to be finally collected by a designated sink. We prove that the resulting multidimensional Markov chain representing the queue size of nodes has two behavior regimes depending on the value of the rate of data generation. In particular, we show that there is a nontrivial critical value of the data rate below which the chain is ergodic and converges to a stationary distribution and above which it is non-ergodic, i.e., the queues at the nodes grow in an unbounded manner. We show that the rate of convergence to stationarity is geometric in the subcritical regime.

Keywords

Queueing networksrandom walksgeometric ergodicity

MSC classification

Primary: 60G10: Stationary processes
Secondary: 60G50: Sums of independent random variables; random walks 60K25: Queueing theory
Type
Original Article
Information
Advances in Applied Probability , Volume 54 , Issue 1 , March 2022 , pp. 254 - 278
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Applied Probability Trust

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

Becchetti, L., Bonifaci, V. and Natale, E. (2018). Pooling or sampling: collective dynamics for electrical flow estimation. In Proc. 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS ’18), International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, pp. 1576–1584.Google Scholar
Boyd, S., Ghosh, A., Prabhakar, B. and Shah, D. (2005). Gossip algorithms: design, analysis and applications. In Proc. 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 1653–1664.10.1109/INFCOM.2005.1498447CrossRefGoogle Scholar
Brightwell, G. and Winkler, P. (1990). Maximum hitting time for random walks on graphs. Random Structures Algorithms 1, 263–276.10.1002/rsa.3240010303CrossRefGoogle Scholar
Cheeger, J. (1969). A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis: a Symposium in Honor of Salomon Bochner, ed. Gunning, R. C., Princeton University Press, pp. 195–199.Google Scholar
Cohen, M. B. et al. (2014). Solving SDD linear systems in nearly $m~log^{1/2}n$ time. In Proc. 46th annual ACM Symposium on Theory of Computing (STOC ’14), Association for Computing Machinery, New York, pp. 343–352.10.1145/2591796.2591833CrossRefGoogle Scholar
Doyle, P. and Snell, J. Random Walks and Electric Networks. Mathematical Association of America, Washington, DC.10.5948/UPO9781614440222CrossRefGoogle Scholar
Georgiadis, L. and Szpankowski, W. (1992). Stability of token passing rings. Queueing Systems 11, 7–33.10.1007/BF01159285CrossRefGoogle Scholar
Gillani, I. A. and Bagchi, A. (2020). A queueing network-based distributed Laplacian solver. In Proc. 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’20), Association for Computing Machinery, New York, pp. 535–537.10.1145/3350755.3400251CrossRefGoogle Scholar
Gillani, I. A. and Bagchi, A. (2021). A queueing network-based distributed Laplacian solver for directed graphs. Inf. Process. Lett. 166, 106040.10.1016/j.ipl.2020.106040CrossRefGoogle Scholar
Gillani, I. A., Bagchi, A. and Ranu, S. (2021). A group-to-group version of random walk betweenness centrality. In Proc. 8th ACM IKDD CODS and 26th COMAD (CODS-COMAD ’21), Association for Computing Machinery, New York, pp. 127–135.10.1145/3430984.3431020CrossRefGoogle Scholar
Gillani, I. A., Vyavahare, P. and Bagchi, A. (2021). Lower bounds for in-network computation of arbitrary functions. Distrib. Comput 34, 181–193.10.1007/s00446-021-00394-7CrossRefGoogle Scholar
Kamra, A., Misra, V., Feldman, J. and Rubenstein, D. (2006). Growth codes: maximizing sensor network data persistence. In Proc. 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ’06), Association for Computing Machinery, New York, pp. 255–266.10.1145/1159913.1159943CrossRefGoogle Scholar
Kanade, V., Mallmann-Trenn, F. and Sauerwald, T. (2019). On coalescence time in graphs: when is coalescing as fast as meeting? In Proc. 30th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA ’19), Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 956–965.Google Scholar
Kempe, D., Dobra, A. and Gehrke, J. (2003). Gossip-based computation of aggregate information. In Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’03), Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 482–491.10.1109/SFCS.2003.1238221CrossRefGoogle Scholar
Kleinrock, L. (1975). Queueing Systems. John Wiley, New York.Google Scholar
Koutis, I. and Xu, S. C. (2016). Simple parallel and distributed algorithms for spectral graph sparsification. ACM Trans. Comput, Parallel . 3, paper no. 14, 14 pp.10.1145/2948062CrossRefGoogle Scholar
Kyng, R. and Sachdeva, S. (2016). Approximate Gaussian elimination for Laplacians—fast, sparse, and simple. In Proc. 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’16), Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 573–582.10.1109/FOCS.2016.68CrossRefGoogle Scholar
Leighton, F. T., Maggs, B. M., Ranade, A. G. and Rao, S. B. (1994). Randomized routing and sorting on fixed-connection networks. J. Algorithms 17, 157–205.10.1006/jagm.1994.1030CrossRefGoogle Scholar
Leighton, F. T., Maggs, B. M. and Rao, S. B. (1994). Packet routing and job-shop scheduling in ${O} (congestion + dilation)$ steps. Combinatorica 14, 167–186.10.1007/BF01215349CrossRefGoogle Scholar
Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times. American Mathematical Society, Providence, RI.Google Scholar
Little, J. D. C. (1961). Proof for the queuing formula: $L= \lambda w$ . Operat. Res. 9, 383–387.10.1287/opre.9.3.383CrossRefGoogle Scholar
Loynes, R. M. (1962). The stability of a queue with non-independent inter-arrival and service times. Math. Proc. Camb. Phil. Soc. 58, 497–520.10.1017/S0305004100036781CrossRefGoogle Scholar
Lund, R. B. and Tweedie, R. L. (1996). Geometric convergence rates for stochastically ordered Markov chains. Math. Operat. Res. 21, 182–194.10.1287/moor.21.1.182CrossRefGoogle Scholar
Luo, W. and Ephremides, A. (1999). Stability of N interacting queues in random-access systems. IEEE Trans. Inf. Theory 45, 1579–1587.10.1109/18.771161CrossRefGoogle Scholar
Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Springer, London.10.1007/978-1-4471-3267-7CrossRefGoogle Scholar
Mosk-Aoyama, D. and Shah, D. (2006). Computing separable functions via gossip. In Proc. 25th Annual ACM Symposium on Principles of Distributed Computing (PODC ’06), Association for Computing Machinery, New York, pp. 113–122.10.1145/1146381.1146401CrossRefGoogle Scholar
Palacios, J. L. (1994). Expected hitting and cover times of random walks on some special graphs. Random Structures Algorithms 5, 173–182.10.1002/rsa.3240050116CrossRefGoogle Scholar
Sengupta, N., Bagchi, A., Ramanath, M. and Bedathur, S. (2019). ARROW: approximating reachability using random-walks over web-scale graphs. In Proc. 35th IEEE International Conference on Data Engineering (ICDE ’19), Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 470–481.10.1109/ICDE.2019.00049CrossRefGoogle Scholar
Spielman, D. A. and Teng, S.-H. (2004). Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proc. 36th Annual ACM Symposium on Theory of Computing (STOC ’04), Association for Computing Machinery, New York, pp. 81–90.10.1145/1007352.1007372CrossRefGoogle Scholar
Szpankowski, W. (1990). Towards computable stability criteria for some multidimensional stochastic processes. In Stochastic Analysis of Computer and Communication Systems, ed. Takagi, H., Elsevier, Amsterdam, pp. 131–172.Google Scholar
Szpankowski, W. (1994). Stability conditions for some distributed systems: buffered random access systems. Adv. Appl. Prob. 26, 498–515.10.2307/1427448CrossRefGoogle Scholar
Tripathi, V., Talak, R. and Modiano, E. (2019). Age optimal information gathering and dissemination on graphs. In Proc. 38th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2019), Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 2422–2430.10.1109/INFOCOM.2019.8737642CrossRefGoogle Scholar
Tsybakov, B. S. and Mikhailov, V. A. (1979). Ergodicity of a slotted ALOHA system. Problemy Peredachi Informatsii 15, 73–87.Google Scholar