Faculté informatique et communications IC, Section des systèmes de communication, Institut d'informatique fondamentale IIF (Laboratoire de programmation distribuée LPD)

Time-complexity bounds on agreement problems

Dutta, Partha ; Guerraoui, Rachid (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3261.

Add to personal list
    Summary
    In many distributed systems, designing an application that maintains consistency and availability despite failure of processes, involves solving some form of agreement. Not surprisingly, providing efficient agreement algorithms is critical for improving the performance of many distributed applications. This thesis studies how fast we can solve fundamental agreement problems like consensus, uniform consensus, and non-blocking atomic commit. In an agreement problem, the processes are supposed to propose a value and eventually decide on a common value that depends on the proposed values. To study agreement problems, we consider two round-based message-passing models, the wellknown synchronous model, and the eventually synchronous model. The second model is a partially synchronous model that remains asynchronous for an arbitrary number of rounds but eventually becomes synchronous. We investigate two aspects of the performance of agreement algorithms. We first measure time-complexity using a finer-grained metric than what was considered so far in the literature. Then we optimize algorithms for subsets of executions that are considered to be common in practice. Traditionally, the performance of agreement algorithms was measured in terms of global decision: the number of rounds required for all correct (non-faulty) processes to decide. However, in many settings, upon deciding, any correct process can provide the decision value to the process that is waiting for a decision. In this case, a more suitable performance metric is a local decision: the number of rounds required for at least one correct process to decide. We present tight bounds for local decisions in the synchronous and the eventually synchronous models. We also show that considering the local decision metric allows us to uncover fundamental differences between agreement problems, and between models, that were not apparent with previous metrics. In the eventually synchronous model, we observe that, for many cases in practice, executions are frequently synchronous and only occasionally asynchronous. Thus we optimize algorithms for synchronous executions, and give matching lower bounds. We show that, in some sense, synchronous executions of algorithms designed for the eventually synchronous model are slower than executions of algorithms directly designed for the synchronous model, i.e., there is an inherent price associated with tolerating arbitrary periods of asynchrony. Finally, we establish a tight bound on the number of rounds required to reach agreement once an execution becomes synchronous and no new failures occur.
    Résumé
    Dans les systèmes répartis, la conception d'une application consistante et disponible malgré des erreurs de processus nécessite un protocole d'accord. Comme on peut s'y attendre, il est difficile de fournir des algorithmes d'accord efficaces. Cette thèse étudie la complexité des problèmes d'accord fondamentaux comme le consensus, le consensus uniforme, et la validation atomique non-bloquante. Dans un problème d'accord, les processus sont supposés proposer une valeur et ensuite décider d'une valeur commune qui sera déterminée en fonction des valeurs proposées. Pour étudier les problèmes d'accord, nous considérons deux modèles de communication basés sur des rondes: le modèle synchrone bien connu, et le modèle finalement synchrone. Le second modèle est un modèle partiellement synchrone, qui reste asynchrone pour un nombre arbitraire de rondes, pour finalement devenir synchrone. Nous étudions deux aspects de la performance d'algorithmes d'accord. D'abord, nous mesurons la complexité en temps avec une métrique plus fine que celle utilisée jusqu'à présent dans la littérature. Puis nous optimisons les algorithmes pour les sous-ensembles d'exécutions considérés comme les plus fréquentes dans la pratique. Traditionnellement, la performance d'algorithmes d'accord est mesurée en termes de décision globale: le nombre de rondes requis pour que tous les processus corrects (sans défaillance) décident. Cependant, dans bien des contextes, n'importe quel processus correct peut fournir la valeur de décision au processus qui attend qu'une décision soit prise. Dans ce cas, une métrique de la performance mieux adaptée sera la décision locale: le nombre de rondes requis pour qu'au moins un processus correct puisse décider. Nous présentons des bornes exactes pour les décisions locales dans les modèles synchrone et finalement synchrone. Nous montrons également qu'en matière de décision locale, notre métrique nous permet de découvrir des différences fondamentales entre les problèmes d'accord, et entre les modèles eux-mêmes, différences qui n'apparaissaient pas avec les métriques précédentes. Dans le modèle finalement synchrone, nous observons que dans bien des cas, les exécutions sont en pratique souvent synchrones, et seulement occasionnellement asynchrones. Nous optimisons donc les algorithmes pour des exécutions synchrones, et donnons des bornes inférieures adaptées. Nous montrons que d'une certaine façon, les exécutions synchrones d'algorithmes conçus pour le modèle finalement synchrone sont plus lentes que les exécutions d'algorithmes conçus directement pour le modèle synchrone; cela signifie que la tolérance aux périodes asynchrones a un prix. Finalement, nous établissons une borne inférieure exacte sur le nombre de rondes requis pour chaque accord une fois qu'une exécution devient synchrone et qu'aucune nouvelle erreur n'apparaît.