Traffic-light scheduling on the grid

Traffic-light scheduling on the grid

0.00 Avg rating0 Votes
Article ID: iaor1995947
Country: Netherlands
Volume: 53
Issue: 1/3
Start Page Number: 211
End Page Number: 234
Publication Date: Sep 1994
Journal: Discrete Applied Mathematics
Authors: ,
Abstract:

This paper studies the problem of route scheduling under the telephone model of communicationnetworks. Previous work in this model considered mostly the ‘broadcast’ and ‘gossip’ communication primitives. The approach studied here is that of devising simple, distributed universal schedules, that are efficient for wide families of routing instances, rather than attempting to solve individual instances separately. The paper concentrates on ‘traffic-light’ type schedules for route scheduling on the two-dimensional grid. In order to study the problem of scheduling given route instances, routes are classified according to the number of directions they use, and tight bounds are given on the time required for scheduling route instances in each class. For routes of length d or less, using only one direction, scheduling is shown to require d+O(1) time. For simple routesusing only two or three directions, scheduling is shown to require 2d+3 and 2d+4 time, respectively. Finally, for arbitrary simple routes scheduling is shown to require equ1 time.

Reviews

Required fields are marked *. Your email address will not be published.