Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Randomized Solutions to Renaming under Crashes and Byzantine Faults
Speaker:Oksana Denysyuk
coming from:INESC-ID and University of Lisbon
Speakers Bio:
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.
Event Type:SWS Colloquium
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Expert Audience
Date, Time and Location
Date:Monday, 17 November 2014
Duration:60 Minutes
Building:E1 5

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.
Name(s):Brigitta Hansen
Phone:0681 93039102
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:YesTo Location:Kaiserslautern
To Building:G26To Room:112
Meeting ID:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Brigitta Hansen, 11/13/2014 02:03 PM -- Created document.