论文标题
异质服务系统中的稳定性，内存和消息交易权衡
Stability, memory, and messaging tradeoffs in heterogeneous service systems
论文作者
论文摘要
我们考虑了一个异质分布式服务系统，该系统由$ n $的服务器组成，这些服务器的处理率未知且可能不同。具有单位平均值和独立处理时间的工作是作为续签$λn$的续订过程，并以$ 0 <λ<1 $的价格到达系统。即将到来的工作立即派往与$ n $服务器相关的几个队列之一。我们假设派遣决策是由中央调度程序赋予有限内存的中央调度程序，并且能够与服务器交换消息。 我们研究基本资源需求（内存位和消息汇率），以使派遣策略是{\ bf最大稳定}的，即每当处理率的到达率使到达率小于总可用处理率时，稳定。首先，对于Poisson到达和指数服务时间的情况，我们提出了一种策略，该策略在使用正（但任意小）的消息速率以及$ \ log_2（n）$中的内存中最大程度地稳定。其次，我们表明，在某个广泛的策略中，每单位时间交换$ o \ big（n^2 \ big）$消息的派遣策略，并且使用$ o（\ log（n））$内存的位置，无法最大程度地稳定。因此，只要消息率不太过分，就必须进行对数记忆，并且足以达到最大稳定性。
We consider a heterogeneous distributed service system, consisting of $n$ servers with unknown and possibly different processing rates. Jobs with unit mean and independent processing times arrive as a renewal process of rate $λn$, with $0<λ<1$, to the system. Incoming jobs are immediately dispatched to one of several queues associated with the $n$ servers. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers. We study the fundamental resource requirements (memory bits and message exchange rate) in order for a dispatching policy to be {\bf maximally stable}, i.e., stable whenever the processing rates are such that the arrival rate is less than the total available processing rate. First, for the case of Poisson arrivals and exponential service times, we present a policy that is maximally 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\big(n^2\big)$ messages per unit of time, and with $o(\log(n))$ bits of memory, cannot be maximally stable. Thus, as long as the message rate is not too excessive, a logarithmic memory is necessary and sufficient for maximal stability.
