Fault-tolerant Distrubuted Algorithms in AD Hoc Networks

Due to the advances of wireless communication technologies, wireless ad hoc networks are increasingly commonplace nowadays. Spontaneous ("ad hoc") communication without a fixed infrastructure is in fact a prerequisite for applications like wireless sensor networks and disaster area communication systems. It is also a major enabling technology for future pervasive computing systems, as envisioned in the ISTAG Scenario for Ambient Intelligence, for example. Inevitably, however, our society will become dependent upon the correct and reliable operation/interaction of such systems. Hence, in the long run, todays best-effort approaches to system-wide dependability will not be sufficient. Unfortunately, most existing protocols and algorithms for wireless ad hoc and sensor networks lack a precisely defined failure model and provide dependability on a best-effort basis ("robustness") only. Fault-tolerant distributed algorithms, on the other hand, have usually been designed for fully connected networks. A classic consensus algorithm, for example, does not work in a sparsely connected and possibly dynamically changing ad hoc network. Although an intemediate routing layer for simulating a fully connected network via multi-hop communication could be employed, the resulting solutions are typically quite inefficient. Encouraged by some previous research in this area, the project "Fault-Tolerant Distributed Algorithms in Sparse Ad Hoc Wireless Networks" (SPAWN) shall design and analyze failure models, protocols and algorithms for basic fault-tolerant distributed computing problems like consensus and clock synchronization that run directly atop of sparse networks.

Due to the advances of wireless communication technologies, wireless ad hoc networks are increasingly commonplace nowadays. Spontaneous ("ad hoc") communication without a fixed infrastructure is in fact a prerequisite for applications like wireless sensor networks and disaster area communication systems. It is also a major enabling technology for future pervasive computing systems, as envisioned in the ISTAG Scenario for Ambient Intelligence, for example. Inevitably, however, our society will become dependent upon the correct and reliable operation/interaction of such systems. Hence, in the long run, todays best-effort approaches to system-wide dependability will not be sufficient. Unfortunately, most existing protocols and algorithms for wireless ad hoc and sensor networks lack a precisely defined failure model and provide dependability on a best-effort basis ("robustness") only. Fault-tolerant distributed algorithms, on the other hand, have usually been designed for fully connected networks. A classic consensus algorithm, for example, does not work in a sparsely connected and possibly dynamically changing ad hoc network. Although an intemediate routing layer for simulating a fully connected network via multi-hop communication could be employed, the resulting solutions are typically quite inefficient. Encouraged by some previous research in this area, the project "Fault-Tolerant Distributed Algorithms in Sparse Ad Hoc Wireless Networks" (SPAWN) shall design and analyze failure models, protocols and algorithms for basic fault-tolerant distributed computing problems like consensus and clock synchronization that run directly atop of sparse networks.