Noname manuscript No. (will be inserted by the editor) Real Time Stochastic Scheduling in Broadcast Systems with Decentralized Data Storage

the date of receipt and acceptance should be inserted later Abstract Data broadcasting is an efficient method to disseminate informa-tion to a large group of requesters with common interests. Performing such broadcasts typically involve the determination of a broadcast schedule in-tended to maximize the quality of service provided by the broadcast system. Earlier studies have proposed solutions to this problem in the form of heuris-tics and local search techniques designed to achieve minimal deadline misses or maximal utility. An often ignored factor in these studies is the possibility of the data items being not available locally, but rather have to be fetched from data servers distributed over a network, thereby inducing a certain level of stochasticity in the actual time required to serve a data item. This stochas-ticity is introduced on behalf of the data servers which themselves undergo a dynamic management of serving data requests. In this paper we revisit the problem of real time data broadcasting under such a scenario. We investigate the efficiency of heuristics that embed the stochastic nature of the problem in their design and compare their performance with those proposed for non-stochastic broadcast scheduling. Further, we extend our analysis to understand the various factors in the problem structure that influence these heuristics, and are often exploited by a better performing one