Is Consensus Really Universal?

Title: Is Consensus Really Universal?

Research Question: Can we determine if consensus, a fundamental concept in distributed computing, is truly universal?

Methodology: The researchers analyzed the assumptions underlying Herlihy's universality result for consensus. They focused on the concept of naming, which assumes that each process has a unique identifier known to all. They proposed probabilistic protocols for systems with asynchronous processes communicating via a shared memory, even in the presence of crash failures. They used a strong adversary model, assuming that the adversary decides which process moves next based on the entire past history of the protocol execution.

Results: The researchers found that naming is a necessary assumption for Herlihy's universality result. They also discovered that naming with randomization is universal, meaning that any other data structure can be implemented in a wait-free manner. This is a counterintuitive result, as it challenges the common belief that consensus is necessary for universality.

Implications: The findings suggest that the universality of consensus may not be as absolute as previously thought. The researchers' results provide a more nuanced understanding of the relationship between consensus and the implementation of other data structures in distributed computing systems. This could lead to more efficient and resilient protocols in the future.

Link to Article: https://arxiv.org/abs/0201006v1 Authors: arXiv ID: 0201006v1