The Capacity of Smartphone Peer-To-Peer Networks

Authors Michael Dinitz, Magnús M. Halldórsson, Calvin Newport, Alex Weaver



PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.14.pdf
  • Filesize: 458 kB
  • 17 pages

Document Identifiers

Author Details

Michael Dinitz
  • Johns Hopkins University, Baltimore, MD, United States
Magnús M. Halldórsson
  • Reykjavík University, Iceland
Calvin Newport
  • Georgetown University, Washington, DC, United States
Alex Weaver
  • Georgetown University, Washington, DC, United States

Cite AsGet BibTex

Michael Dinitz, Magnús M. Halldórsson, Calvin Newport, and Alex Weaver. The Capacity of Smartphone Peer-To-Peer Networks. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.14

Abstract

We study three capacity problems in the mobile telephone model, a network abstraction that models the peer-to-peer communication capabilities implemented in most commodity smartphone operating systems. The capacity of a network expresses how much sustained throughput can be maintained for a set of communication demands, and is therefore a fundamental bound on the usefulness of a network. Because of this importance, wireless network capacity has been active area of research for the last two decades. The three capacity problems that we study differ in the structure of the communication demands. The first problem is pairwise capacity, where the demands are (source, destination) pairs. Pairwise capacity is one of the most classical definitions, as it was analyzed in the seminal paper of Gupta and Kumar on wireless network capacity. The second problem we study is broadcast capacity, in which a single source must deliver packets to all other nodes in the network. Finally, we turn our attention to all-to-all capacity, in which all nodes must deliver packets to all other nodes. In all three of these problems we characterize the optimal achievable throughput for any given network, and design algorithms which asymptotically match this performance. We also study these problems in networks generated randomly by a process introduced by Gupta and Kumar, and fully characterize their achievable throughput. Interestingly, the techniques that we develop for all-to-all capacity also allow us to design a one-shot gossip algorithm that runs within a polylogarithmic factor of optimal in every graph. This largely resolves an open question from previous work on the one-shot gossip problem in this model.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Distributed algorithms
  • Networks → Network algorithms
Keywords
  • Capacity
  • Wireless
  • Mobile Telephone
  • Throughput

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Gianluca Aloi, Marco Di Felice, Valeria Loscrì, Pasquale Pace, and Giuseppe Ruggeri. Spontaneous smartphone networks as a user-centric solution for the future internet. IEEE Communications Magazine, 52(12):26-33, 2014. Google Scholar
  2. Apple. MultipeerConnectivity | Apple Developer Documentation. Internet: https://developer.apple.com/documentation/multipeerconnectivity [Accessed : 07 2018], 2018.
  3. Daniel Camps-Mur, Andres Garcia-Saavedra, and Pablo Serrano. Device-to-device communications with Wi-Fi Direct: Overview and experimentation. IEEE Wireless Communications, 20(3):96-104, 2013. Google Scholar
  4. Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. Rumour Spreading and Graph Conductance. In Proceedings of the ACM-SIAM symposium on Discrete Algorithms (SODA), 2010. Google Scholar
  5. Vasek Chvátal. Tough graphs and Hamiltonian circuits. Discrete Mathematics, 5(3):215-228, 1973. Google Scholar
  6. Sebastian Daum, Fabian Kuhn, and Yannic Maus. Rumor spreading with bounded in-degree. In Proceedings of the International Colloquium on Structural Information and Communication Complexity, 2016. Google Scholar
  7. Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport. Load balancing with bounded convergence in dynamic networks. In INFOCOM, pages 1-9, 2017. Google Scholar
  8. Michael Dinitz, Magnús M. Halldórsson, Taisuke Izumi, and Calvin Newport. Distributed Minimum Degree Spanning Trees. In Proceedings of the ACM Symposium on the Principles of Distributed Computing (PODC), 2019 (to appear.). Google Scholar
  9. Nikolaos Fountoulakis and Konstantinos Panagiotou. Rumor spreading on random regular graphs and expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 560-573. Springer, 2010. Google Scholar
  10. Alan M Frieze and Geoffrey R Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10(1):57-77, 1985. Google Scholar
  11. Martin Fürer and Balaji Raghavachari. Approximating the Minimum-Degree Steiner Tree to within One of Optimal. Journal of Algorithms, 17(3):409-423, 1994. Google Scholar
  12. Open Garden. FireChat. Internet: https://www.opengarden.com/ [Accessed: 07 2018], 2018.
  13. Open Garden. The Open Garden Hotspot. Internet: https://www.opengarden.com/ [Accessed: 07 2018], 2018.
  14. Mohsen Ghaffari and Calvin Newport. How to Discreetly Spread a Rumor in a Crowd. In Proceedings of the International Symposium on Distributed Computing (DISC), 2016. Google Scholar
  15. George Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2011. Google Scholar
  16. George Giakkoupis. Tight bounds for rumor spreading with vertex expansion. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. Google Scholar
  17. George Giakkoupis and Thomas Sauerwald. Rumor spreading and vertex expansion. In Proceedings of the ACM-SIAM symposium on Discrete Algorithms (SODA), pages 1623-1641. SIAM, 2012. Google Scholar
  18. Carles Gomez, Joaquim Oller, and Josep Paradells. Overview and evaluation of Bluetooth low energy: An emerging low-power wireless technology. Sensors, 12(9):11734-11753, 2012. Google Scholar
  19. Piyush Gupta and Panganmala R Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388-404, 2000. Google Scholar
  20. Adrian Holzer, Sven Reber, Jonny Quarta, Jorge Mazuze, and Denis Gillet. Padoc: Enabling social networking in proximity. Computer Networks, 111:82-92, 2016. Google Scholar
  21. Zongqing Lu, Guohong Cao, and Thomas La Porta. Networking smartphones for disaster recovery. In Proceedings of the IEEE International Conference on Pervasive Computing and Communications (PerCom), pages 1-9. IEEE, 2016. Google Scholar
  22. Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC), pages 121-130. ACM, 2010. Google Scholar
  23. David Mark, Jayant Varma, Jeff LaMarche, Alex Horovitz, and Kevin Kim. Peer-to-Peer Using Multipeer Connectivity. In More iPhone Development with Swift, pages 239-280. Springer, 2015. Google Scholar
  24. Calvin Newport. Leader Election in a Smartphone Peer-to-Peer Network. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2017. Full version available online at: URL: http://people.cs.georgetown.edu/~cnewport/pubs/le-IPDPS2017.pdf.
  25. Calvin Newport and Alex Weaver. Random Gossip Processes in Smartphone Peer-to-Peer Networks. In Proceedings of the International Conference on Distributed Computing in Sensor Systems (DCOSS), 2019. Google Scholar
  26. DG Reina, Mohamed Askalani, SL Toral, Federico Barrero, Eleana Asimakopoulou, and Nik Bessis. A survey on multihop ad hoc networks for disaster response scenarios. International Journal of Distributed Sensor Networks, 11(10):647037, 2015. Google Scholar
  27. Claude E Shannon. A theorem on coloring the lines of a network. Journal of Mathematics and Physics, 28(1-4):148-152, 1949. Google Scholar
  28. Noriyuki Suzuki, Jane Louie Fresco Zamora, Shigeru Kashihara, and Suguru Yamaguchi. Soscast: Location estimation of immobilized persons through sos message propagation. In Proceedings of the International Conference on Intelligent Networking and Collaborative Systems (INCoS), pages 428-435. IEEE, 2012. Google Scholar
  29. Sein Win. On a connection between the existence of k-trees and the toughness of a graph. Graphs and Combinatorics, 5(1):201-205, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail