Randomized Solutions to Renaming under Crashes and Byzantine Faults
Oksana Denysyuk
INESC-ID and University of Lisbon
SWS Colloquium
Oksana Denysyuk received an M.S. and B.S. in Computer Science from the Instituto Superior Tecnico of the University of Lisbon in 2009 and 2007, respectively. She is currently a Ph.D. student in the same organization and expects to obtain her doctorate degree in November 2014. Her work was published at the PODC, DISC, and ICDCS conferences. Her research interests include theory of distributed computing, dynamic networks, fault tolerance, and randomized distributed algorithms.
Exploring the power and limitations of different coordination problems has always been at the heart of the theory of distributed computing. This talk addresses a coordination problem called renaming. Renaming can be seen as a dual to the classical consensus problem: instead of agreeing on a unique value, in renaming correct processes must disagree by picking distinct values from an appropriate range of values.
The talk consists of two parts, each considering a different fault model in synchronous message-passing systems. In the first part, we tackle crash faults and propose a new randomization technique, called balls-into-leaves, which solves renaming in sub-logarithmic number of rounds. This technique outperforms optimal deterministic algorithms by an exponential factor. In the second part, we consider the more challenging Byzantine faults. We propose a randomized renaming algorithm that tolerates up to t<n faults, where n is the number of processes. Our second solution has logarithmic round complexity; this is a significant improvement over previously known deterministic algorithms, which either required unbounded time or could tolerate only t<n/3 faults.