Virtual Infrastructure for Collision-Prone Wireless Networks

Wireless ad hoc networks pose several significant challenges: devices are unreliable; deployments are unpredictable; and communication is erratic. One proposed solution is Virtual Infrastructure, an abstraction in which unpredictable and unreliable devices are used to emulate reliable and predictable infrastructure. In this paper, we present a new protocol for emulating virtual infrastructure in collision-prone wireless networks. At the heart of our emulation is a "convergent history agreement protocol" that tolerates lost messages and crash failures, and is designed specifically for ad hoc deployments: the participants are a priori unknown, and thus the protocol adapts to varying numbers of participants. The convergent history agreement protocol is quite efficient, as each agreement instance completes in a constant number of communication rounds, and the size of the messages is constant, independent of the length of the execution. Building on the convergent history agreement protocol, out virtual infrastructure emulation introduces only constant overhead per virtual round emulated. We believe that this new emulation algorithm, along with the techniques developed in this paper, help to bring virtual infrastructure closer to a reality.

Presented at:
27th Annual Symposium on Principles of Distributed Computing, Toronto, Canada, August, 2008

Note: The status of this file is: Anyone

 Record created 2008-06-05, last modified 2020-10-28

Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)