000086004 001__ 86004 000086004 005__ 20190619003124.0 000086004 0247_ $$2doi$$a10.5075/epfl-thesis-3587 000086004 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis3587-1 000086004 02471 $$2nebis$$a5175442 000086004 037__ $$aTHESIS 000086004 041__ $$aeng 000086004 088__ $$a3587 000086004 245__ $$aTransformations in distributed computations and applications to set agreement 000086004 269__ $$a2006 000086004 260__ $$bEPFL$$c2006$$aLausanne 000086004 300__ $$a133 000086004 336__ $$aTheses 000086004 502__ $$aEliezer Gafni, Kathryn Hess Bellwald, Maurice Herlihy 000086004 520__ $$aIn a distributed application, high-availability of a critical online service is ensured despite failures by duplicating the vital components of the server. Whilst guaranteeing the access to the server at all times, duplication requires particular care, so as to maintain a consistent state amongst all components. A distributed computation plays a key-role in preserving the consistency of the state in this case. Indeed, one of the fundamental forms of distributed computation is distributed agreement. In a distributed agreement problem, the components of the system, called processes, are supposed to all propose a value and eventually decide on a common value that depends on the proposed values. Designing correct distributed agreement algorithms relies on a mathematical model abstracting the details of the underlying physical model. In practice, there are many models, inspired from various types of physical failures. Coping with one type of failures rather than another one, for a distributed agreement algorithm, is not of equal difficulty. Indeed some types are intrinsically harder to cope with than other ones. The thesis studies how distributed algorithms can be transformed from one model to another one. The idea is to design distributed agreement algorithms in models in which the task is made as easiest and least error-prone as possible, and execute the transformed algorithms in models imposed by the underlying physical constraints. We investigate another aspect of transforming distributed computations, the notion of reducibility amongst distributed computations. Reducibility offers an elegant way for deducing lower or upper bounds on the complexity of a distributed algorithm from complexity bounds that have been proved elsewhere, about a different distributed computation or in a different model. For investigating reducibility, the thesis considers two very general classes of models: synchronous models, in which the communication delay and the process execution speed are known and bounded, and asynchronous models, in which the communication delay and the process execution speed are unknown and potentially unbounded. The thesis investigates reducibility of a distributed agreement problem called set agreement. Precisely, we consider the early-deciding variant of set agreement, in which processes must decide as fast as they can in any execution. We prove a lower bound on the complexity of early-deciding set agreement in the synchronous model. The proof works by reducing the impossibility of set agreement in the asynchronous model to the desired lower bound. In some cases, complexity bounds must still be derived with ad-hoc arguments, for example when there is no apparent connection with existing results. The thesis presents an alternative approach to reducibility, namely the connection of distributed computing with algebraic topology. Within this framework, we derive a lower bound for the complexity of early-deciding set agreement in the synchronous model. For all the lower bounds that we derive in the thesis, we show that these bounds are tight, by presenting for each lower bound an algorithm matching the complexity of the lower bound. 000086004 6531_ $$aDistributed algorithms 000086004 6531_ $$aModels of computations 000086004 6531_ $$aTransformations 000086004 6531_ $$aReducibility 000086004 6531_ $$aSet agreement 000086004 6531_ $$aAlgebraic topology 000086004 6531_ $$aAlgorithmique répartie 000086004 6531_ $$aModèles de calcul 000086004 6531_ $$aTransformations entre modèles 000086004 6531_ $$aRéductibilité 000086004 6531_ $$aAccord d'ensemble 000086004 6531_ $$aTopologie algébrique 000086004 700__ $$0(EPFLAUTH)111497$$g111497$$aPochon, Bastian 000086004 720_2 $$aGuerraoui, Rachid$$edir.$$g105326$$0240335 000086004 8564_ $$uhttps://infoscience.epfl.ch/record/86004/files/EPFL_TH3587.pdf$$zTexte intégral / Full text$$s960284$$yTexte intégral / Full text 000086004 909C0 $$xU10407$$0252114$$pDCL 000086004 909CO $$pthesis-public$$pDOI$$pIC$$ooai:infoscience.tind.io:86004$$qDOI2$$qGLOBAL_SET$$pthesis$$pthesis-bn2018 000086004 918__ $$bIC-SSC$$cIIF$$aIC 000086004 919__ $$aLPD 000086004 920__ $$b2006$$a2006-8-25 000086004 970__ $$a3587/THESES 000086004 973__ $$sPUBLISHED$$aEPFL 000086004 980__ $$aTHESIS