English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give a time-randomness tradeoff for the quasi-random rumor spreadingprotocol proposed by Doerr, Friedrich and Sauerwald [SODA 2008] on completegraphs. In this protocol, the goal is to spread a piece of informationoriginating from one vertex throughout the network. Each vertex is assumed tohave a (cyclic) list of its neighbors. Once a vertex is informed by one of itsneighbors, it chooses a position in its list uniformly at random and theninforms its neighbors starting from that position and proceeding in order ofthe list. Angelopoulos, Doerr, Huber and Panagiotou [Electron.~J.~Combin.~2009]showed that after $(1+o(1))(\log_2 n + \ln n)$ rounds, the rumor will have beenbroadcasted to all nodes with probability $1 - o(1)$.  We study the broadcast time when the amount of randomness available at eachnode is reduced in natural way. In particular, we prove that if each node canonly make its initial random selection from every $\ell$-th node on its list,then there exists lists such that $(1-\varepsilon) (\log_2 n + \ln n - \log_2\ell - \ln \ell)+\ell-1$ steps are needed to inform every vertex withprobability at least $1-O\bigl(\exp\bigl(-\frac{n^\varepsilon}{2\lnn}\bigr)\bigr)$. This shows that a further reduction of the amount ofrandomness used in a simple quasi-random protocol comes at a loss ofefficiency.

Quasi-Random Rumor Spreading: Reducing Randomness Can Be Costly