More Like this

1. Simplex Consensus: A Simple and Fast Consensus Protocol

   Benjamin Y. Chan and Rafael Pass (November 2023, TCC'23)
2. Consensus‐based sampling

   https://doi.org/10.1111/sapm.12470  

   Carrillo, J. A.; Hoffmann, F.; Stuart, A. M.; Vaes, U. (April 2022, Studies in Applied Mathematics)
3. Kemeny Consensus Complexity

   https://doi.org/10.24963/ijcai.2021/28  

   Fitzsimmons, Zack; Hemaspaandra, Edith (August 2021, Thirtieth International Joint Conference on Artificial Intelligence (IJCAI))

   null (Ed.)

   The computational study of election problems generally focuses on questions related to the winner or set of winners of an election. But social preference functions such as Kemeny rule output a full ranking of the candidates (a consensus). We study the complexity of consensus-related questions, with a particular focus on Kemeny and its qualitative version Slater. The simplest of these questions is the problem of determining whether a ranking is a consensus, and we show that this problem is coNP-complete. We also study the natural question of the complexity of manipulative actions that have a specific consensus as a goal. Though determining whether a ranking is a Kemeny consensus is hard, the optimal action for manipulators is to simply vote their desired consensus. We provide evidence that this simplicity is caused by the combination of election system (Kemeny), manipulative action (manipulation), and manipulative goal (consensus). In the process we provide the first completeness results at the second level of the polynomial hierarchy for electoral manipulation and for optimal solution recognition. 

   more » « less
4. Consensus Subspace Clustering

   https://doi.org/10.1109/ICTAI52525.2021.00064  

   Thom, Nathan; Nguyen, Hung; Hand, Emily M. (November 2021, IEEE International Conference on Tools with Artificial Intelligence)

   One significant challenge in the field of supervised deep learning is the lack of large-scale labeled datasets for many problems. In this paper, we propose Consensus Spectral Clustering (CSC), which leverages the strengths of convolutional autoencoders and spectral clustering to provide pseudo labels for image data. This data can be used as weakly-labeled data for training and evaluating classifiers which require supervision. The primary weaknesses of previous works lies in their inability to isolate the object of interest in an image and cluster similar images together. We address these issues by denoising input images to remove pixels which do not contain data pertinent to the target. Additionally, we introduce a voting method for label selection to improve the clustering results. Our extensive experimentation on several benchmark datasets demonstrates that the proposed CSC method achieves competitive performance with state-of-the-art methods. 

   more » « less
5. Safe Permissionless Consensus

   Pu, Youer (August 2024, Cornell University)

   Nakamoto’s consensus protocol, known for operating in a permissionless model where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This thesis shows that it is not with the Sandglass and Gorilla Sandglass protocols. Sandglass emerges as the first permissionless consensus algorithm that transcends Nakamoto’s probabilistic limitations by guaranteeing deterministic agreement and termination with probability 1, under general omission failures. It operates under a hybrid synchronous communication model, where, despite the unknown number and dynamic participation of nodes, a majority are consistently correct and synchronously connected. Further building on the framework of Sandglass, Gorilla Sandglass is the first Byzantine fault-tolerant consensus protocol that preserves deterministic agreement and termination with probability 1 within the same synchronous model adopted by Nakamoto. Gorilla addresses the limitations of Sandglass, which only tolerates benign failures, by extending its robustness to include Byzantine failures. We prove the correctness of Gorilla by mapping executions that would violate agreement or termination in Gorilla to executions in Sandglass, where we know such violations are impossible. Establishing termination proves particularly interesting, as the mapping requires reasoning about infinite executions and their probabilities 

   more » « less