The Data Broadcast Problem with Preemption

Abstract : The data-broadcast problem consists in finding an infinite schedule to broadcast a given set of messages so as to minimize the average response time to clients requesting messages, and the cost of the broadcast. This is an efficient means of disseminating data to clients, designed for environments, such as satellites, cable~TV, mobile phones, where there is a much larger capacity from the information source to the clients than in the reverse direction. Previous work concentrated on scheduling indivisible messages. Here, we studied a generalization of the model where the messages can be preempted. We show that this problem is NP-hard, even in the simple setting where the broadcast costs are zero, and give some practical 2-approximation algorithms for broadcasting messages. We also show that preemption can improve the quality of the broadcast by an arbitrary factor.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101959
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:46 AM
Last modification on : Wednesday, November 20, 2019 - 2:54:28 AM

File

RR1999-49.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101959, version 1

Collections

Citation

Nicolas Schabanel. The Data Broadcast Problem with Preemption. [Research Report] LIP RR-1999-49, Laboratoire de l'informatique du parallélisme. 1999, 3+21p. ⟨hal-02101959⟩

Share

Metrics

Record views

9

Files downloads

32