CMI Library

Your cart is empty.
Normal view MARC view ISBD view

Impossibility Results for Distributed Computing Hagit Attiya, Faith Ellen.

By: Attiya, Hagit [author.].
Contributor(s): Ellen, Faith [author.].
Material type: TextTextSeries: v.12Synthesis lectures on distributed computing theory. Publisher: Switzerland. Springer Nature. c2022Description: xiii, 146 pages; E 34.99 23 cms.ISBN: 9783031008825 (pbk.).Subject(s): Electronic data processing. -- Distributed processing | Unsolvability (Mathematical logic)
Contents:
1. Introduction -- 1.1 Unsolvability results and lower bounds -- 1.2 Why study impossibility results? -- 1.3 Structure of the book --
a 2. Indistinguishability -- 2.1 A time tradeoff between read and write in the implementation of a register -- 2.2 A space lower bound for first-come first-served mutual exclusion -- 2.3 A lower bound on the step complexity of approximate agreement -- 2.4 Chain arguments for consensus -- 2.5 Causality arguments --
Summary: To understand the power of distributed systems, it is necessary to understand their inherent limitations: what problems cannot be solved in particular systems, or without sufficient resources (such as time or space). This book presents key techniques for proving such impossibility results and applies them to a variety of different problems in a variety of different system models. Insights gained from these results are highlighted, aspects of a problem that make it difficult are isolated, features of an architecture that make it inadequate for solving certain problems efficiently are identified, and different system models are compared.
List(s) this item appears in: 2023-12-25
Item type Current location Call number Status Date due Barcode Item holds
Book Chennai Mathematical Institute
General Stacks 		004.36 ATT (Browse shelf) Checked out 28/10/2024 11128
Total holds: 0

1. Introduction -- 1.1 Unsolvability results and lower bounds -- 1.2 Why study impossibility results? -- 1.3 Structure of the book --

a 2. Indistinguishability -- 2.1 A time tradeoff between read and write in the implementation of a register -- 2.2 A space lower bound for first-come first-served mutual exclusion -- 2.3 A lower bound on the step complexity of approximate agreement -- 2.4 Chain arguments for consensus -- 2.5 Causality arguments --

To understand the power of distributed systems, it is necessary to understand their inherent limitations: what problems cannot be solved in particular systems, or without sufficient resources (such as time or space). This book presents key techniques for proving such impossibility results and applies them to a variety of different problems in a variety of different system models. Insights gained from these results are highlighted, aspects of a problem that make it difficult are isolated, features of an architecture that make it inadequate for solving certain problems efficiently are identified, and different system models are compared.