Oksana Denysyuk

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

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 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.

Selected Publications

Fault-Tolerant Renaming in Synchronous Message-Passing Systems: Oksana Denysyuk; PhD Thesis. Departamento de Engenharia Informática, Instituto Superior Técnico (IST), Universidade de Lisboa; 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 < N.: 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 L. Rodrigues.; Proceedings of the 33rd International Conference on Distributed Computing Systems (ICDCS), Philadelphia, USA, Juy 2013.

Luís Rodrigues