MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

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.
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Expert Audience
English

Date, Time and Location

Monday, 17 November 2014
14:00
60 Minutes
E1 5
029
Saarbrücken

Abstract


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.

Contact

Brigitta Hansen
0681 93039102
--email hidden

Video Broadcast

Yes
Kaiserslautern
G26
112
passcode not visible
logged in users only

Brigitta Hansen, 11/13/2014 14:03 -- Created document.