On the Instability of Matching Queues

A matching queue is described via a graph $G$ together with a matching policy. Specifically, to each node in the graph there is a corresponding arrival process of items which can either be queued, or matched with queued items in neighboring nodes. The matching policy specifies how items are matched whenever more than one matching is possible. Motivated by the increasing theoretical interest in such matching models, we investigate the question of (in)stability of matching queues which satisfy a natural necessary condition for stability, which can be thought of as an analogue of the usual traffic condition for traditional queueing networks (namely, $\rho_i < 1$ in each service station $i$). We employ fluid-stability arguments to show that matching queues can in general be unstable, even though the necessary stability condition is satisfied.