1 Search Results for "Weaver, Alex"

Document

DOI: 10.4230/LIPIcs.DISC.2019.14

The Capacity of Smartphone Peer-To-Peer Networks

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

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.DISC.2019.14,
  author =	{Dinitz, Michael and Halld\'{o}rsson, Magn\'{u}s M. and Newport, Calvin and Weaver, Alex},
  title =	{{The Capacity of Smartphone Peer-To-Peer Networks}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.14},
  URN =		{urn:nbn:de:0030-drops-113218},
  doi =		{10.4230/LIPIcs.DISC.2019.14},
  annote =	{Keywords: Capacity, Wireless, Mobile Telephone, Throughput}
}

Refine by Author
1 Dinitz, Michael
1 Halldórsson, Magnús M.
1 Newport, Calvin
1 Weaver, Alex

Refine by Classification
1 Computing methodologies → Distributed algorithms
1 Networks → Network algorithms

Refine by Keyword
1 Capacity
1 Mobile Telephone
1 Throughput
1 Wireless

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Weaver, Alex"

The Capacity of Smartphone Peer-To-Peer Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message