Efficient wireless channel allocation, location information management, design of low overhead communication protocols and causal dependency tracking, and fault tolerance are important areas of research in mobile computing systems. This dissertation proposes new and efficiency solutions for these problems. (1) A probabilistic analysis of temporal imbalance in wireless channel demand is presented. The effectiveness of channel transfers depends on the duration for which imbalance persists. (2) A distributed dynamic channel allocation algorithm that adapts to spatial and temporal fluctuations in channel demand is presented. The algorithm requires minimal involvement of mobile nodes. The algorithm is deadlock free, starvation free, fair, and scalable. (3) A coterie based approach is adopted for update and querying location information of mobile nodes. Location updates and location queries are made at a subset of location servers. The set of servers, corresponding to a mobile node, for location update and query operations is dynamic. The dynamic nature of these sets alleviates situations of heavy burden on some location servers, when several mobile nodes are concentrated in a small area. (4) It is shown that in order to ensure causally ordered message delivery, only direct dependency information need to be sent with each message. An algorithm using this knowledge to enforce causal ordering of messages is presented. It can handle dynamically changing multicast communication groups. (5) Two alternatives to vector clocks for tracking causal dependencies, are presented. One scheme employs sets of dependency sequences, while the other relies on hierarchical clocks. Both schemes have low overheads, and are immune to fluctuations in the number of nodes in the system: a property that vector clocks lack. (6) For failure recovery, a quasi-synchronous checkpointing algorithm for mobile system is presented. A minimal set of nodes needs to take local checkpoints. The underlying computation is not blocked during checkpointing. A minimal rollback/recovery algorithm is presented. Computation at a node is rolled back only if its state depends on operations that have been undone due to node failure(s).;All algorithms have low communication and storage overheads, can withstand disconnected operation of mobile hosts, and meet the energy conservation and low bandwidth constraints.
展开▼
