A Combinatorial Bound on the List Size

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