5 papers
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…
The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective
Matthias Bentert, Shay Kutten, Darya Melnyk +2
The theoretical model behind the pigeon post as a link layer in a communication network was introduced by Shannon (under the guise of studying One-Time Pads for cryptography). That…
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 $Ï…
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…