A Timing-based Schema for Stabilizing Information Exchange

摘要

The paradigm of information exchange provides a basis for nodes in a network to stay uptodate with the recent information in the network. In this paradigm, nodes cooperate with each other to share their current information. We present a simple and uniform schema for building information exchange protocols that are stabilizing, in the following strong sense. Starting from arbitrary state, the protocols reach within bounded real-time a state wherefrom all nodes remain uptodate with the recent information in the network.The ability to stabilize in bounded time is achieved by using timing-based actions. The timing constraints on these actions can be systematically adapted to suit a variety of network loads, delay requirements, and scheduling restrictions and to tolerate out-of-phase and drift-prone node clocks. Our schema also tolerates any number of topolog-ical changes in the network. Moreover, it accommodates information that is time-varying as well as it does information that is fixed. It is thus well-suited to dynamic high speed networks.