Virtual infrastructure for collision-prone wireless networks

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.

REFERENCES

• 1: Marcos K. Aguilera , Svend Frolund , Vassos Hadzilacos , Stephanie L. Horn , Sam Toueg, Abortable and query-abortable objects and their efficient implementation, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281107]
• 2: Lali Barriére , Pierre Fraigniaud , Lata Narayanan, Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.19-27, July 2001, Rome, Italy [doi>10.1145/381448.381451]
• 3: M. D. Brown. Air traffic control using virtual stationary automata. Master's thesis, MIT, Sept. 2007.
• 4: M. Brown, S. Gilbert, N. A. Lynch, C. Newport, T. Nolte, and M. Spindel. The virtual node layer: A programming abstraction for wireless sensor networks. In WSNA, April 2007.
• 5: C. Busch, M. Magdon-Ismail, F. Sivrikaya, and B. Yener. Contention-free mac protocols for wireless sensor networks. In DISC, Oct. 2004.
• 6: Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002 [doi>10.1145/571637.571640]
• 7: Gregory Chockler , Murat Demirbas , Seth Gilbert , Nancy Lynch , Calvin Newport , Tina Nolte, Reconciling the Theory and Practice of (Un)Reliable Wireless Broadcast, Proceedings of the Fourth International Workshop on Assurance in Distributed Systems and Networks (ADSN) (ICDCSW'05), p.42-48, June 06-10, 2005 [doi>10.1109/ICDCSW.2005.120]
• 8: Gregory Chockler , Murat Demirbas , Seth Gilbert , Calvin Newport , Tina Nolte, Consensus and collision detectors in wireless Ad Hoc networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073850]
• 9: G. Chockler, M. Demirbas, S. Gilbert, N. Lynch, C. Newport, and T. Nolte. Consensus and collision detectors in radio networks. Distributed Computing, 21(1):55--84, June 2008.
• 10: J. Deng, P. K. Varshney, and Z. J. Haas. A new backoff algorithm for the IEEE 802.11 distributed coordination function. In Communication Networks and Distributed Systems Modeling and Simulation, Jan. 2004.
• 11: S. Dolev, S. Gilbert, L. Lahiani, N. A. Lynch, and T. Nolte. Virtual stationary automata for mobile networks. In OPODIS, 2005.
• 12: S. Dolev, S. Gilbert, N. A. Lynch, E. Schiller, A. A. Shvartsman, and Jennifer L. Welch. Virtual mobile nodes for mobile ad hoc networks. In DISC, Oct. 2004.
• 13: S. Dolev, S. Gilbert, N. A. Lynch, Alex A. Shvartsman, and Jennifer Welch. Geoquorums: Implementing atomic memory in mobile ad hoc networks. In DISC, Oct. 2003.
• 14: Shlomi Dolev , Seth Gilbert , Nancy A. Lynch , Alexander A. Shvartsman , Jennifer L. Welch, GeoQuorums: implementing atomic memory in mobile ad hoc networks, Distributed Computing, v.18 n.2, p.125-155, December 2005 [doi>10.1007/s00446-005-0140-9]
• 15: Shlomi Dolev , Seth Gilbert , Elad Schiller , Alex Shvartsman , Jennifer Welch, Autonomous virtual mobile nodes, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074004]
• 16: S. Dolev, L. Lahiani, N. A. Lynch, and T. Nolte. Self-stabilizing mobile node location management and message routing. In SSS, Oct. 2005.
• 17: R. Droms and C. Newport. Virtual infrastructure routing for mobile ad hoc networks. Manuscript, 2007.
• 18: R. Gallager. A perspective on multiaccess channels. IEEE Trans. Information Theory, IT-31:124--142, 1985.
• 19: Seth Gilbert , Nancy Lynch, Virtual infrastructure for wireless ad hoc networks, Massachusetts Institute of Technology, Cambridge, MA, 2007
• 20: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 21: T. Herman and S. Tixeuil. A distributed TDMA slot assignment algorithm for wireless sensor networks. In Workshop on Algorithmic Aspects of Wireless Sensor Networks, 2004.
• 22: Idit Keidar , Danny Dolev, Increasing the resilience of atomic commit, at no additional cost, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.245-254, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212468]
• 23: I. Keidar and D. Dolev. Broadcast in the face of network partitions: Exploiting group communication for replication in partitionable networks. D. Avresky, ed., Dependable Network Computing, chapter 3. Kluwer Academic Publications, 2000.
• 24: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 25: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 26: Butler W. Lampson, How to Build a Highly Available System Using Consensus, Proceedings of the 10th International Workshop on Distributed Algorithms, p.1-17, October 09-11, 1996
• 27: N. A. Lynch, S. Mitra, and T. Nolte. Motion coordination using virtual nodes. In CDC, Dec. 2005.
• 28: Tal Mizrahi , Yoram Moses, Continuous consensus via common knowledge, Proceedings of the 10th conference on Theoretical aspects of rationality and knowledge, June 10-12, 2005, Singapore
• 29: Tal Mizrahi and Yoram Moses. Long Live Continuous Consensus. In DISC, 2007.
• 30: Tal Mizrahi and Yoram Moses. Continuous Consensus with Ambiguous Failures. In ICDCN, 2008.
• 31: Koji Nakano , Stephan Olariu, Uniform Leader Election Protocols in Radio Networks, Proceedings of the 2001 International Conference on Parallel Processing, p.240-250, September 03-07, 2001
• 32: K. Nakano and S. Olariu. A survey on leader election protocols for radio networks. In I-SPAN, 2002.
• 33: Ryan Newton , Arvind , Matt Welsh, Building up to macroprogramming: an intermediate language for sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 34: Tina Nolte. Virtual Stationary Timed Automata for Mobile Networks. PhD thesis, MIT, To appear: 2008.
• 35: T. Nolte and N. A. Lynch. Self-stabilization and virtual node layer emulations. In SSS, Nov. 2007.
• 36: Tina Nolte , Nancy Lynch, A Virtual Node-Based Tracking Algorithm for Mobile Networks, Proceedings of the 27th International Conference on Distributed Computing Systems, p.1, June 25-27, 2007 [doi>10.1109/ICDCS.2007.82]
• 37: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 38: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 39: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 40: M. Spindel. Simulation and evaluation of the virtual node layer. Master's thesis, MIT, June 2008.
• 41: Dale Skeen, Nonblocking commit protocols, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582339]
• 42: D. Skeen. A quorum-based commit protocol. In Berkeley Workshop, 1982.
• 43: Matt Welsh , Geoff Mainland, Programming sensor networks using abstract regions, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.3-3, March 29-31, 2004, San Francisco, California
• 44: Kamin Whitehouse , Cory Sharp , Eric Brewer , David Culler, Hood: a neighborhood abstraction for sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990079]
• 45: Dan E Willard, Log-logarithmic selection resolution protocols in a multiple access channel, SIAM Journal on Computing, v.15 n.2, p.468-477, May 1986 [doi>10.1137/0215032]
• 46: A. Woo, K. Whitehouse, F. Jiang, J. Polastre, and D. Culler. The shadowing phenomenon: implications of receiving during a collision. Technical Report UCB//CSD-04-1313, UC Berkeley, March 2004.
• 47: J. Wu. Title pending. PhD thesis, CUNY, To appear: 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

General Terms:
Algorithms, Reliability

Keywords:
fault tolerance, mobile ad hoc networks