ABSTRACT
Opportunistic networks are partially connected wireless ad hoc networks, in which pairwise unpredicted transient contacts between mobile devices are the only opportunities for these devices to exchange information or services. Ensuring the coordination of multiple parts of a distributed application in such conditions is a challenge. This paper presents a system that can solve consensus problems in an opportunistic network. This system combines an implementation of the One-Third Rule (OTR) algorithm with a communication layer that supports network-wide, content-driven message dissemination based on controlled epidemic routing. Experimental results obtained with a small flotilla of smartphones are also presented, that validate the system and demonstrate that consensus can be solved effectively in an opportunistic network.
- V. Arnaboldi, M. Conti, and F. Delmastro. CAMEO: A Novel Context-Aware Middleware for Opportunistic Mobile Social Networks. Pervasive and Mobile Computing, 2013.Google Scholar
- J. Augustine, G. Pandurangan, and P. Robinson. Fast Byzantine Agreement in Dynamic Networks. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC '13, pages 74--83, New York, NY, USA, 2013. ACM. Google ScholarDigital Library
- A. Benchi, F. Guidec, and P. Launay. A Message Service for Opportunistic Computing in Disconnected MANETs. In 12th IFIP International Conference on Distributed Applications and Interoperable Systems, pages 118--131, Stockholm, Sweden, June 2012. Springer. Google ScholarDigital Library
- A. Benchi, P. Launay, and F. Guidec. A P2P Tuple Space Implementation for Disconnected MANETs. Peer-to-Peer Networking and Applications, pages 1--16, Aug. 2013.Google Scholar
- C. Boldrini, M. Conti, and A. Passarella. Context and Resource Awareness in Opportunistic Network Data Dissemination. In The Second IEEE WoWMoM Workshop on Autonomic and Opportunistic Communications, Newport Beach, CA, USA, June 2008. Google ScholarDigital Library
- C. Boldrini, K. Lee, M. Önen, J. Ott, and E. Pagani. Opportunistic networks. Computer Communications, pages 1--4, March 2014.Google Scholar
- F. Borran, R. Prakash, and A. Schiper. Extending Paxos/LastVoting with an Adequate Communication Layer for Wireless Ad Hoc Networks. In 2008 Symposium on Reliable Distributed Systems, page 227--236. IEEE, 2008. Google ScholarDigital Library
- F. V. Brasileiro, F. Greve, A. Mostéfaoui, and M. Raynal. Consensus in One Communication Step. In Parallel Computing Technologies, volume 2127 of LNCS, pages 42--50. Springer, 2001. Google ScholarDigital Library
- A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-Varying Graphs and Dynamic Networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387--408, Apr. 2012. Google ScholarDigital Library
- D. Cavin, Y. Sasson, and A. Schiper. Consensus with Unknown Participants or Fundamental Self-Organization. In ADHOC-NOW, volume 3158 of LNCS, pages 135--148. Springer, 2004.Google ScholarCross Ref
- D. Cavin, Y. Sasson, and A. Schiper. Reaching Agreement with Unknown Participants in Mobile Self-Organized Networks in Spite of Process Crashes. Technical report, 2005.Google Scholar
- A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of Human Mobility on Opportunistic Forwarding Algorithms. IEEE Transactions on Mobile Computing, 6(6):606--620, jun 2007. Google ScholarDigital Library
- B. Charron-Bost and A. Schiper. The Heard-Of Model: Computing in Distributed Systems With Benign Faults. Distributed Computing, 22(1):49--71, 2009.Google ScholarDigital Library
- L.-J. Chen, C.-H. Yu, C.-L. Tseng, H.-H. Chu, and C.-F. Chou. A Content-Centric Framework for Effective Data Dissemination in Opportunistic Networks. IEEE Journal of Selected Areas in Communications, 2008. Google ScholarDigital Library
- M. Conti, S. Giordano, M. May, and A. Passarella. From Opportunistic Networks to Opportunistic Computing. IEEE Communications Magazine, 48(9):126--139, Sept. 2010. Google ScholarDigital Library
- M. Conti, E. Marzini, D. Mascitti, A. Passarella, and L. Ricci. Service Selection and Composition in Opportunistic Networks. In 9th IEEE International Wireless Communications and Mobile Computing Conference, pages 1565--1572. IEEE CS, July 2013.Google Scholar
- A. Datta, S. Quarteroni, and K. Aberer. Autonomous Gossiping: a Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Mobile Ad Hoc Networks. In International Conference on Semantics of a Networked World, number 3226 in LNCS, pages 126--143, Paris, France, June 2004.Google ScholarCross Ref
- K. Fall. A Delay-Tolerant Network Architecture for Challenged Internets. In Proceedings of The 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 27--34, New York, USA, 2003. ACM. Google ScholarDigital Library
- M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of Distributed Consensus With One Faulty Process. Journal of the ACM, 32(2):374--382, Apr 1985. Google ScholarDigital Library
- F. Greve and S. Tixeuil. Knowledge Connectivity vs. Synchrony Requirements for Fault-Tolerant Agreement in Unknown Networks. In Dependable Systems and Networks, 2007. 37th Annual IEEE/IFIP International Conference on, pages 82--91, June 2007. Google ScholarDigital Library
- R. Guerraoui, F. Huc, and A.-M. Kermarrec. Highly Dynamic Distributed Computing with Byzantine Failures. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC '13, pages 176--183. ACM, 2013. Google ScholarDigital Library
- J. Haillot and F. Guidec. A Protocol for Content-Based Communication in Disconnected Mobile Ad Hoc Networks. Journal of Mobile Information Systems, 6(2):123--154, 2010. Google ScholarDigital Library
- K. A. Harras, K. C. Almeroth, and E. M. Belding-Royer. Delay Tolerant Mobile Networks (DTMNs): Controlled Flooding in Sparse Mobile Networks. In IFIP Networking Conference, Waterloo, Ontario, Canada, May 2005. Google ScholarDigital Library
- P. Hui, J. Crowcroft, and E. Yoneki. BUBBLE Rap: Social Based Forwarding in Delay Tolerant Networks. In 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 241--250, Hong Kong, China, may 2008. ACM. Google ScholarDigital Library
- P. Hui, E. Yoneki, S.-Y. Chan, and J. Crowcroft. Distributed Community Detection in Delay Tolerant Networks. In Sigcomm Workshop MobiArch, Kyoto, Japan, aug 2007. Google ScholarDigital Library
- M. J. Khabbaz, A. Chadi M., and F. Wissam F. Disruption-Tolerant Networking: a Comprehensive Survey on Recent Developments and Persisting Challenges. IEEE Communications Surveys and Tutorials, 14(2):607--640, 2012.Google ScholarCross Ref
- A. Lindgren, A. Doria, and O. Schelen. Probabilistic Routing in Intermittently Connected Networks. In Proceedings of the 1st International Workshop on Service Assurance with Partial and Intermittent Resources, Fortaleza, Brazil, Aug. 2004.Google ScholarCross Ref
- A. Makke, Y. Mahéo, and N. Le Sommer. Towards Opportunistic Service Provisoning in Intermittently Connected Hybrid Networks. In 4th International Conference on Networking and Distributed Computing, pages 28--32, Honk Kong, China, Dec. 2013. IEEE CS. Google ScholarDigital Library
- M. Musolesi, B. Hui, C. Mascolo, and J. Crowcroft. Writing on the Clean Slate: Implementing a Socially-Aware Protocol in Haggle. In IEEE International Workshop on Autonomic and Opportunistic Communications, Newport Beach, CA, jun 2008. Google ScholarDigital Library
- H. A. Nguyen and S. Giordano. Routing in Opportunistic Networks. International Journal of Ambient Computing and Intelligence, 1(3):19--38, 2009.Google ScholarCross Ref
- H. A. Nguyen, S. Giordano, and A. Puiatti. Probabilistic Routing Protocol for Intermittently Connected Mobile Ad hoc Network (PROPICMAN). In International Symposium on a World of Wireless, Mobile and Multimedia Networks, pages 1--6, Helsinky, Finland, June 2007. IEEE CS.Google ScholarCross Ref
- L. Pelusi, A. Passarella, and M. Conti. Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks. IEEE Communications Magazine, 44(11):134--141, Nov. 2006. Google ScholarDigital Library
- R. F. P. Quelhas. Improving Opportunistic with Social Context Communications. PhD thesis, Universidade do Minho, Escola de Engenharia, Oct. 2011.Google ScholarDigital Library
- J. Scott, P. Hui, J. Crowcroft, and C. Diot. Haggle: a Networking Architecture Designed Around Mobile Users. In Proceedings of the 2006 IFIP Conference on Wireless on Demand Network Systems and Services, Jan. 2006.Google Scholar
- J. P. Tower and T. D. Little. A Proposed Scheme for Epidemic Routing With Active Curing for Opportunistic Networks. In 2008 22nd International Workshops on Advanced Information Networking and Applications (AINA Workshops), pages 1696--1701. IEEE, 2008. Google ScholarDigital Library
- A. Triviño-Cabrera and S. Cañadas-Hurtado. Survey on Opportunistic Routing in Multihop Wireless Networks. International Journal of Communication Networks and Information Security, 3(2), Aug. 2011.Google Scholar
- A. Vahdat and D. Becker. Epidemic Routing for Partially Connected Ad Hoc Networks. Technical report, Duke University, Apr. 2000.Google Scholar
- E. W. Vollset and P. D. Ezhilchelvan. Design and Performance-Study of Crash-Tolerant Protocols for Broadcasting and Reaching Consensus in MANETs. In Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, volume 0, page 166--178, Washington, DC, USA, 2005. IEEE Computer Society. Google ScholarDigital Library
- W. Wu, J. Cao, J. Yang, and M. Raynal. Design and Performance Evaluation of Efficient Consensus Protocols for Mobile Ad Hoc Networks. IEEE Transactions on Computers, 56(8):1055--1070, 2007. Google ScholarDigital Library
- Z. Zhang. Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges. IEEE Communications Surveys and Tutorials, 8(1):24--37, Jan. 2006. Google ScholarDigital Library
Index Terms
- Solving Consensus in Opportunistic Networks
Recommendations
Consensus in Sparse, Mobile Ad Hoc Networks
Consensus is central to several applications including collaborative ones which a wireless ad hoc network can facilitate for mobile users in terrains with no infrastructure support for communication. We solve the consensus problem in a sparse network in ...
A cooperative cache-based content delivery framework for intermittently connected mobile ad hoc networks
For an infrastructure-less wireless environment, content dissemination among mobile users can be facilitated by self-organizing mobile ad hoc networks (MANETs) through low cost wireless connections. However, due to limited radio transmission range, ...
Location-Based Service Discovery and Delivery in Opportunistic Networks
ICN '10: Proceedings of the 2010 Ninth International Conference on NetworksOpportunistic networks are usually formed spontaneously by mobile devices equipped with short range wireless communication interfaces. Designing and implementing a routing protocol to support both service discovery and delivery in such kinds of networks ...
Comments