TY - CONF
AB - 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(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
AU - Brandt, Sebastian
AU - Keller, Barbara
AU - Rybicki, Joel
AU - Suomela, Jukka
AU - Uitto, Jara
ID - 9678
SN - 9781450380706
T2 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
TI - Efficient load-balancing through distributed token dropping
ER -
TY - CONF
AB - 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 𝑛≥3 processes for this problem on any cycle of length 𝑐≥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 𝑐≥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 class of graphs that properly contains the class of chordal graphs.
AU - Alistarh, Dan-Adrian
AU - Ellen, Faith
AU - Rybicki, Joel
ID - 9823
SN - 03029743
T2 - Structural Information and Communication Complexity
TI - Wait-free approximate agreement on graphs
VL - 12810
ER -
TY - CONF
AB - 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 neighbors 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 polylog n pairwise interactions, with high probability, using at most 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 an example, this implies that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ 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.
AU - Alistarh, Dan-Adrian
AU - Gelashvili, Rati
AU - Rybicki, Joel
ID - 10218
SN - 1868-8969
T2 - 35th International Symposium on Distributed Computing
TI - Brief announcement: Fast graphical population protocols
VL - 209
ER -
TY - CONF
AB - We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(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 Ω(log n).
AU - Korhonen, Janne
AU - Paz, Ami
AU - Rybicki, Joel
AU - Schmid, Stefan
AU - Suomela, Jukka
ID - 10219
SN - 1868-8969
T2 - 35th International Symposium on Distributed Computing
TI - Brief announcement: Sinkless orientation is hard also in the supported LOCAL model
VL - 209
ER -
TY - JOUR
AB - 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. In contrast, 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 complex effects on 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.
AU - Rybicki, Joel
AU - Abrego, Nerea
AU - Ovaskainen, Otso
ID - 7224
IS - 3
JF - Ecology Letters
SN - 1461-023X
TI - Habitat fragmentation and species diversity in competitive communities
VL - 23
ER -
TY - CONF
AB - 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 xi and has to decide on an
output value yi such that
1. the output values are in the convex hull of the non-faulty processors’ input values,
2. 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 ≥ 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 ≥ 1,
we show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f,
where ω 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.
AU - Nowak, Thomas
AU - Rybicki, Joel
ID - 6931
KW - consensus
KW - approximate agreement
KW - Byzantine faults
KW - chordal graphs
KW - lattice agreement
T2 - 33rd International Symposium on Distributed Computing
TI - Byzantine approximate agreement on graphs
VL - 146
ER -
TY - CONF
AB - 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.
AU - Foerster, Klaus-Tycho
AU - Korhonen, Janne
AU - Rybicki, Joel
AU - Schmid, Stefan
ID - 6935
SN - 9781450362177
T2 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
TI - Does preprocessing help under congestion?
ER -
TY - JOUR
AB - 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.
AU - Ovaskainen, Otso
AU - Rybicki, Joel
AU - Abrego, Nerea
ID - 6936
IS - 11
JF - Ecography
SN - 0906-7590
TI - What can observational data reveal about metacommunity processes?
VL - 42
ER -
TY - JOUR
AB - We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of thennodes 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