123/2006 : Construction of a Fault-Tolerant Wireless Communication Topology Using Distributed Agreement

RR Number

123/2006

Conference

Proceedings of the 2006 Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS 2006)

Author(s)

Heinrich Moser, Bernd Thallner

Abstract

This paper presents a proven correct implementation of a distributed topology construction algorithm based upon agreement on minimal-weight clusters for creating a k-regular, k-node connected fault-tolerant communication network. It adapts to crashing nodes, moving nodes and changing communication cost and is guaranteed to converge. We analyze the requirements imposed upon the system model by this class of agreement-based algorithms and show that our implementation works in asynchronous distributed systems augmented with unreliable failure detectors.

Bibtex

@inproceedings{MT06,
 author = {Heinrich Moser and Bernd Thallner},
 title = {Construction of a fault-tolerant wireless communication topology using distributed agreement},
 booktitle = {DIWANS '06: Proceedings of the 2006 workshop on Dependability issues in wireless ad hoc networks and sensor networks},
 year = {2006},
 isbn = {1-59593-471-5},
 pages = {35--44},
 location = {Los Angeles, CA, USA},
 doi = {http://doi.acm.org/10.1145/1160972.1160979},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }

Download

Get paper.pdf - Adobe PDF-format, (181.7842 KB; posted at July 09 2013; )