14 citations · 50 across the 20 of their papers we have counts for
23 papers · 1 filter
Randomized Tree-Intersection Leader Election
Yuval Emek, Shay Kutten, Ido Rafael +1
We present a randomized leader election algorithm for synchronous complete -node graphs in the \textsf{CONGEST} model that introduces a highly tunable trade-off between time com…
Team Formation and Applications
Yuval Emek, Shay Kutten, Ido Rafael +1
A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the…
Beeping Deterministic CONGEST Algorithms in Graphs
Pawel Garncarek, Dariusz R. Kowalski, Shay Kutten +1
The Beeping Network (BN) model captures important properties of biological processes. Paradoxically, the extremely limited communication capabilities of such nodes has helped BN be…
Tight Bounds on the Message Complexity of Distributed Tree Verification
Shay Kutten, Peter Robinson, Ming Ming Tan
We consider the message complexity of verifying whether a given subgraph of the communication network forms a tree with specific properties both in the KT- (nodes know their …
Improved Tradeoffs for Leader Election
Shay Kutten, Peter Robinson, Ming Ming Tan +1
We consider leader election in clique networks, where nodes are connected by point-to-point communication links. For the synchronous clique under simultaneous wake-up, i.e., wh…
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
Fabien Dufoulon, Shay Kutten, William K. Moses +2
A singularly (near) optimal distributed algorithm is one that is (near) optimal in \emph{two} criteria, namely, its time and message complexities. For \emph{synchronous} CONGEST ne…