Asynchronous Gossip in Smartphone Peer-to-Peer Networks
In this paper, we study gossip algorithms in communication models that describe the peer-to-peer networking functionality included in most standard smartphone operating systems. We begin by describing and analyzing a new synchronous gossip algorithm in this setting that features both a faster round...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2102.06804 http://arxiv.org/abs/2102.06804 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1879172788424540160 |
|---|---|
| author | Newport, Calvin Weaver, Alex Zheng, Chaodong |
| author_browse | Newport, Calvin Weaver, Alex Zheng, Chaodong |
| author_facet | Newport, Calvin Weaver, Alex Zheng, Chaodong |
| author_sort | Newport, Calvin |
| building | arXiv |
| collection | Acceso abierto |
| description | In this paper, we study gossip algorithms in communication models that describe the peer-to-peer networking functionality included in most standard smartphone operating systems. We begin by describing and analyzing a new synchronous gossip algorithm in this setting that features both a faster round complexity and simpler operation than the best-known existing solutions. We also prove a new lower bound on the rounds required to solve gossip that resolves a minor open question by establishing that existing synchronous solutions are within logarithmic factors of optimal. We then adapt our synchronous algorithm to produce a novel gossip strategy for an asynchronous model that directly captures the interface of a standard smartphone peer-to-peer networking library (enabling algorithms described in this model to be easily implemented on real phones). Using new analysis techniques, we prove that this asynchronous strategy efficiently solves gossip. This is the first known efficient asynchronous information dissemination result for the smartphone peer-to-peer setting. We argue that our new strategy can be used to implement effective information spreading subroutines in real world smartphone peer-to-peer network applications, and that the analytical tools we developed to analyze it can be leveraged to produce other broadly useful algorithmic strategies for this increasingly important setting. |
| first_indexed | 2026-10-15T23:46:56Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2102.06804</identifier><datestamp>2021-02-16</datestamp>
<dc:title>Asynchronous Gossip in Smartphone Peer-to-Peer Networks</dc:title>
<dc:creator>Newport, Calvin</dc:creator>
<dc:creator>Weaver, Alex</dc:creator>
<dc:creator>Zheng, Chaodong</dc:creator>
<dc:subject>Distributed, Parallel, and Cluster Computing</dc:subject>
<dc:description>In this paper, we study gossip algorithms in communication models that describe the peer-to-peer networking functionality included in most standard smartphone operating systems. We begin by describing and analyzing a new synchronous gossip algorithm in this setting that features both a faster round complexity and simpler operation than the best-known existing solutions. We also prove a new lower bound on the rounds required to solve gossip that resolves a minor open question by establishing that existing synchronous solutions are within logarithmic factors of optimal. We then adapt our synchronous algorithm to produce a novel gossip strategy for an asynchronous model that directly captures the interface of a standard smartphone peer-to-peer networking library (enabling algorithms described in this model to be easily implemented on real phones). Using new analysis techniques, we prove that this asynchronous strategy efficiently solves gossip. This is the first known efficient asynchronous information dissemination result for the smartphone peer-to-peer setting. We argue that our new strategy can be used to implement effective information spreading subroutines in real world smartphone peer-to-peer network applications, and that the analytical tools we developed to analyze it can be leveraged to produce other broadly useful algorithmic strategies for this increasingly important setting. </dc:description>
<dc:date>2021-02-12</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2102.06804</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2102.06804</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2102.06804 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:46:56Z |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| record_format | oai_dc |
| spelling | arxiv-2102.068042021-02-16 Asynchronous Gossip in Smartphone Peer-to-Peer Networks Newport, Calvin Weaver, Alex Zheng, Chaodong Distributed, Parallel, and Cluster Computing In this paper, we study gossip algorithms in communication models that describe the peer-to-peer networking functionality included in most standard smartphone operating systems. We begin by describing and analyzing a new synchronous gossip algorithm in this setting that features both a faster round complexity and simpler operation than the best-known existing solutions. We also prove a new lower bound on the rounds required to solve gossip that resolves a minor open question by establishing that existing synchronous solutions are within logarithmic factors of optimal. We then adapt our synchronous algorithm to produce a novel gossip strategy for an asynchronous model that directly captures the interface of a standard smartphone peer-to-peer networking library (enabling algorithms described in this model to be easily implemented on real phones). Using new analysis techniques, we prove that this asynchronous strategy efficiently solves gossip. This is the first known efficient asynchronous information dissemination result for the smartphone peer-to-peer setting. We argue that our new strategy can be used to implement effective information spreading subroutines in real world smartphone peer-to-peer network applications, and that the analytical tools we developed to analyze it can be leveraged to produce other broadly useful algorithmic strategies for this increasingly important setting. 2021-02-12 text https://arxiv.org/abs/2102.06804 http://arxiv.org/abs/2102.06804 |
| spellingShingle | Distributed, Parallel, and Cluster Computing Newport, Calvin Weaver, Alex Zheng, Chaodong Asynchronous Gossip in Smartphone Peer-to-Peer Networks |
| title | Asynchronous Gossip in Smartphone Peer-to-Peer Networks |
| title_full | Asynchronous Gossip in Smartphone Peer-to-Peer Networks |
| title_fullStr | Asynchronous Gossip in Smartphone Peer-to-Peer Networks |
| title_full_unstemmed | Asynchronous Gossip in Smartphone Peer-to-Peer Networks |
| title_short | Asynchronous Gossip in Smartphone Peer-to-Peer Networks |
| title_sort | asynchronous gossip in smartphone peer to peer networks |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2102.06804 http://arxiv.org/abs/2102.06804 |
| work_keys_str_mv | AT newportcalvin asynchronousgossipinsmartphonepeertopeernetworks AT weaveralex asynchronousgossipinsmartphonepeertopeernetworks AT zhengchaodong asynchronousgossipinsmartphonepeertopeernetworks |