I am a junior professor (≈ assistant professor) of distributed computing at Humboldt University of Berlin.

My research focuses on theoretical foundations of distributed computing. I also occasionally work in the area of theoretical ecology, mainly using stochastic models to study the dynamics of large-scale ecological communities.

• Theoretical computer science:
  distributed algorithms, graph algorithms, fault-tolerant coordination and synchronisation, stochastic interaction models
• Theoretical ecology:
  stochastic spatial models, community dynamics, habitat loss and fragmentation, individual-based modelling

• November 2024
  I gave a talk about majority consensus in stochastic populations in WAND 2024. The slides are available here.
• June 2024
  Our DISCO SPA research project got funded by the German Research Foundation (DFG).

• 2023–: Junior professor of Distributed Computing (HU Berlin)
  Junior professor (tenure track) at Humboldt University of Berlin
• 2018–2022: Postdoc (IST Austria)
  Postdoctoral researcher at Institute of Science and Technology Austria (IST Austria). Funded by:
  • ISTplus fellowship 2018–2019
  • Marie Skłodowska-Curie Actions Individual Fellowship 2019--2021
• 2016–2017: Postdoc (University of Helsinki)
  Postdoctoral researcher at the Mathematical biology group
• 2012–2016: Doctoral student (University of Helsinki and Aalto University)
  Doctoral student at the Distributed algorithms group
• 2014–2015: Guest researcher (Max Planck Institute for Informatics)
  Guest researcher at the Theory of distributed systems and embedded systems group
• 2011–2012: Researcher (University of Helsinki)
  Researcher in Metapopulation research group

PC memberships: SAND 2025 • DISC 2024 • SIROCCO 2024 • ICDCS 2021 • NetSciCom 2017.

2024

• Majority consensus thresholds for competitive Lotka--Volterra populations
  Matthias Függer, Thomas Nowak and Joel Rybicki • PODC 2024
  
  • Publisher's version
  • arXiv preprint

  ACM Symposium on Principles of Distributed Computing (2024) • doi:10.1145/3662158.3662823

  ---

  Abstract

  One of the key challenges in synthetic biology is devising robust signaling primitives for engineered microbial consortia. In such systems, a fundamental signal amplification problem is the majority consensus problem: given a system with two input species with initial difference of $\Delta$ in population sizes, what is the probability that the system reaches a state in which only the initial majority species is present?

  In this work, we consider a discrete and stochastic version of competitive Lotka--Volterra dynamics, a standard model of microbial community dynamics. We identify new threshold properties for majority consensus under different types of interference competition:

  • We show that under so-called self-destructive interference competition between the two input species, majority consensus can be reached with high probability if the initial difference satisfies $\Delta \in \Omega(\log^2 n)$, where $n$ is the initial population size. This gives an exponential improvement compared to the previously known bound of $\Omega(n \log n)$ by Cho et al. [Distributed Computing, 2021] given for a special case of the competitive Lotka--Volterra model. In contrast, we show that an initial gap of $\Delta \in \Omega(\sqrt{\log n})$ is necessary.
  • On the other hand, we show that under non-self-destructive interference competition, an initial gap of $\Omega(\sqrt{n})$ is necessary to succeed with high probability and that a $\Omega(\sqrt{n \log n})$ gap is sufficient.

  This shows a strong qualitative gap between the performance of self-destructive and non-self-destructive interference competition. Moreover, we show that if in addition the populations exhibit interference competition between the individuals of the same species, then majority consensus cannot always be solved with high probability, no matter what the difference in the initial population counts.

2023

• Wait-free approximate agreement on graphs
  Dan Alistarh, Faith Ellen and Joel Rybicki • Theoretical Computer Science 2023
  
  • Publisher's version
  • Conference version

  Theoretical Computer Science, volume 948, number 113733 (2023) • doi:10.1016/j.tcs.2023.113733

  ---

  Abstract

  Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a node of the graph as input and, if non-faulty, must output a node such that

  • all the outputs are within distance 1 of one another, and
  • each output value lies on a shortest path between two input values.

  From prior work, it is known that there is no wait-free algorithm among n ≥ 3 processes for this problem on any cycle of length c ≥ 4, by reduction from 2-set agreement (Castañeda et al., 2018).

  In this work, we investigate the solvability of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length c ≥ 4, via a generalisation of Sperner’s Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a different class of graphs, which properly contains the class of chordal graphs.

• Sinkless Orientation Made Simple
  Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela and Jara Uitto • SOSA 2023
  
  • Publisher's version
  • arXiv preprint

  SIAM Symposium on Simplicity in Algorithms (2023) • doi:10.1137/1.9781611977585.ch17

  ---

  Abstract

  The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is $\Omega(\log n)$ in the deterministic LOCAL model and $O(\log \log n)$ in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.

2022

• Near-Optimal Leader Election in Population Protocols on Graphs
  Dan Alistarh, Joel Rybicki and Sasha Voitovych • PODC 2022
  
  • Publisher's version
  • arXiv preprint

  41st ACM Symposium on Principles of Distributed Computing (2022) • doi:10.1145/3519270.3538435

  ---

  Abstract

  In the stochastic population protocol model, we are given a connected graph with $n$ nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this model is stable leader election, in which all nodes start in an identical state and the aim is to reach a configuration in which (1) exactly one node is elected as leader and (2) this node remains as the unique leader no matter what sequence of interactions follows. On cliques, the complexity of this problem has recently been settled: time-optimal protocols stabilize in $\Theta(n \log n)$ expected steps using $\Theta(\log \log n)$ states, whereas protocols that use $O(1)$ states require $\Theta(n^2)$ expected steps.

  In this work, we investigate the complexity of stable leader election on general graphs. We provide the first non-trivial time lower bounds for leader election on general graphs, showing that, when moving beyond cliques, the complexity landscape of leader election becomes very diverse: the time required to elect a leader can range from $O(1)$ to $\Theta(n^3)$ expected steps. On the upper bound side, we first observe that there exists a protocol that is time-optimal on many graph families, but uses polynomially-many states. In contrast, we give a near-time-optimal protocol that uses only $O(\log^2n)$ states that is at most a factor $\log n$ slower. Finally, we show that the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor $n \log n$ slower than the fast polynomial-state protocol. Moreover, among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs.

• Brief Annoucement: Locality in online algorithms
  Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela and Aleksandr Tereshchenko • DISC 2022
  
  • arXiv preprint

  36th International Symposium on Distributed Computing (2022)

  ---

  Abstract

  Online algorithms make decisions based on past inputs. In general, the decision may depend on the entire history of inputs. If many computers run the same online algorithm with the same input stream but are started at different times, they do not necessarily make consistent decisions.

  In this work we introduce time-local online algorithms. These are online algorithms where the output at a given time only depends on $T = O(1)$ latest inputs. The use of (deterministic) time-local algorithms in a distributed setting automatically leads to globally consistent decisions.

  Our key observation is that time-local online algorithms (in which the output at a given time only depends on local inputs in the temporal dimension) are closely connected to local distributed graph algorithms (in which the output of a given node only depends on local inputs in the spatial dimension). This makes it possible to interpret prior work on distributed graph algorithms from the perspective of online algorithms.

  We describe an algorithm synthesis method that one can use to design optimal time-local online algorithms for small values of $T$. We demonstrate the power of the technique in the context of a variant of the online file migration problem, and show that e.g. for two nodes and unit migration costs there exists a $3$-competitive time-local algorithm with horizon $T=4$, while no deterministic online algorithm (in the classic sense) can do better. We also derive upper and lower bounds for a more general version of the problem; we show that there is a $6$-competitive deterministic time-local algorithm and a $2.62$-competitive randomized time-local algorithm for any migration cost $\alpha \ge 1$.

• Local mending
  Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki and Jukka Suomela • SIROCCO 2022
  
  • Publisher's version
  • arXiv preprint

  29th International Colloquium on Structural Information and Communication Complexity (2022) • doi:10.1007/978-3-031-09993-9_1

  ---

  Abstract

  In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to ``patch a hole.''

  We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that $O(1)$-mendable problems are also solvable in $O(\log^* n)$ rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem $\Pi$ can be solved in $O(\log^* n)$, there is always a restriction $\Pi' \subseteq \Pi$ that is still efficiently solvable but that is also $O(1)$-mendable.

  We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is $O(1)$, $\Theta(\log n)$, or $\Theta(n)$, while in general graphs the structure is much more diverse.

2021

• Wait-free approximate agreement on graphs
  Dan Alistarh, Faith Ellen and Joel Rybicki • SIROCCO 2021
  
  • Publisher's version
  • arXiv preprint

  28th International Colloquium on Structural Information and Communication Complexity (2021) • doi:10.1007/978-3-030-79527-6_6

  ---

  Abstract

  Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a vertex of the graph as input and, if non-faulty, must output a vertex such that

  • all the outputs are within distance 1 of one another, and
  • each output value lies on a shortest path between two input values.

  From prior work, it is known that there is no wait-free algorithm among $n \ge 3$ processes for this problem on any cycle of length $c \ge 4$, by reduction from 2-set agreement (Castañeda et al., 2018).

  In this work, we investigate the solvability and complexity of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length $c \ge 4$, via a generalisation of Sperner's Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on on these graphs is unsolvable. Furthermore, we show that combinatorial arguments, used by both existing proofs, are necessary, by showing that the impossibility of a wait-free algorithm in the nonuniform iterated snapshot model cannot be proved via an extension-based proof. On the positive side, we present a wait-free algorithm for a class of graphs that properly contains the class of chordal graphs.

• Efficient load-balancing through distributed token dropping
  Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela and Jara Uitto • SPAA 2021
  
  • Publisher's version
  • arXiv preprint

  33th ACM Symposium on Parallelism in Algorithms and Architectures (2021) • doi:10.1145/3409964.3461785

  ---

  Abstract

  We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in $O(\Delta^5)$ rounds in graphs of maximum degree $\Delta$, while we improve it to $O(\Delta^4)$ and also prove a lower bound of $\Omega(\Delta)$. For the more generalproblem of locally optimal semi-matchings, the prior upper bound is $O(S^5)$ and our new algorithm runs in $O(C \cdot S^4)$ rounds, which is an improvement for $C=o(S)$; here $C$ and $S$ are the maximum degrees of customers and servers, respectively.

• Brief announcement: Sinkless orientation is hard also in the supported LOCAL model
  Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid and Jukka Suomela • DISC 2021
  
  • Publisher's version
  • arXiv preprint

  35th International Symposium on Distributed Computing (2021) • doi:10.4230/LIPIcs.DISC.2021.58

  ---

  Abstract

  We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires $\Omega(\log n)$ rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is $\Omega(\log n)$.

• Fast graphical population protocols
  Dan Alistarh, Rati Gelashvili and Joel Rybicki • OPODIS 2021
  
  • Publisher's version
  • arXiv preprint
  • DISC BA

  Conference on Principles of Distributed Systems (2021) • doi:10.4230/LIPIcs.OPODIS.2021.14

  ---

  Abstract

  Let $G$ be a graph on $n$ nodes. In the stochastic population protocol model, a collection of $n$ indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbours first read each other's states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when $G$ is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in $n \operatorname{polylog} n$ pairwise interactions, with high probability, using at most $\operatorname{polylog} n$ states per node.

  In this work, we consider the more general setting where $G$ is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance $\phi$, both leader election and exact majority can be solved in $\phi^{-2} \cdot n \operatorname{polylog} n$ pairwise interactions, with high probability, using at most $\phi^{-2} \cdot \operatorname{polylog} n$ states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.

• Input-dynamic distributed graph algorithms for communication networks
  Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki and Stefan Schmid • Proceedings of the ACM on Measurement and Analysis of Computing Systems 2021
  
  • Publisher's version
  • arXiv preprint
  • SIGMETRICS 2021

  Proceedings of the ACM on Measurement and Analysis of Computing Systems, volume 5, number 1 (2021) • doi:10.1145/3447384

  ---

  Abstract

  Consider a distributed system, where the topology of the communication network remains fixed, but local inputs given to nodes may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner?

  To address this question, we define the batch dynamic CONGEST model, where the communication network $G=(V,E)$ remains fixed and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive,

  • how much time as a function of α we need to update an existing solution, and
  • how much information the nodes have to keep in local memory between batches in order to update the solution quickly.

  We give a general picture of the complexity landscape in this model, including a general framework for lower bounds. In particular, we prove non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.

2020

• Habitat fragmentation and species diversity in competitive communities
  Joel Rybicki, Nerea Abrego and Otso Ovaskainen • Ecology Letters 2020
  
  • Publisher's version

  Ecology Letters, volume 23, pages 506--517 (2020) • doi:10.1111/ele.13450

  ---

  Abstract

  Habitat loss is one of the key drivers of the ongoing decline of biodiversity. However, ecologists still argue about how fragmentation of habitat (independent of habitat loss) affects species richness. The recently proposed habitat amount hypothesis posits that species richness only depends on the total amount of habitat in a local landscape. On the other hand, different empirical studies report contrasting patterns: some find positive and others negative effects of fragmentation per se on species richness. To explain this apparent disparity, we devise a stochastic, spatially-explicit model of competitive species communities in heterogeneous habitats. The model shows that habitat loss and fragmentation have a non-monotone and non-linear effect on the species diversity in competitive communities. When the total amount of habitat is large, fragmentation per se tends to increase species diversity, but if the total amount of habitat is small, the situation is reversed: fragmentation per se decreases species diversity.

2019

• What can observational data reveal about metacommunity processes?
  Otso Ovaskainen, Joel Rybicki and Nerea Abrego • Ecography 2019
  
  • Publisher's version

  Ecography, (2019) • doi:10.1111/ecog.04444

  ---

  Abstract

  A key challenge for community ecology is to understand to what extent observational data can be used to infer the underlying community assembly processes. As different processes can lead to similar or even identical patterns, statistical analyses of non-manipulative observational data never yield undisputable causal inference on the underlying processes. Still, most empirical studies in community ecology are based on observational data, and hence understanding under which circumstances such data can shed light on assembly processes is a central concern for community ecologists. We simulated a spatial agent-based model that generates variation in metacommunity dynamics across multiple axes, including the four classic metacommunity paradigms as special cases. We further simulated a virtual ecologist who analysed snapshot data sampled from the simulations using eighteen output metrics derived from beta-diversity and habitat variation indices, variation partitioning and joint species distribution modelling. Our results indicated two main axes of variation in the output metrics. The first axis of variation described whether the landscape has patchy or continuous variation, and thus was essentially independent of the properties of the species community. The second axis of variation related to the level of predictability of the metacommunity. The most predictable communities were niche-based metacommunities inhabiting static landscapes with marked environmental heterogeneity, such as metacommunities following the species sorting paradigm or the mass effects paradigm. The most unpredictable communities were neutral-based metacommunities inhabiting dynamics landscapes with little spatial heterogeneity, such as metacommunities following the neutral or patch sorting paradigms. The output metrics from joint species distribution modelling yielded generally the highest resolution to disentangle among the simulated scenarios. Yet, the different types of statistical approaches utilized in this study carried complementary information, and thus our results suggest that the most comprehensive evaluation of metacommunity structure can be obtained by combining them.

• Self-stabilising Byzantine clock synchronisation is almost as easy as consensus
  Christoph Lenzen and Joel Rybicki • Journal of the ACM 2019
  
  • Publisher's version
  • arXiv preprint
  • Conference version

  Journal of the ACM, volume 66, number 5 (2019) • doi:10.1145/3339471

  ---

  Abstract

  We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the $n$ nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to $f\lt n/3$ ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner.

  Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem:

  • In the deterministic setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $\Theta(f \log f)$ bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to $\Theta(\log f)$ while retaining the same stabilisation time.
  • In the randomised setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $O(1)$ bits per time unit. We exponentially reduce the stabilisation time to $\mathrm{polylog} f$ while each node broadcasts $\mathrm{polylog} f$ bits per time unit.

  These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.

• Byzantine approximate agreement on graphs
  Thomas Nowak and Joel Rybicki • DISC 2019
  
  • Publisher's version
  • arXiv preprint

  33rd International Symposium on Distributed Computing (2019) • doi:10.4230/LIPIcs.DISC.2019.29

  ---

  Abstract

  Consider a distributed system with $n$ processors out of which $f$ can be Byzantine faulty. In the approximate agreement task, each processor $i$ receives an input value $x_i$ and has to decide on an output value $y_i$ such that

  • the output values are in the convex hull of the non-faulty processors' input values,
  • the output values are within distance $d$ of each other.

  
  Classically, the values are assumed to be from an $m$-dimensional Euclidean space, where $m \ge 1$.

  In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph $G$ and the goal is to output vertices that are within distance $d$ of each other in $G$, but still remain in the graph-induced convex hull of the input values. For $d=0$, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any $d \ge 1$, we show that the task is solvable in asynchronous systems when $G$ is chordal and $n > (\omega+1)f$, where $\omega$ is the clique number of $G$. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.

• Brief announcement: Does preprocessing help under congestion?
  Klaus-Tycho Foerster, Janne H. Korhonen, Joel Rybicki and Stefan Schmid • PODC 2019
  
  • Publisher's version
  • arXiv preprint

  38th ACM Symposium on Principles of Distributed Computing (2019) • doi:10.1145/3293611.3331581

  ---

  Abstract

  This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does preprocessing help in the CONGEST model.

• Near-optimal self-stabilising counting and firing squads
  Christoph Lenzen and Joel Rybicki • Distributed Computing 2019
  
  • Publisher's version
  • arXiv preprint
  • Conference version

  Distributed Computing, volume 32, pages 339--360 (2019) • doi:10.1007/s00446-018-0342-6

  ---

  Abstract

  Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous $C$-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo $C$ in each round for given $C>1$. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience $f \lt n/3$, asymptotically optimal stabilisation and response time $O(f)$, and message size $O(\log f)$. As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions.

2018

• Model of bacterial toxin-dependent pathogenesis explains infective dose
  Joel Rybicki, Eva Kisdi and Jani V. Anttila • Proceedings of the National Academy of Sciences 2018
  
  • Publisher's version

  Proceedings of the National Academy of Sciences, (2018) • doi:10.1073/pnas.1721061115

  ---

  Abstract

  The initial amount of pathogens required to start an infection within a susceptible host is called the infective dose and is known to vary to a large extent between different pathogen species. We investigate the hypothesis that the differences in infective doses are explained by the mode of action in the underlying mechanism of pathogenesis: Pathogens with locally acting mechanisms tend to have smaller infective doses than pathogens with distantly acting mechanisms. While empirical evidence tends to support the hypothesis, a formal theoretical explanation has been lacking. We give simple analytical models to gain insight into this phenomenon and also investigate a stochastic, spatially explicit, mechanistic within-host model for toxin-dependent bacterial infections. The model shows that pathogens secreting locally acting toxins have smaller infective doses than pathogens secreting diffusive toxins, as hypothesized. While local pathogenetic mechanisms require smaller infective doses, pathogens with distantly acting toxins tend to spread faster and may cause more damage to the host. The proposed model can serve as a basis for the spatially explicit analysis of various virulence factors also in the context of other problems in infection dynamics.

2017

• Large cuts with local algorithms on triangle-free graphs
  Juho Hirvonen, Joel Rybicki, Stefan Schmid and Jukka Suomela • Electronic Journal of Combinatorics 2017
  
  • Publisher's version
  • arXiv preprint

  Electronic Journal of Combinatorics, volume 24, number 4, paper #P4.21 (2017)

  ---

  Abstract

  We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/\sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/\sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$.

• Efficient counting with optimal resilience
  Christoph Lenzen, Joel Rybicki and Jukka Suomela • SIAM Journal on Computing 2017
  
  • Publisher's version
  • arXiv preprint
  • Conference version

  SIAM Journal on Computing, volume 46, number 4, pages 1473--1500 (2017) • doi:10.1137/16M107877X

  ---

  Abstract

  Consider a complete communication network of $n$ nodes, where the nodes receive a common clock pulse. We study the synchronous $c$-counting problem: given any starting state and up to $f$ faulty nodes with arbitrary behavior, the task is to eventually have all correct nodes labeling the pulses with increasing values modulo $c$ in agreement. Thus, we are considering algorithms that are self-stabilizing despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have optimal resilience, (3) have a linear stabilization time in $f$ (asymptotically optimal), (4) use a small number of states, and, consequently, (5) communicate a small number of bits per round. Prior algorithms either resort to randomization, use a large number of states and need high communication bandwidth, or have suboptimal resilience. In particular, we achieve an exponential improvement in both state complexity and message size for deterministic algorithms. Moreover, we present two complementary approaches for reducing the number of bits communicated during and after stabilization.

• Deterministic subgraph detection in broadcast CONGEST
  Janne H. Korhonen and Joel Rybicki • OPODIS 2017
  
  • Publisher's version
  • arXiv preprint
  • Janne's OPODIS slides

  21st International Conference on Principles of Distributed Systems (2017) • doi:10.4230/LIPIcs.OPODIS.2017.4

  ---

  Abstract

  We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation:

  • For any constant $k$, detecting $k$-paths and trees on $k$ nodes can be done in $O(1)$ rounds.
  • For any constant $k$, detecting $k$-cycles and pseudotrees on $k$ nodes can be done in $O(n)$ rounds.
  • On $d$-degenerate graphs, cliques and $4$-cycles can be enumerated in $O(d + \log n)$ rounds, and $5$-cycles in $O(d^2 + \log n)$ rounds.

  In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for $d$-degenerate graphs can be improved to optimal complexity $O(d/\log n)$ and $O(d^2/\log n)$, respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.

  Proceedings

  Proceedings the 21st International Conference on Principles of Distributed Systems 18-20 December 2017, Lisboa, Portugal, pages 4:1--4:16, 2017

• Self-stabilising pulse synchronisation is almost as easy as consensus
  Christoph Lenzen and Joel Rybicki • DISC 2017
  
  • Publisher's version
  • arXiv preprint

  31st International Symposium on Distributed Computing (2017) • doi:10.4230/LIPIcs.DISC.2017.32

  ---

  Abstract

  We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to $f \lt n/3$ ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner. Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem:

  • In the deterministic setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $\Theta(f \log f)$ bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to $\Theta(\log f)$ while retaining the same stabilisation time.
  • In the randomised setting, the state-of-the-art solutions stabilise in time $\Theta(f)$ and have each node broadcast $O(1)$ bits per time unit. We exponentially reduce the stabilisation time to polylog $f$ while each node broadcasts polylog $f$ bits per time unit.

  These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.

• LCL problems on grids
  Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela and Przemysław Uznański • PODC 2017
  
  • Publisher's version
  • arXiv preprint

  ACM Symposium on Principles of Distributed Computing (2017) • doi:10.1145/3087801.3087833

  ---

  Abstract

  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 cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $\Theta(\log^* n)$, or $\Theta(n)$, and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $\Theta(\log^* n)$, and $\Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $\Theta(\log^* n)$ or $\Theta(n)$ in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is $\Theta(\log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A' \circ S_k$, where $A'$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.

  Proceedings

  Proceedings of the ACM Symposium on Principles of Distributed Computing - PODC '17, pages 101--110, 2017

2016

• Deterministic local algorithms, unique identifiers, and fractional graph colouring
  Henning Hasemann, Juho Hirvonen, Joel Rybicki and Jukka Suomela • Theoretical Computer Science 2016
  
  • Publisher's version

  Theoretical Computer Science, volume 610, pages 204--217 (2016) • doi:10.1016/j.tcs.2014.06.044

  ---

  Abstract

  We show that for any $\alpha > 1$ there exists a deterministic distributed algorithm that finds a fractional graph colouring of length at most $\alpha (\Delta + 1)$ in any graph in one synchronous communication round; here $\Delta$ is the maximum degree of the graph. The result is near-tight, as there are graphs in which the optimal solution has length $\Delta+1$. The result is, of course, too good to be true. The usual definitions of scheduling problems (fractional graph colouring, fractional domatic partition, etc.) in a distributed setting leave a loophole that can be exploited in the design of distributed algorithms: the size of the local output is not bounded. Our algorithm produces an output that seems to be perfectly good by the usual standards but it is impractical, as the schedule of each node consists of a very large number of short periods of activity. More generally, the algorithm shows that when we study distributed algorithms for scheduling problems, we can choose virtually any trade-off between the following three parameters: $T$, the running time of the algorithm, $\ell$, the length of the schedule, and $\kappa$, the maximum number of periods of activity for a any single node. Here $\ell$ is the objective function of the optimisation problem, while $\kappa$ captures the “subjective” quality of the solution. If we study, for example, bounded-degree graphs, we can trivially keep $T$ and $\kappa$ constant, at the cost of a large $\ell$, or we can keep $\kappa$ and $\ell$ constant, at the cost of a large $T$. Our algorithm shows that yet another trade-off is possible: we can keep $T$ and $\ell$ constant at the cost of a large $\kappa$.

• Synchronous counting and computational algorithm design
  Danny Dolev, Keijo Heljanko, Matti Järvisalo, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, Jukka Suomela and Siert Wieringa • Journal of Computer and System Sciences 2016
  
  • Publisher's version
  • arXiv preprint
  • Conference version

  Journal of Computer and System Sciences, volume 82, number 2, pages 310--332 (2016) • doi:10.1016/j.jcss.2015.09.002

  ---

  Abstract

  Consider a complete communication network on $n$ nodes. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree on which pulses are "odd" and which are "even". Furthermore, the solution needs to be self-stabilising (reaching correct operation from any initial state) and tolerate $f$ Byzantine failures (nodes that send arbitrary misinformation). Prior algorithms either require a source of random bits or a large number of states per node. In this work, we give fast state-optimal deterministic algorithms for the first non-trivial case $f=1$. To obtain these algorithms, we develop and evaluate two different techniques for algorithm synthesis. Both are based on casting the synthesis problem as a propositional satisfiability (SAT) problem; a direct encoding is efficient for synthesising time-optimal algorithms, while an approach based on counter-example guided abstraction refinement discovers non-optimal algorithms quickly.

• Near-optimal self-stabilising counting and firing squads
  Christoph Lenzen and Joel Rybicki • SSS 2016
  
  • Publisher's version
  • arXiv preprint

  18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (2016) • doi:10.1007/978-3-319-49259-9_21

  ---

  Abstract

  Consider a fully-connected synchronous distributed system of $n$ nodes, where up to $f$ nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous counting problem, all nodes need to eventually agree on a counter that is increased by one modulo some $C$ in each round. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external 'go' signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a 'fire' signal. Moreover, no node should generate a 'fire' signal without some correct node having previously received a ``go'' signal as input. We present a framework reducing both tasks to binary consensus at very small cost: we maintain the resilience of the underlying consensus routine, while the stabilisation time and message size are, up to constant factors, bounded by the sum of the cost of the consensus routine for $f$ faults and recursively applying our scheme to $f' \lt f/2$ faults. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience $f \lt n/3$, asymptotically optimal stabilisation and response time $O(f)$, and message size $O(\log f)$. As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions, and it is straightforward to adapt our framework to allow for $f \lt n/2$ omission or $f \lt n$ crash faults. Our results resolve various open questions on the two problems, most prominently whether (communication-efficient) self-stabilising Byzantine firing squads or sublinear-time solutions for either problem exist.

  Proceedings

  Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016), volume 10083 of Lecture Notes in Computer Science, pages 263--280, 2016

• A lower bound for the distributed Lovász local lemma
  Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela and Jara Uitto • STOC 2016
  
  • Publisher's version
  • arXiv preprint

  48th Annual ACM SIGACT Symposium on Theory of Computing (2016) • doi:10.1145/2897518.2897570

  ---

  Abstract

  We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires $\Omega(\log \log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of $d = O(1)$, where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of $O(\log n)$ rounds in bounded-degree graphs, and the best lower bound before our work was $\Omega(\log^* n)$ rounds [Chung et al. 2014].

  Proceedings

  Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016, pages 479--488, 2016

2015

• Large-scale habitat corridors for biodiversity conservation: A forest corridor in Madagascar
  Tanjona Ramiadantsoa, Otso Ovaskainen, Joel Rybicki and Ilkka Hanski • PLOS ONE 2015
  
  • Publisher's version

  PLOS ONE, volume 10, number 7, paper e0132126 (2015) • doi:10.1371/journal.pone.0132126

  ---

  Abstract

  In biodiversity conservation, habitat corridors are assumed to increase landscape-level connectivity and to enhance the viability of otherwise isolated populations. While the role of corridors is supported by empirical evidence, studies have typically been conducted at small spatial scales. Here, we assess the quality and the functionality of a large 95-km long forest corridor connecting two large national parks (416 and 311 km²) in the southeastern escarpment of Madagascar. We analyze the occurrence of 300 species in 5 taxonomic groups in the parks and in the corridor, and combine high-resolution forest cover data with a simulation model to examine various scenarios of corridor destruction. At present, the corridor contains essentially the same communities as the national parks, reflecting its breadth which on average matches that of the parks. In the simulation model, we consider three types of dispersers: passive dispersers, which settle randomly around the source population; active dispersers, which settle only in favorable habitat; and gap-avoiding active dispersers, which avoid dispersing across non-habitat. Our results suggest that long-distance passive dispersers are most sensitive to ongoing degradation of the corridor, because increasing numbers of propagules are lost outside the forest habitat. For a wide range of dispersal parameters, the national parks are large enough to sustain stable populations until the corridor becomes severely broken, which will happen around 2065 if the current rate of forest loss continues. A significant decrease in gene flow along the corridor is expected after 2040, and this will exacerbate the adverse consequences of isolation. Our results demonstrate that simulation studies assessing the role of habitat corridors should pay close attention to the mode of dispersal and the effects of regional stochasticity.

• Efficient counting with optimal resilience
  Christoph Lenzen and Joel Rybicki • DISC 2015
  
  • Publisher's version
  • arXiv preprint
  • Journal version
  • DISC slides

  29th International Symposium on Distributed Computing (DISC 2015) (2015) • doi:10.1007/978-3-662-48653-5_2

  ---

  Abstract

  In the synchronous $c$-counting problem, we are given a synchronous system of $n$ nodes, where up to $f$ of the nodes may be Byzantine, that is, have arbitrary faulty behaviour. The task is to have all of the correct nodes count modulo $c$ in unison in a self-stabilising manner: regardless of the initial state of the system and the faulty nodes’ behavior, eventually rounds are consistently labelled by a counter modulo c at all correct nodes. We provide a deterministic solution with resilience $f \lt n/3$ that stabilises in $O(f)$ rounds and every correct node broadcasts $O(\log^2 f)$ bits per round. We build and improve on a recent result offering stabilisation time $O(f)$ and communication complexity $O(\log^2 f/ \log \log f)$ but with sub-optimal resilience $f=n^{1−o(1)}$ (PODC 2015). Our new algorithm has optimal resilience, asymptotically optimal stabilisation time, and low communication complexity. Finally, we modify the algorithm to guarantee that after stabilisation very little communication occurs. In particular, for optimal resilience and polynomial counter size $c=n^{O(1)}$, the algorithm broadcasts only $O(1)$ bits per node every $\Theta(n)$ rounds without affecting the other properties of the algorithm; communication-wise this is asymptotically optimal.

  Proceedings

  Proceedings of the 29th International Symposium on Distributed Computing (DISC 2015), Tokyo, Japan, October 7--13, 2015, volume 9363 of Lecture Notes in Computer Science, pages 16--30, 2015

• Exact bounds for distributed graph colouring
  Joel Rybicki and Jukka Suomela • SIROCCO 2015
  
  • Publisher's version
  • arXiv preprint
  • SIROCCO slides

  22nd International Colloquium on Structural Information and Communication Complexity (2015) • doi:10.1007/978-3-319-25258-2_4

  ---

  Abstract

  We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with n colours, by prior work it is known that we can find a proper 3-colouring in $\log^*(n) \pm O(1)$ communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many n the time complexity is precisely $\log^* n$ communication rounds.

  Proceedings

  Structural Information and Communication Complexity: Post-proceedings of the 22nd International Colloquium (SIROCCO 2015), volume 9439 of Lecture Notes in Computer Science, pages 46--60, 2015

• Towards optimal synchronous counting
  Christoph Lenzen, Joel Rybicki and Jukka Suomela • PODC 2015
  
  • Publisher's version
  • arXiv preprint
  • Journal version
  • PODC slides

  34th ACM Symposium on Principles of Distributed Computing (2015) • doi:10.1145/2767386.2767423

  ---

  Abstract

  Consider a complete communication network of n nodes, in which the nodes receive a common clock pulse. We study the synchronous c-counting problem: given any starting state and up to f faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes count modulo c in agreement. Thus, we are considering algorithms that are self-stabilising despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have linear stabilisation time in f, (3) use a small number of states, and (4) achieve almost-optimal resilience. Prior algorithms either resort to randomisation, use a large number of states, or have poor resilience. In particular, we achieve an exponential improvement in the state complexity of deterministic algorithms, while still achieving linear stabilisation time and almost-linear resilience.

  Proceedings

  Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC 2015), pages 441--450, 2015

2013

• Species-area relationships and extinctions caused by habitat loss and fragmentation
  Joel Rybicki and Ilkka Hanski • Ecology Letters 2013
  
  • Publisher's version

  Ecology Letters, volume 16, number S1, pages 27--38 (2013) • doi:10.1111/ele.12065

  ---

  Abstract

  The species–area relationship (SAR) has been used to predict the numbers of species going extinct due to habitat loss, but other researchers have maintained that SARs overestimate extinctions and instead one should use the endemics–area relationship (EAR) to predict extinctions. Here, we employ spatially explicit simulations of large numbers of species in spatially heterogeneous landscapes to investigate SARs and extinctions in a dynamic context. The EAR gives the number of species going extinct immediately after habitat loss, but typically many other species have unviable populations in the remaining habitat and go extinct soon afterwards. We conclude that the EAR underestimates extinctions due to habitat loss, the continental SAR (with slope ~0.1 or somewhat less) gives a good approximation of short-term extinctions, while the island SAR calculated for discrete fragments of habitat (with slope ~0.25) predicts the long-term extinctions. However, when the remaining area of land-covering habitat such as forest is roughly less than 20% of the total landscape and the habitat is highly fragmented, all current SARs underestimate extinction rate. We show how the ‘fragmentation effect’ can be incorporated into a predictive SAR model. When the remaining habitat is highly fragmented, an effective way to combat the fragmentation effect is to aggregate habitat fragments into clusters rather than to place them randomly across the landscape.

  ---

  Additional material

  • Updated Supplementary information
  • Example implementation of the habitat generation algorithm
• Species-fragmented area relationship
  Ilkka Hanski, Gustavo A. Zurita, M. Isabel Bellocq and Joel Rybicki • Proceedings of the National Academy of Sciences 2013
  
  • Publisher's version

  Proceedings of the National Academy of Sciences, volume 110, number 31, pages 12715--12720 (2013) • doi:10.1073/pnas.1311491110

  ---

  Abstract

  The species-area relationship (SAR) gives a quantitative description of the increasing number of species in a community with increasing area of habitat. In conservation, SARs have been used to predict the number of extinctions when the area of habitat is reduced. Such predictions are most needed for landscapes rather than for individual habitat fragments, but SAR-based predictions of extinctions for landscapes with highly fragmented habitat are likely to be biased because SAR assumes contiguous habitat. In reality, habitat loss is typically accompanied by habitat fragmentation. To quantify the effect of fragmentation in addition to the effect of habitat loss on the number of species, we extend the power-law SAR to the species-fragmented area relationship. This model unites the single-species metapopulation theory with the multispecies SAR for communities. We demonstrate with a realistic simulation model and with empirical data for forest-inhabiting subtropical birds that the species-fragmented area relationship gives a far superior prediction than SAR of the number of species in fragmented landscapes. The results demonstrate that for communities of species that are not well adapted to live in fragmented landscapes, the conventional SAR underestimates the number of extinctions for landscapes in which little habitat remains and it is highly fragmented.

• Synchronous counting and computational algorithm design
  Danny Dolev, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki and Jukka Suomela • SSS 2013
  
  • Publisher's version
  • arXiv preprint
  • Journal version
  • SSS slides

  15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (2013) • doi:10.1007/978-3-319-03089-0_17

  ---

  Abstract

  Consider a complete communication network on n nodes, each of which is a state machine with s states. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree on which pulses are 'odd' and which are 'even'. We require that the solution is self-stabilising (reaching the correct operation from any initial state) and it tolerates f Byzantine failures (nodes that send arbitrary misinformation). Prior algorithms are expensive to implement in hardware: they require a source of random bits or a large number of states $s$. We use computational techniques to construct very compact deterministic algorithms for the first non-trivial case of $f = 1$. While no algorithm exists for $n \lt 4$, we show that as few as 3 states are sufficient for all values $n \ge 4$. We prove that the problem cannot be solved with only 2 states for $n = 4$, but there is a 2-state solution for all values $n \ge 6$.

  Proceedings

  Proceedings of the 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013), volume 8255 of Lecture Notes in Computer Science, pages 237--250, 2013

2012

• Deterministic local algorithms, unique identifiers, and fractional graph colouring
  Henning Hasemann, Juho Hirvonen, Joel Rybicki and Jukka Suomela • SIROCCO 2012
  
  • Publisher's version
  • Journal version

  19th International Colloquium on Structural Information and Communication Complexity (2012) • doi:10.1007/978-3-642-31104-8_5

  ---

  Abstract

  We show that for any $\alpha > 1$ there exists a deterministic distributed algorithm that finds a fractional graph colouring of length at most $\alpha (\Delta + 1)$ in any graph in one synchronous communication round; here $\Delta$ is the maximum degree of the graph. The result is near-tight, as there are graphs in which the optimal solution has length $\Delta+1$. The result is, of course, too good to be true. The usual definitions of scheduling problems (fractional graph colouring, fractional domatic partition, etc.) in a distributed setting leave a loophole that can be exploited in the design of distributed algorithms: the size of the local output is not bounded. Our algorithm produces an output that seems to be perfectly good by the usual standards but it is impractical, as the schedule of each node consists of a very large number of short periods of activity. More generally, the algorithm shows that when we study distributed algorithms for scheduling problems, we can choose virtually any trade-off between the following three parameters: $T$, the running time of the algorithm, $\ell$, the length of the schedule, and $\kappa$, the maximum number of periods of activity for a any single node. Here $\ell$ is the objective function of the optimisation problem, while $\kappa$ captures the “subjective” quality of the solution. If we study, for example, bounded-degree graphs, we can trivially keep $T$ and $\kappa$ constant, at the cost of a large $\ell$, or we can keep $\kappa$ and $\ell$ constant, at the cost of a large $T$. Our algorithm shows that yet another trade-off is possible: we can keep $T$ and $\ell$ constant at the cost of a large $\kappa$.

  Proceedings

  Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), volume 7355 of Lecture Notes in Computer Science, pages 48--60, 2012

2009

• A local 2-approximation algorithm for the vertex cover problem
  Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela and Jara Uitto • DISC 2009
  
  • Publisher's version

  23rd International Symposium on Distributed Computing (2009) • doi:10.1007/978-3-642-04355-0_21

  ---

  Abstract

  We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in $(\Delta+1)^2$ synchronous communication rounds, where $\Delta$ is the maximum degree of the graph. For $\Delta=3$, we give a 2-approximation algorithm also for the weighted version of the problem.

  Proceedings

  Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009), volume 5805 of Lecture Notes in Computer Science, pages 191--205, 2009

Manuscripts

• Reaching agreement in competitive microbial systems
  Victoria Andaur, Janna Burman, Matthias Függer, Manish Kushwaha, Bilal Manssouri, Thomas Nowak and Joel Rybicki • Manuscript.
  
  • arXiv preprint

  Manuscript (2021)

  ---

  Abstract

  In this work, we consider distributed agreement tasks in microbial distributed systems under stochastic population dynamics and competitive interactions. We examine how competitive exclusion can be used to solve distributed agreement tasks in the microbial setting. To this end, we develop a new technique for analyzing the time to reach competitive exclusion in systems with two competing species under biologically realistic population dynamics. We use this technique to analyze a protocol that exploits competitive interactions to solve approximate majority consensus efficiently in microbial systems. To corroborate our analytical results, we use computer simulations to show that these consensus dynamics occur within practical time scales.

• Local algorithms in (weakly) coloured graphs
  Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela and Jara Uitto • Manuscript.
  
  • arXiv preprint

  Manuscript (2010)

  ---

  Abstract

  A local algorithm is a distributed algorithm that completes after a constant number of synchronous communication rounds. We present local approximation algorithms for the minimum dominating set problem and the maximum matching problem in 2-coloured and weakly 2-coloured graphs. In a weakly 2-coloured graph, both problems admit a local algorithm with the approximation factor $(\Delta+1)/2$, where $\Delta$ is the maximum degree of the graph. We also give a matching lower bound proving that there is no local algorithm with a better approximation factor for either of these problems. Furthermore, we show that the stronger assumption of a 2-colouring does not help in the case of the dominating set problem, but there is a local approximation scheme for the maximum matching problem in 2-coloured graphs.