1 Dependable Message Delivery to Mobile Units

Mobile computing is emerging as a novel paradigm with its own characteristic problems, models, and algorithms. Much effort is being directed to integrate mobile units with xed networks, providing bridges to connect wireless to wired. The result is a xed core of wire-connected static nodes and a uid fringe of wireless mobile units, a computing system similar to the cellular telephone network. The model we put forward uses the graph of xed nodes as a foundation and models the mobile units themselves as persistent messages moving through this network graph. Such a model allows algorithms from traditional distributed computing to be directly implemented in the mobile environment, however, it has been shown that the unique properties of mobility, such as limited bandwidth and disconnection, make such direct translation impractical. This paper presents a fundamentally different idea. Instead of recreat-ing the functionality of distributed algorithms in the mobile domain, we show how distributed algorithms can be adapted to solve problems unique to the mobile environment. Specically we focus on the problem of dependably delivering a message to a moving unit. We demon-strate this technique with two new algorithms, the rst based on distributed snapshots and the second on diffusing computations