| In this thesis we investigate distinct techniques to avoid the impact of miscellaneous failures derived from hostile attacks in a message-passing distributed computing environment. Our failure palette assumes more benign faults as an appetizer and then moves on to more malign ones. To start with, we revisit the classical k-set agreement problem, where different distributed processors must all agree on up to k values previously proposed by them. We develop an optimal crash-resilient k-set agreement protocol, which tolerates the best possible number of crashes given (exact or close to) minimal synchrony features provided by limited-scope failure detectors in asynchronous systems. Tight bounds on the maximum number of crashes are achieved through combinatorial topology, and relation of failure detectors to timing assumptions, in settings such as stabilizing ones, is unfolded.;Finally, we show how to boost threshold protocols in adversarial structure models where failures may be dependent and processors may behave badly in an arbitrary, byzantine way. In particular, we look at the problem of running any protocol that has an upper bound of n > c t, for any positive integer constant c, where n is the total number of processors and t is the maximum number of faults. We introduce an optimal byzantine-resilient protocol that enables simulation with less than n processors of any such threshold protocol in adversarial structure models. We also define equivalence classes using a particular set of key hierarchy properties.;In the sequence, we broaden our failure repertoire to include message omissions performed by coprocessor hosts with high incentives to cheating. Here, coprocessors are tamper-proof and receive and send encrypted messages. This prevents arbitrary behavior of hosts, which may just omit incoming or outgoing messages or crash their own coprocessor. In this context, making use of secret shared coins, we derive randomized consensus (that is, 1-set agreement) protocols, optimal both in terms of time and resilience, and of very practical use for e-business. Deterministic versions and automatic transformations for failure detectors are also discussed. |
