The pinwheel: a real-time scheduling problem

Abstract

Some satellites transmit a piece of information for a set duration, then proceed with another piece of information. A ground station receiving from several such satellites and wishing to avoid data loss faces a real-time scheduling problem. The pinwheel is a formalization of this problem. Given a multiset A of integers=(a/sub 1/, a/sub 2/, . . ., a/sub n/), a successful schedule S is an infinite sequence over (1, 2, . . ., n) such that any subsequence of a/sub i/ (1<or=i<or=n) consecutive entries (slots) contains at least one i. The pinwheel decision problem concerns whether a useful representation of the corresponding schedule exists. Several results thus far established for these problems are reported.<<ETX>>