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 u...[ Read more ]

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, 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.