We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Consensus Potpourri: Locally Solvable Tasks and the Limitations of Valency Arguments

Formale Metadaten

Titel
Consensus Potpourri: Locally Solvable Tasks and the Limitations of Valency Arguments
Serientitel
Anzahl der Teile
30
Autor
Lizenz
CC-Namensnennung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is *local* in nature, as at each stage, one configuration of an hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to *consensus*, leading one to wonder why it has not been used in impossibility results of the two other well-known tasks: *set agreement* and *renaming*. This paper provide an explanation why the proof strategies for showing the impossibility of these tasks have a global nature. We show that *a protocol can always solve such tasks locally*, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming.