Scheduling in synchronous networks and the greedy algorithm

We study the greedy algorithm for delivering messages with deadlines in syn chronous networks. The processors have to determine a feasible schedule, by which all messages will arrive at their destinations and meet their deadli nes. 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 s um of the capacities of the edges entering it. For such networks where ther e 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 dire cted chain networks with unit capacities, and modify the results to general chains, directed rings, trees, and then for the general above-mentioned cl ass of networks. For networks with a bottleneck and half-duplex networks we show that no algorithm, that makes decisions based only on local informati on, can solve the problem. For bottleneck-free networks, in which the messa ges 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-c omplete. (C) 1999 Elsevier Science B.V. All rights reserved.