publication . Preprint . 2017

Gossip in a Smartphone Peer-to-Peer Network

Newport, Calvin;
Open Access English
  • Published: 26 May 2017
Abstract
In this paper, we study the fundamental problem of gossip in the mobile telephone model: a recently introduced variation of the classical telephone model modified to better describe the local peer-to-peer communication services implemented in many popular smartphone operating systems. In more detail, the mobile telephone model differs from the classical telephone model in three ways: (1) each device can participate in at most one connection per round; (2) the network topology can undergo a parameterized rate of change; and (3) devices can advertise a parameterized number of bits about their state to their neighbors in each round before connection attempts are in...
Subjects
free text keywords: Computer Science - Data Structures and Algorithms, Computer Science - Distributed, Parallel, and Cluster Computing
Download from
21 references, page 1 of 2

[1] FireChat Phone-to-Phone App. http://www.opengarden.com/FireChat.

[2] Latest mobile statistics: key figures (Ericsson Mobility Report). https://www.ericsson.com/mobility-report/latest-mobile-statistics.

[3] Scott Burleigh, Adrian Hooke, Leigh Torgerson, Kevin Fall, Vint Cerf, Bob Durst, Keith Scott, and Howard Weiss. Delay-tolerant networking: an approach to interplanetary internet. IEEE Communications Magazine, 41(6):128-136, 2003.

[4] 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.

[5] Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. Rumour spreading and graph conductance. In Proceedings of the ACM-SIAM symposium on Discrete Algorithms (SODA), 2010. [OpenAIRE]

[6] Sebastian Daum, Fabian Kuhn, and Yannic Maus. Rumor spreading with bounded in-degree. In International Colloquium on Structural Information and Communication Complexity (SIRROCO), 2016.

[7] Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Gossiping in a multi-channel radio network. In Proceedings of the Symposium on Distributed Computing (DISC), 2007. [OpenAIRE]

[8] 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.

[9] Alan M Frieze and Geoffrey R Grimmett. The shortest-path problem for graphs with random arclengths. Discrete Applied Mathematics, 10(1):57-77, 1985. [OpenAIRE]

[10] Alan M Frieze and Geoffrey R Grimmett. The shortest-path problem for graphs with random arclengths. Discrete Applied Mathematics, 10(1):57-77, 1985. [OpenAIRE]

[11] 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. [OpenAIRE]

[12] 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. [OpenAIRE]

[13] 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. [OpenAIRE]

[14] George Giakkoupis. Tight bounds for rumor spreading with vertex expansion. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. [OpenAIRE]

[15] George Giakkoupis and Thomas Sauerwald. Rumor spreading and vertex expansion. In Proceedings of the ACM-SIAM symposium on Discrete Algorithms (SODA), pages 1623-1641, 2012. [OpenAIRE]

21 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue