10 citations · 43 across the 22 of their papers we have counts for
5 papers · 1 filter
Time and Space Optimal Exact Majority Population Protocols
Leszek Gąsieniec, Grzegorz Stachowiak, Przemysław Uznański
In this paper we study population protocols governed by the {\em random scheduler}, which uniformly at random selects pairwise interactions between agents. The main result of t…
Robust Comparison in Population Protocols
Dan Alistarh, Martin Töpfer, Przemysław Uznański
There has recently been a surge of interest in the computational and complexity properties of the population model, which assumes anonymous, computationally-bounded nodes, inte…
Almost logarithmic-time space optimal leader election in population protocols
Leszek Gąsieniec, Grzegorz Stachowiak, Przemysław Uznański
The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called {\em agents}. The agents communicate and perform computation…
Distributed Colour Reduction Revisited
Jukka Kohonen, Janne H. Korhonen, Christopher Purcell +2
We give a new, simple distributed algorithm for graph colouring in paths and cycles. Our algorithm is fast and self-contained, it does not need any globally consistent orientation,…
LCL problems on grids
Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen +6
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cy…