Distributed Online and Stochastic Queueing on a Multiple Access Channel

Bienkowski, Marcin, Jurdzinski, Tomasz, Korzeniowski, Miroslaw and Kowalski, Dariusz R ORCID: 0000-0002-1316-7788 (2018) Distributed Online and Stochastic Queueing on a Multiple Access Channel. ACM TRANSACTIONS ON ALGORITHMS, 14 (2). pp. 1-22.

Text paper.pdf - Author Accepted Manuscript Download (434kB)

Abstract

<jats:p> We consider the problems of online and stochastic packet queueing in a distributed system of <jats:italic>n</jats:italic> nodes with queues, where the communication between the nodes is done via a multiple access channel. In the online setting, in each round, an arbitrary number of packets can be injected to nodes’ queues. Two measures of performance are considered: the total number of packets in all queues, called the <jats:italic>total load</jats:italic> , and the maximum queue size, called the <jats:italic>maximum load</jats:italic> . We develop a deterministic distributed algorithm that is asymptotically optimal with respect to both complexity measures, in a competitive way. More precisely, the total load of our algorithm is bigger than the total load of any other algorithm, including centralized online solutions, by only an additive term of <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>2</jats:sup> ), whereas the maximum queue size of our algorithm is at most <jats:italic>n</jats:italic> times bigger than the maximum queue size of any other algorithm, with an extra additive <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> ). The optimality for both measures is justified by proving the corresponding lower bounds, which also separates nearly exponentially distributed solutions from the centralized ones. Next, we show that our algorithm is also stochastically stable for <jats:italic>any</jats:italic> expected injection rate smaller or equal to 1. This is the first solution to the stochastic queueing problem on a multiple access channel that achieves such stability for the (highest possible) rate equal to 1. </jats:p>

Item Type:	Article
Uncontrolled Keywords:	Distributed algorithms, online algorithms, multiple access channel, contention resolution, shared channel, stochastic queueing, stability
Depositing User:	Symplectic Admin
Date Deposited:	06 Aug 2018 06:23
Last Modified:	19 Jan 2023 01:29
DOI:	10.1145/3182396
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3024619