In this paper, we address the problem of propagating data updates to alarge number of mobile clients. Typically, mobile clients operateautonomously, i.e., disconnected from data servers, for prolongedperiods of time relying on locally replicated corporate data (e.g.,database views, file systems). From time to time, they need to refreshtheir replicas with data changes registered at a central datarepository. We propose a hybrid approach for delivering these updatesto the clients. We use a broadcast channel to "cache on the air"fresh updates for as long as they are high on demand. At the sametime, any requests for older updates are individually serviced by theserver through a separate channel. The air-caching satisfies the bulkof clients' needs, increasing data throughput many-fold compared totraditional data delivery mechanisms. We describe a hierarchicalair-cache structure, and analyze the performance of broadcasting a logof committed updates. Based on that, we propose a technique thatdynamically modifies the contents and the structure of the air-cacheaccording to the number and the (dis)connection habits of the clients.Through extensive simulations, we demonstrate the adaptiveness,efficiency, and practicality of the proposed system even for verylarge client populations.