Competitive concurrent distributed queuing

Distributed queuing is a fundamental problem in distributed computing, arising in a variety of applications. The chal-lenge in designing a distributed queuing algorithm is to min-imize message traffic and delay. This paper gives a novel competitive analysis of the Arrow distributed queuing protocol under concurrent access. We analyze the combined latency of r simultaneous requests, and derive a competitive ratio of s • log r, where s is the stretch of a preselected spanning tree in the network. Our analysis employs a novel greedy characterization of the way the Arrow protocol orders concurrent requests, and yields a new lower bound on the quality of the nearest-neighbor heuristic for the Traveling Salesperson Problem. 1