Author name cluster

Joel Rybicki

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

TCS Journal 2023 Journal Article

Wait-free approximate agreement on graphs

Dan Alistarh
Faith Ellen
Joel Rybicki

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.

Details DOI

STOC Conference 2016 Conference Paper

A lower bound for the distributed Lovász local lemma

Sebastian Brandt 0002
Orr Fischer
Juho Hirvonen
Barbara Keller
Tuomo Lempiäinen
Joel Rybicki
Jukka Suomela
Jara Uitto

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].

Details

TCS Journal 2016 Journal Article

Deterministic local algorithms, unique identifiers, and fractional graph colouring

Henning Hasemann
Juho Hirvonen
Joel Rybicki
Jukka Suomela

In the fractional graph colouring problem, the task is to schedule the activities of the nodes so that each node is active for 1 time unit in total, and at each point of time the set of active nodes forms an independent set. We show that for any α > 1 there exists a deterministic distributed algorithm that finds a fractional graph colouring of length at most α ( Δ + 1 ) in any graph in one synchronous communication round; here Δ is the maximum degree of the graph. The result is near-tight, as there are graphs in which the optimal solution has length Δ + 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 demonstrates 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, ℓ, the length of the schedule, and κ, the maximum number of periods of activity for any single node. Here ℓ is the objective function of the optimisation problem, while κ captures the “subjective” quality of the solution. If we study, for example, bounded-degree graphs, we can trivially keep T and κ constant, at the cost of a large ℓ, or we can keep κ and ℓ constant, at the cost of a large T. Our algorithm shows that yet another trade-off is possible: we can keep T and ℓ constant at the cost of a large κ.

Details DOI