  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.
