The Broad Picture

Dynamic information is the currency of most computer networks today. Information available on networked devices tends to change over a period of time, rather than remain static, and these changes must be propagated throughout the network. While the specific requirements of propagating these changes may vary from real time dissemination of changes to lazy propagation of changes, there have to be mechanisms which guarantee this functionality, at an acceptable overhead. An ad hoc network is an network of mobile routers and hosts that together form an arbitrary network topology. The routers and hosts in an ad hoc network are free to move and organize themselves arbitrarily; thus, the network's topology may change randomly. Mobile hosts may be considered as weakly connected nodes in an ad hoc network [1] because of the absence of a fixed topology connecting these devices and the intermittent addition and removal of such devices from the network. Note the ambiguous use of the term ``network" - the other end of the network to which the device is synchronizing may be a mobile device, a PC or a server. For example, an appointment schedule may be simultaneously maintained on a PC in office, a PC at home, and a mobile device like a PDA (Personal Digital Assistant). The three hosts will have to synchronize the appointment database periodically to maintain consistent data in the database. A natural metric of acceptable overhead for synchronization will usually be a measure of the cost in terms of the latency and the bandwidth involved in dissemination of information through the network for synchronization. Mobile device network throughput is also very sensitive to the number of rounds involved in any communication. Non-interactive synchronization protocols that are not dependent on repeated data exchanges while synchronizing are preferred because the overhead of packet transmission is substantial for wireless networks (increasingly used by mobile devices) as compared to wired networks. Mobile devices are usually also bogged down due to excessive protocol overhead because of their limited computational capabilities and limited power resources. Some of these limitations become apparent from Figure 1.1, which highlights the specifications of the Palm Vx PDA [2]. For example, the Palm Vx has a single threaded processor with a clock speed of just 32MHz, which is lesser than even entry level PCs by orders of magnitude.

Figure 1.1: Representative PDA Specification - Palm Vx