Text

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

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 log2(n) bits of memory. Second, we show that within a certain broad class of policies, a dispatching policy that exchanges o(n2) messages per unit of time, and with o(log (n)) bits of memory, cannot be always stable.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.3 August 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1862-1874

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

STABILITY
MEMORY
LOAD BALANCING
COMMUNICATION OVERHEAD

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1191

Pernyataan Tanggungjawab

David Gamarnik, John N. Tsitsiklis, Martin Zubeldia

Versi lain/terkait

Lampiran Berkas

Komentar