Oksana Denysyuk
FaultTolerant Renaming in Synchronous MessagePassing Systems
Thesis submitted for the PhD in Computer Science and Engineering, Instituto Superior Técnico
(IST), Universidade de Lisboa
Abstract
Exploring the power and limitations of different coordination problems
has al ways been at the heart of the theory of distributed
computing. This thesis addresses the coordination problem called
renaming, in which processes start with ids from a large namespace and
output new names from a small namespace. 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 in a
constructive way, by picking distinct values (names) from an
appropriate range of values.
We focus on synchronous
messagepassing systems, where n processes are arranged in a fully
connected network and communicate by sending messages. We show that,
with resort to randomization, renaming can be solved in O(log log n)
rounds with high probability, if up to t < n may fail by crashing (t
is an upper bound on the number of faults). In contrast, deterministic
algorithms require Omega(log n) rounds. Thus, our result implies
that randomized renaming algorithms can outperform deterministic
algorithms by an exponential factor. When considering Byzantine
faults, we show that randomized algorithms can solve renaming in O(log
n) rounds with high probability, while tolerating up to t < n
Byzantine faults (in contrast, deterministic algorithms require
unbounded time). These results imply that randomization is a
powerful and necessary technique in solving renaming.
Finally, this thesis is the first to address orderpreserving renaming
in the context of Byzantine faults. In orderpreserving renaming,
processes must output new names in the order of their original ids. We
show that renaming can be solved in O(log n) rounds, if up to t < n/3
processes may be Byzantine. We also show that orderpreserving
renaming can be solved in O(1) rounds if the maximum number of
Byzantine faults is bounded by t < n^2 +2t. On the negative side, we
show that orderpreserving renaming cannot be solved if t >= n/3; the
impossibility applies to both deterministic and randomized
algorithms. This result establishes a separation between the
resiliency of renaming and order preserving renaming algorithms in
the Byzantine fault model.
Selected Publications
 FaultTolerant Renaming in Synchronous MessagePassing Systems
 Oksana Denysyuk
 PhD Thesis. Departamento de Engenharia Informática,
Instituto Superior Técnico (IST), Universidade
de Lisboa
 November, 2014.
 Available pdf.
 BallsintoLeaves: Sublogarithmic Renaming in
Synchronous MessagePassing Systems.
 D. Alistarh,
O. Denysyuk, L. Rodrigues and N. Shavit.
 In proceedings of the
33rd ACM Symposium on Principles of Distributed Computing (PODC),
Paris, France, July 2014.
 Byzantine Renaming in Synchronous Systems with t <
N.
 O. Denysyuk and L. Rodrigues.
 In proceedings of the 32nd ACM
Symposium on Principles of Distributed Computing (PODC), Montreal,
Canada, July 2013.

 Orderpreserving Renaming in Synchronous Systems
with Byzantine Faults.
 O. Denysyuk and
L. Rodrigues.
 Proceedings of the 33rd International Conference
on Distributed Computing Systems (ICDCS), Philadelphia, USA,
Juy 2013.

Luís Rodrigues