1.7k citations · 1.9k across the 33 of their papers we have counts for
4 papers · 1 filter
A Combinatorial Characterization of Self-Stabilizing Population Protocols
Shaan Mathur, Rafail Ostrovsky
We fully characterize self-stabilizing functions in population protocols for complete interaction graphs. In particular, we investigate self-stabilization in systems of finite…
Population stability: regulating size in the presence of an adversary
Shafi Goldwasser, Rafail Ostrovsky, Alessandra Scafuro +1
We introduce a new coordination problem in distributed computing that we call the population stability problem. A system of agents each with limited memory and communication, as we…
Space-Time Tradeoffs for Distributed Verification
Rafail Ostrovsky, Mor Perry, Will Rosenbaum
Verifying that a network configuration satisfies a given boolean predicate is a fundamental problem in distributed computing. Many variations of this problem have been studied, for…
Deterministic and Energy-Optimal Wireless Synchronization
Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky
We consider the problem of clock synchronization in a wireless setting where processors must power-down their radios in order to save energy. Energy efficiency is a central goal in…