Title: Randomized Rumor Spreading in Ad Hoc Networks with Buffers,
Abstract: The randomized rumor spreading problem generates a big interest in the area
of distributed algorithms due to its simplicity, robustness and wide range of
applications. The two most popular communication paradigms used for spreading
the rumor are Push and Pull algorithms. The former protocol allows nodes to
send the rumor to a randomly selected neighbor at each step, while the latter
is based on sending a request and downloading the rumor from a randomly
selected neighbor, provided the neighbor has it. Previous analysis of these
protocols assumed that every node could process all such push/pull operations
within a single step, which could be unrealistic in practical situations.
Therefore we propose a new framework for analysis rumor spreading accommodating
buffers, in which a node can process only one push/pull message or push request
at a time. We develop upper and lower bounds for randomized rumor spreading
time in the new framework, and compare the results with analogous in the old
framework without buffers.