A stochastic process on a network with connections to Laplacian systems of equations
From MaRDI portal
Publication:5066880
Abstract: We study an open discrete-time queueing network that models the collection of data in a multi-hop sensor network. We assume data is generated at the sensor nodes 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 multi-dimensional 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 non-trivial critical value of 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 sub-critical regime. We also show the connections of this process to a class of Laplacian systems of equations whose solutions include the important problem of finding the effective resistance between two nodes, a subroutine that has been widely used to develop efficient algorithms for a number of computational problems. Hence our work provides the theoretical basis for a new class of distributed algorithms for these problems.
Recommendations
Cites work
- A Proof for the Queuing Formula: L = λW
- A queueing network-based distributed Laplacian solver
- A queueing network-based distributed Laplacian solver for directed graphs
- Computing separable functions via gossip
- Ergodicity of a slotted ALOHA system
- Expected hitting and cover times of random walks on some special graphs
- Geometric Convergence Rates for Stochastically Ordered Markov Chains
- scientific article; zbMATH DE number 3934150 (Why is no real title available?)
- scientific article; zbMATH DE number 3522951 (Why is no real title available?)
- scientific article; zbMATH DE number 3322728 (Why is no real title available?)
- scientific article; zbMATH DE number 3337135 (Why is no real title available?)
- Lower bounds for in-network computation of arbitrary functions
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Markov chains and stochastic stability
- Maximum hitting time for random walks on graphs
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Randomized Routing and Sorting on Fixed-Connection Networks
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Stability conditions for some distributed systems: buffered random access systems
- Stability of N interacting queues in random-access systems
- Stability of token passing rings
Cited in
(6)- Laplace and bi-Laplace equations for directed networks and Markov chains
- Networks of reinforced stochastic processes: asymptotics for the empirical means
- Stochastic Unfolding and Homogenization of Spring Network Models
- scientific article; zbMATH DE number 5225666 (Why is no real title available?)
- Local weak convergence for sparse networks of interacting processes
- Lax–Oleinik Formula on Networks
This page was built for publication: A stochastic process on a network with connections to Laplacian systems of equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066880)
