Scheduling in synchronous networks and the greedy algorithm

Abstract

We study the greedy algorithm for delivering messages with deadlines in synchronous networks. The processors have to determine a feasible schedule, by which all messages will arrive at their destinations and meet their deadlines. At each step a processor cannot send on any of its leaving links more messages than the capacity of that link. We study bottleneck-free networks, in which the capacity of each edge leaving any processor is at least the sum of the capacities of the edges entering it. For such networks where there is at most one simple path connecting any pair of vertices, we determine a necessary and sufficient condition for the initial configuration to have a feasible schedule, and prove that if this condition holds then the greedy algorithm, that chooses at each step the most urgent messages (those with closest deadlines), determines such a feasible schedule. We start with directed chain networks with unit capacities, and modify the results to general chains, directed rings, trees, and then for the general above-mentioned class of networks. For networks with a bottleneck and half-duplex networks we show that no algorithm, that makes decisions based only on local information, can solve the problem. For bottleneck-free networks, in which the messages between two processors have to follow only one of the paths connecting them, the problem of deciding whether there exists a valid schedule is NP-complete. © 1999 Elsevier Science B.V. All rights reserved.