Is Consensus Really Universal?

Title: Is Consensus Really Universal?

Research Question: Can we implement any data structure in a fault-tolerant manner using consensus and shared memory?

Methodology: The researchers studied the problem of consensus, where a set of asynchronous processes communicate via a shared memory. They considered two basic assumptions: naming (the existence of distinct IDs known to all) and randomization (the availability of unbiased random bits).

Results: The researchers found that naming is a hidden, but necessary, assumption of Herlihy's universality result for consensus. They also showed that naming is harder than consensus and brought to light some important differences between popular shared memory models.

Implications: This research has implications for the distributed computing community. It clarifies the assumptions needed for consensus to be universally applicable and highlights the complexity of naming in such systems. It also provides insights into the differences between popular shared memory models.

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