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