Fault-Tolerant Distributed Algorithms in Sparse Ad Hoc Wireless Networks (SPAWN)
Wireless ad hoc networks are becoming more commonplace by the day. However,
spontaneous communication without a fixed infrastructure places
new challenges on the atop-lying algorithms, and these challenges
have to be conquered to attain dependable systems.
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 intermediate routing layer for simulating a fully connected
network via multi-hop communication could be employed,
the resulting solutions are typically quite
inefficient.
The project SPAWN shall develop 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.
This project, which has been supported by the Austrian Science Foundation (
) under project number
P18264, was prematurely terminated due to the move of the project head.