15 citations · 31 across the 11 of their papers we have counts for
14 papers
Distributed Stochastic Graph Algorithms
Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis
We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph of a known base graph is realize…
DejaVu: A Minimalistic Mechanism for Distributed Plurality Consensus
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +2
We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of opinions, aims to agree on the init…
On the -majority dynamics with many opinions
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +1
We present the first upper bound on the convergence time to consensus of the well-known -majority dynamics with opinions, in the synchronous setting, for and that ar…
Self-Stabilizing MIS Computation in the Beeping Model
George Giakkoupis, Volker Turau, Isabella Ziccardi
We consider self-stabilizing algorithms to compute a Maximal Independent Set (MIS) in the extremely weak beeping communication model. The model consists of an anonymous network wit…
Naively Sorting Evolving Data is Optimal and Robust
George Giakkoupis, Marcos Kiwi, Dimitrios Los
We study sorting in the evolving data model, introduced by [AKMU11], where the true total order changes while the sorting algorithm is processing the input. More precisely, each co…
Distributed Self-Stabilizing MIS with Few States and Weak Communication
George Giakkoupis, Isabella Ziccardi
We study a simple random process that computes a maximal independent set (MIS) on a general -vertex graph. Each vertex has a binary state, black or white, where black indicates…
Cluster-and-Conquer: When Randomness Meets Graph Locality
George Giakkoupis, Anne-Marie Kermarrec, Olivier Ruas +1
K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and l…
How to Spread a Rumor: Call Your Neighbors or Take a Walk?
George Giakkoupis, Frederik Mallmann-Trenn, Hayk Saribekyan
We study the problem of randomized information dissemination in networks. We compare the now standard PUSH-PULL protocol, with agent-based alternatives where information is dissemi…
Search via Parallel Lévy Walks on
Andrea Clementi, Francesco d'Amore, George Giakkoupis +1
Motivated by the Lévy foraging hypothesis -- the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency -- we study the parallel…
Efficient Randomized Test-And-Set Implementations
George Giakkoupis, Philipp Woelfel
We study randomized test-and-set (TAS) implementations from registers in the asynchronous shared memory model with n processes. We introduce the problem of group election, a natura…
Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs
George Giakkoupis
We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by Lieberman et al.\ (Nature, 2005). In this process, individu…
Deterministic and Fast Randomized Test-and-Set in Optimal Space
George Giakkoupis, Maryam Helmi, Lisa Higham +1
The test-and-set object is a fundamental synchronization primitive for shared memory systems. A test-and-set object stores a bit, initialized to 0, and supports one operation, test…
Bounds on the Voter Model in Dynamic Networks
Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec +1
In the voter model, each node of a graph has an opinion, and in every round each node chooses independently a random neighbour and adopts its opinion. We are interested in the cons…
Tight Bounds for Rumor Spreading with Vertex Expansion
George Giakkoupis
We establish a bound for the classic PUSH-PULL rumor spreading protocol on arbitrary graphs, in terms of the vertex expansion of the graph. We show that O(log^2(n)/α) rounds suffic…