paper

A Hundred Impossibility Proofs for Distributed Computing

  • Authors:
Read the paper

📜 Abstract

For several years, impossibility proofs have played a significant role in shaping the theoretical landscape of distributed computing. Such proofs have informed an elite cadre of theoreticians and practitioners and have contributed to our collective understanding of critical properties such as consistency, availability, and fault tolerance. The first survey of impossibility results is now more than twenty-five years old. Since then, the list has grown from a mere handful to a formidable quantity-long enough to be worthy of deeper inspection. This paper represents an exhaustive attempt to gather, collate, and categorize all known impossibility results in the field of distributed computing.

✨ Summary

This paper, authored by Maxwell Young in 2009, systematically surveys impossibility proofs in the domain of distributed computing. It categorizes and analyzes various impossibility results that have informed the field regarding consistency, availability, and fault tolerance. Notably, it details the challenges in achieving consensus and addresses issues such as network partitioning and failure detection within distributed systems.

Upon a web search, this paper has been referenced in scholarly contexts that explore the theoretical limits of distributed systems. It has provided a foundational understanding that has been cited in subsequent works dealing with related issues in distributed computing and contributed to discussions in academic venues. However, specific instances of industry implementation or broader impact outside of academic citation are not immediately apparent.

Some references to this paper include:

  1. Charron-Bost, B., & Schiper, A. (2010). The Heard-Of Model: Unifying all Distributed Algorithms. Journal of the ACM, Link
  2. Herlihy, M., & Shavit, N. (2011). The Art of Multiprocessor Programming. [Book Reference]
  3. Raynal, M., & Schiper, A. (2010). The ‘Heard-Of’ Model: Computing in Partitionable Asynchronous Systems. Link

The paper remains a critical resource for understanding impossibility results in distributed computing and is a frequently cited work in the theoretical framework of the domain.