Virtual infrastructure for collision-prone wireless networks. / Chockler, Gregory; Gilbert, Seth; Lynch, Nancy.

Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. Toronto, ON, Canada : ACM, 2008. p. 233-242.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Documents

Links

Abstract

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. It is designed specifically for ad hoc deployments, for example, the set of participants a priori unknown. 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, our virtual infrastructure emulation introduces only constant overhead per virtual round emulated. We believe that the techniques developed in this paper help to bring virtual infrastructure one step closer to a reality.
Original languageEnglish
Title of host publicationProceedings of the twenty-seventh ACM symposium on Principles of distributed computing
Place of PublicationToronto, ON, Canada
PublisherACM
Pages233-242
Number of pages10
ISBN (Print)978-1-59593-989-0
DOIs
Publication statusPublished - Aug 2008
Event27th ACM symposium on Principles of distributed computing - Toronto, ON, Canada
Duration: 18 Aug 200821 Aug 2008

Conference

Conference27th ACM symposium on Principles of distributed computing
CountryCanada
CityToronto, ON
Period18/08/0821/08/08
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 10507241