A Caltech Library Service

Staleness vs. waiting time in universal discrete broadcast

Langberg, Michael and Sprintson, Alexander and Bruck, Jehoshua (2005) Staleness vs. waiting time in universal discrete broadcast. In: 2005 IEEE International Symposium on Information Theory (ISIT), Adelaide, Australia, 4-9 September, 2005. IEEE , Piscataway, NJ, pp. 2124-2128.

See Usage Policy.


Use this Persistent URL to link to this item:


In this paper we study the distribution of dynamic data over a broadcast channel to a large number of passive clients. The data is simultaneously distributed to clients in the form of discrete packets, each packet captures the most recent state of the information source. Clients obtain the information by accessing the channel and listening for the next available packet. This scenario, referred to as discrete broadcast, has many practical applications such as the distribution of stock information to wireless mobile devices and downloading up-to-date battle information in military networks. Our goal is minimize the amount of time a client has to wait in order to obtain a new data packet, i.e., the waiting time of the client. We show that we can significantly reduce the waiting time by adding redundancy to the schedule. We identify universal schedules that guarantee low waiting time for any client, regardless of the access pattern. A key point in the design of data distribution systems is to ensure that the transmitted information is always up-to-date. Accordingly, we introduce the notion of staleness that captures the amount of time that passes from the moment the information is generated, until it is delivered to the client. We investigate the fundamental trade-off between the staleness and the waiting time. In particular, we present schedules that yield lowest possible waiting time for any given staleness constraint.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. Posted online 31 October 2005 This work was supported in part by the Caltech Lee Center for Advanced Networking and by NSF grants ANI-0322475 and CCF-0346991.
Record Number:CaltechAUTHORS:LANisit05a
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2609
Deposited By: Archive Administrator
Deposited On:12 Apr 2006
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page