Kenan Wood∗ kewood@davidson.edu Davidson CollegeDistributed Agreement • October 29th, 2024
Preference aggregation is a fundamental problem in voting theory, in which public input rankings of a set of alternatives (called preferences) must be aggregated into a single preference that satisfies certain soundness properties. The celebrated Arrow Impossibility Theorem is equivalent to a distributed task in a synchronous fault-free system that satisfies properties such as respecting unanimous preferences, maintaining independence of irrelevant alternatives (IIA), and non-dictatorship, along with consensus since only one preference can be decided.
Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic NetworksDistributed Agreement • September 10th, 2018
Abstract. We study distributed agreement in synchronous directed dynamic networks, where an omniscient message adversary controls the presence/absence of communication links. We prove that consensus is impossible under a message adversary that guarantees weak connectivity only, and in- troduce vertex-stable root components (VSRCs) as a means for circumventing this impossibility: A VSRC(k, d) message adversary guarantees that, eventually, there is an interval of d consecutive rounds where every communication graph contains at most k strongly connected components con- sisting of the same processes (with possibly varying interconnect topology), which have at most out-going links to the remaining processes. We present a consensus algorithm that works correctly under a VSRC(1, 4H + 2) message adversary, where H is the dynamic causal network diameter. Our algorithm maintains local estimates of the communication graphs, and applies techniques for detecting network stability and univalent syst
Distributed Agreement in Tile Self-AssemblyDistributed Agreement • May 26th, 2009
Abstract. Laboratory investigations have shown that a formal theory of fault-tolerance will be essen- tial to harness nanoscale self-assembly as a medium of computation. Several researchers have voiced an intuition that self-assembly phenomena are related to the field of distributed computing. This paper formalizes some of that intuition. We construct tile assembly systems that are able to simulate the solution of the wait-free consensus problem in some distributed systems. (For potential future work, this may allow binding errors in tile assembly to be analyzed, and managed, with positive results in distributed computing, as a “blockage” in our tile assembly model is analogous to a crash failure in a distributed computing model.) We also define a strengthening of the “traditional” consensus problem, to make explicit an expectation about consensus algorithms that is often implicit in distributed com- puting literature. We show that solution of this strengthened consensus problem can be
Distributed Agreement and Its Relation with Error-Correcting CodessDistributed Agreement • September 3rd, 2002
Distributed Agreement in Tile Self-AssemblyDistributed Agreement • February 19th, 2009
Abstract. Laboratory investigations have shown that a formal theory of fault-tolerance will be essen- tial to harness nanoscale self-assembly as a medium of computation. Several researchers have voiced an intuition that self-assembly phenomena are related to the field of distributed computing. This paper formalizes some of that intuition. We construct tile assembly systems that are able to simulate the so- lution of the wait-free consensus problem in some distributed systems. This potentially allows binding errors in tile assembly to be analyzed (and managed) with positive results in distributed computing, as a “blockage” in our tile assembly model is analogous to a crash failure in a distributed computing model. We also define a strengthening of the “traditional” consensus problem, to make explicit an expectation about consensus algorithms that is often implicit in distributed computing literature. We show that solution of this strengthened consensus problem can be simulated by a two-
