Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems

David Gamarnik (), John N. Tsitsiklis () and Martin Zubeldia ()
Additional contact information
David Gamarnik: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
John N. Tsitsiklis: Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts, 02139
Martin Zubeldia: Industrial and Systems Engineering Department, Georgia Institute of Technology, Atlanta, Georgia 30332

Mathematics of Operations Research, 2022, vol. 47, issue 3, 1862-1874

Abstract: We consider a heterogeneous distributed service system consisting of n servers with unknown and possibly different processing rates. Jobs with unit mean arrive as a renewal process of rate proportional to n and are immediately dispatched to one of several queues associated with the servers. We assume that the dispatching decisions are made by a central dispatcher with the ability to exchange messages with the servers and endowed with a finite memory used to store information from one decision epoch to the next, about the current state of the queues and about the service rates of the servers. We study the fundamental resource requirements (memory bits and message exchange rate) in order for a dispatching policy to be always stable. First, we present a policy that is always stable while using a positive (but arbitrarily small) message rate and log 2 ( n ) bits of memory. Second, we show that within a certain broad class of policies, a dispatching policy that exchanges o ( n 2 ) messages per unit of time, and with o ( log ( n ) ) bits of memory, cannot be always stable.

Keywords: Primary: 60G52; secondary: 90B22; load balancing; stability; memory; communication overhead (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1191 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:1862-1874

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().