Stability of the greedy algorithm on the circle

DOI10.1002/CPA.21712zbMATH Open1374.60186arXiv1112.2389OpenAlexW2609568662MaRDI QIDQ5370518FDOQ5370518

Authors: Leonardo T. Rolla, Vladas Sidoravicius 

Publication date: 20 October 2017

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Abstract: We consider a single-server system with service stations in each point of the circle. Customers arrive after exponential times at uniformly-distributed locations. The server moves at finite speed and adopts a greedy routing mechanism. It was conjectured by Coffman and Gilbert in~1987 that the service rate exceeding the arrival rate is a sufficient condition for the system to be positive recurrent, for any value of the speed. In this paper we show that the conjecture holds true.

Full work available at URL: https://arxiv.org/abs/1112.2389

Recommendations

• Stability and performance of greedy server systems
• Polling and greedy servers on a line
• Queueing systems on a circle
• Greedy walk on the real line
• On the Stability of Greedy Polling Systems with General Service Policies

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cited In (6)

• Comments on: ``Polling: past, present and perspective
• The critical greedy server on the integers is recurrent
• Random walks avoiding their convex hull with a finite memory
• On the stability of a two-sided sweep algorithm
• Stability and performance of greedy server systems
• Greedy walk on the real line

This page was built for publication: Stability of the greedy algorithm on the circle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5370518)