34 citations · 50 across the 20 of their papers we have counts for
25 papers
Efficient Stable Population Protocols for Parity and Beyond
Leszek Gąsieniec, Tytus Grodzicki, Tomasz Jurdziński +2
For nearly two decades, population protocols have been extensively studied, yielding efficient solutions for central problems in distributed computing, including leader election, a…
Improving Efficiency in Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols
Leszek Gąsieniec, Tytus Grodzicki, Grzegorz Stachowiak
We investigate leader election problem via ranking within self-stabilising population protocols. In this scenario, the agent's state space comprises rank states and extra s…
Simple approximation algorithms for Polyamorous Scheduling
Yuriy Biktairov, Leszek Gąsieniec, Wanchote Po Jiamjitrak +3
In Polyamorous Scheduling, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time betwee…
Polyamorous Scheduling
Leszek Gąsieniec, Benjamin Smith, Sebastian Wild
Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationship…
Selective Population Protocols
Adam Gańczorz, Leszek Gąsieniec, Tomasz Jurdziński +2
The model of population protocols provides a universal platform to study distributed processes driven by pairwise interactions of anonymous agents. While population protocols prese…
Perpetual maintenance of machines with different urgency requirements
Leszek Gąsieniec, Tomasz Jurdziński, Ralf Klasing +4
A garden is populated by bamboos with the respective daily growth rates . It is assumed that the initial heights of…
New Clocks, Optimal Line Formation and Self-Replication Population Protocols
Leszek Gasieniec, Paul Spirakis, Grzegorz Stachowiak
In this paper we consider a variant of population protocols in which agents are allowed to be connected by edges, known as the constructors model. During an interaction between two…
A time and space optimal stable population protocol solving exact majority
David Doty, Mahsa Eftekhari, Leszek Gąsieniec +3
We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange info…
Efficient Assignment of Identities in Anonymous Populations
Leszek Gasieniec, Jesper Jansson, Christos Levcopoulos +1
We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the s…
Information Gathering in Ad-Hoc Radio Networks
Marek Chrobak, Kevin Costello, Leszek Gasieniec
In the ad-hoc radio network model, nodes communicate with their neighbors via radio signals, without knowing the topology of the graph. We study the information gathering problem,…
Patrolling on Dynamic Ring Networks
Shantanu Das, Giuseppe Antonio Di Luna, Leszek A. Gasieniec
We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in ev…
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…
Deterministic Computations on a PRAM with Static Processor and Memory Faults
Bogdan S. Chlebus, Leszek Gasieniec, Andrzej Pelc
We consider Parallel Random Access Machine (PRAM) which has some processors and memory cells faulty. The faults considered are static, i.e., once the machine starts to operate, the…
Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits
Huda Chuangpishit, Jurek Czyzowicz, Leszek Gasieniec +3
Patrolling consists of scheduling perpetual movements of a collection of mobile robots, so that each point of the environment is regularly revisited by any robot in the collection.…
Colored Point-set Embeddings of Acyclic Graphs
Emilio Di Giacomo, Leszek Gasieniec, Giuseppe Liotta +1
We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require edges each having $Ω(n^\fra…
Fast Space Optimal Leader Election in Population Protocols
Leszek Gasieniec, Grzegorz Stachowiak
The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistin…
Temporal flows in Temporal networks
Eleni C. Akrida, Jurek Czyzowicz, Leszek Gasieniec +2
We introduce temporal flows on temporal networks, i.e., networks the links of which exist only at certain moments of time. Such networks are ephemeral in the sense that no link exi…
Efficiently Correcting Matrix Products
Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas +2
We study the problem of efficiently correcting an erroneous product of two matrices over a ring. Among other things, we provide a randomized algorithm for correcting a…
Deterministic Symmetry Breaking in Ring Networks
Leszek Gasieniec, Tomasz Jurdzinski, Russell Martin +1
We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronised rounds. At the beginning of each round an age…
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski +3
In this work we focus on a natural class of population protocols whose dynamics are modelled by the discrete version of Lotka-Volterra equations. In such protocols, when an agent $…
The complexity of optimal design of temporally connected graphs
Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios +1
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of vertices, where each edge has an associated se…
Doing-it-All with Bounded Work and Communication
Bogdan S. Chlebus, Leszek Gąsieniec, Dariusz R. Kowalski +1
We consider the Do-All problem, where cooperating processors need to complete similar and independent tasks in an adversarial setting. Here we deal with a synchronous messa…
Information Gathering in Ad-Hoc Radio Networks with Tree Topology
Marek Chrobak, Kevin Costello, Leszek Gasieniec +1
We study the problem of information gathering in ad-hoc radio networks without collision detection, focussing on the case when the network forms a tree, with edges directed towards…
The Beachcombers' Problem: Walking and Searching with Mobile Robots
Jurek Czyzowicz, Leszek Gasieniec, Konstantinos Georgiou +2
We introduce and study a new problem concerning the exploration of a geometric domain by mobile robots. Consider a line segment and a set of mobile robots $r_1,r_2,...,…