Thrifty scheduling is an algorithm that improves the responsiveness of a stripe-scheduled multimedia server. It increases the determinism of the data-distribution service, reduces the likelihood of high startup delays, and enables an increase in the rated load of the system. A stripe-scheduled media server is a distributed video-on-demand system that load-balances by striping video data across multiple computer nodes and cyclically scheduling the distribution of the data. The server displays highly variable startup delays in response to requests for data streams. These delays are due to clusters of allocated slots in the distribution schedule, which form naturally as the system load increases. Thrifty scheduling is a scalable algorithm that improves responsiveness by allocating streams to schedule slots in a way that reduces the clustering in the schedule. This algorithm has been incorporated into the Tiger video fileserver.