Fault-Tolerant Renaming in Synchronous Message-Passing Systems
Thesis submitted for the PhD in Computer Science and Engineering, Instituto Superior Técnico
(IST), Universidade de Lisboa
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
message-passing 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 order-preserving renaming
in the context of Byzantine faults. In order-preserving 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 order-preserving
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 order-preserving 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.
- Fault-Tolerant Renaming in Synchronous Message-Passing Systems
- Oksana Denysyuk
- PhD Thesis. Departamento de Engenharia Informática,
Instituto Superior Técnico (IST), Universidade
- November, 2014.
- Available pdf.
- Balls-into-Leaves: Sub-logarithmic Renaming in
Synchronous Message-Passing 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 <
- O. Denysyuk and L. Rodrigues.
- In proceedings of the 32nd ACM
Symposium on Principles of Distributed Computing (PODC), Montreal,
Canada, July 2013.
- Order-preserving Renaming in Synchronous Systems
with Byzantine Faults.
- O. Denysyuk and
- Proceedings of the 33rd International Conference
on Distributed Computing Systems (ICDCS), Philadelphia, USA,