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 study a simple random process that computes a maximal independent set(MIS) on a general $n$-vertex graph. Each vertex has a binary state, black orwhite, where black indicates inclusion into the MIS. The vertex states arearbitrary initially, and are updated in parallel: In each round, every vertexwhose state is ``inconsistent'' with its neighbors', i.e., it is black and hasa black neighbor, or it is white and all neighbors are white, changes its statewith probability $1/2$. The process stabilizes with probability 1 on any graph,and the resulting set of black vertices is an MIS. It is also easy to see thatthe expected stabilization time is $O(\log n)$ on certain graph families, suchas cliques and trees. However, analyzing the process on graphs beyond thesesimple cases seems challenging.  Our main result is that the process stabilizes in $\mathrm{poly}(\log n)$rounds w.h.p.\ on $G_{n,p}$ random graphs, for $0\leq p \leq \mathrm{poly}(\logn)\cdot n^{-1/2}$ and $p \geq 1/\mathrm{poly}(\log n)$. Further, an extensionof this process, with larger but still constant vertex state space, stabilizesin $\mathrm{poly}(\log n)$ rounds on $G_{n,p}$ w.h.p., for all $1\leq p\leq 1$.We conjecture that this improved bound holds for the original process as well.In fact, we believe that the original process stabilizes in $\mathrm{poly}(\logn)$ rounds on any given $n$-vertex graph w.h.p. Both processes readilytranslate into distributed/parallel MIS algorithms, which are self-stabilizing,use constant space (and constant random bits per round), and assume restrictedcommunication as in the beeping or the synchronous stone age models. To thebest of our knowledge, no previously known MIS algorithm is self-stabilizing,uses constant space and constant randomness, and stabilizes in$\mathrm{poly}(\log n)$ rounds in general or random graphs.

Distributed Self-Stabilizing MIS with Few States and Weak Communication