Scheduling in Synchronous Networks and the Greedy Algorithm

We study the greedy algorithm for delivering messages with deadline 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, t..