Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 25, 2004 | public
Report Open

A Combinatorial Bound on the List Size

Abstract

In this paper we study the scenario in which a server sends dynamic data over a single broadcast channel to a number of passive clients. We consider the data to consist of discrete packets, where each update is sent in a separate packet. On demand, each client listens to the channel in order to obtain the most recent data packet. Such scenarios arise in many practical applications such as the distribution of weather and traffic updates to wireless mobile devices and broadcasting stock price information over the Internet. To satisfy a request, a client must listen to at least one packet from beginning to end. We thus consider the design of a broadcast schedule which minimizes the time that passes between a clients request and the time that it hears a new data packet, i.e., the waiting time of the client. Previous studies have addressed this objective, assuming that client requests are distributed uniformly over time. However, in the general setting, the clients behavior is difficult to predict and might not be known to the server. In this work we consider the design of universal schedules that guarantee a short waiting time for any possible client behavior. We define the model of dynamic broadcasting in the universal setting, and prove various results regarding the waiting time achievable in this framework.

Files

etr058.pdf
Files (74.1 kB)
Name Size Download all
md5:80a0c3938ea489360b94d3aa73753279
74.1 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023