Central Library, Indian Institute of Technology Delhi
केंद्रीय पुस्तकालय, भारतीय प्रौद्योगिकी संस्थान दिल्ली

Impossibility results for distributed computing / Hagit Attiya, Faith Ellen.

By: Attiya, Hagit [author.]Contributor(s): Ellen, Faith [author.]Material type: TextTextSeries: Synthesis digital library of engineering and computer science | Synthesis lectures on distributed computing theory ; # 12.Publisher: San Rafael, California (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool, 2014Description: 1 PDF (xv, 146 pages) : illustrationsContent type: text Media type: electronic Carrier type: online resourceISBN: 9781627051712Subject(s): Electronic data processing -- Distributed processing | Unsolvability (Mathematical logic) | lower bounds | indistinguishability | shifting | scaling | scenario arguments | information theory arguments | covering | valency | reductions | simulations | implementations | consensus | set consensus | approximate agreement | clock synchronization | mutual exclusion | snapshots | timestampsAdditional physical formats: Print version:: No titleDDC classification: 004.36 LOC classification: QA76.9.D5 | A883 2014Online resources: Abstract with links to resource | Abstract with links to full text Also available in print.
Contents:
1. Introduction -- 1.1 Unsolvability results and lower bounds -- 1.2 Why study impossibility results? -- 1.3 Structure of the book --
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 --
3. Shifting and scaling -- 3.1 Shifting arguments -- 3.2 Time lower bounds for implementing a multi-writer register -- 3.3 Clock synchronization without drift -- 3.4 Scaling arguments -- 3.5 Clock synchronization with drift --
4. Scenario arguments -- 4.1 Impossibility of consensus with arbitrary process failures -- 4.2 Clock synchronization with arbitrary process failures --
5. Information theory arguments -- 5.1 Lower bounds using single-writer registers -- 5.2 The round complexity of OR -- 5.3 The round complexity of approximate agreement -- 5.4 Lower bounds using more powerful objects -- 5.5 The round complexity of collect -- 5.6 A step complexity tradeoff for synchronous snapshots --
6. Covering arguments -- 6.1 A space lower bound for mutual exclusion -- 6.2 The space complexity of timestamps -- 6.3 Space and step complexity lower bounds for the implementation of a counter using swap objects -- 6.4 A lower bound on step complexity for space-optimal implementations of a multi-writer snapshot -- 6.5 A lower bound on the number of stalls incurred by a counter implemented using arbitrary read-modify-write primitives --
7. Valency arguments -- 7.1 The unsolvability of consensus using m-assignment -- 7.2 The round complexity of consensus -- 7.3 The unsolvability of consensus in asynchronous message passing systems -- 7.4 The space complexity of consensus -- 7.4.1 Anonymous processes -- 7.4.2 The general case -- 7.5 A lower bound on expected work for randomized consensus -- 7.5.1 Chain arguments -- 7.5.2 Nullvalent executions -- 7.5.3 Bivalent executions -- 7.5.4 Putting the pieces together --
8. Combinatorial arguments -- 8.1 Unsolvability of set consensus -- 8.2 A lower bound on update time for a single-writer snapshot -- 8.3 A lower bound on the solo step complexity of weak test&set using Turan's Theorem -- 8.4 Anonymous conflict detectors -- 8.5 Yao's principle -- 8.6 Expected step complexity of randomized implementations of a max register.
9. Reductions and simulations -- 9.1 Simulations with different numbers of processes -- 9.2 The BG simulation -- 9.3 Round-by-round simulations -- 9.4 Uncomputability of consensus number --
Bibliography -- Authors' biographies.
Abstract: 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.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Call number Status Date due Barcode
Ebooks Ebooks Indian Institute of Technology Delhi - Central Library
Available

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Series from website.

Includes bibliographical references (pages 135-140) and index.

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

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 --

3. Shifting and scaling -- 3.1 Shifting arguments -- 3.2 Time lower bounds for implementing a multi-writer register -- 3.3 Clock synchronization without drift -- 3.4 Scaling arguments -- 3.5 Clock synchronization with drift --

4. Scenario arguments -- 4.1 Impossibility of consensus with arbitrary process failures -- 4.2 Clock synchronization with arbitrary process failures --

5. Information theory arguments -- 5.1 Lower bounds using single-writer registers -- 5.2 The round complexity of OR -- 5.3 The round complexity of approximate agreement -- 5.4 Lower bounds using more powerful objects -- 5.5 The round complexity of collect -- 5.6 A step complexity tradeoff for synchronous snapshots --

6. Covering arguments -- 6.1 A space lower bound for mutual exclusion -- 6.2 The space complexity of timestamps -- 6.3 Space and step complexity lower bounds for the implementation of a counter using swap objects -- 6.4 A lower bound on step complexity for space-optimal implementations of a multi-writer snapshot -- 6.5 A lower bound on the number of stalls incurred by a counter implemented using arbitrary read-modify-write primitives --

7. Valency arguments -- 7.1 The unsolvability of consensus using m-assignment -- 7.2 The round complexity of consensus -- 7.3 The unsolvability of consensus in asynchronous message passing systems -- 7.4 The space complexity of consensus -- 7.4.1 Anonymous processes -- 7.4.2 The general case -- 7.5 A lower bound on expected work for randomized consensus -- 7.5.1 Chain arguments -- 7.5.2 Nullvalent executions -- 7.5.3 Bivalent executions -- 7.5.4 Putting the pieces together --

8. Combinatorial arguments -- 8.1 Unsolvability of set consensus -- 8.2 A lower bound on update time for a single-writer snapshot -- 8.3 A lower bound on the solo step complexity of weak test&set using Turan's Theorem -- 8.4 Anonymous conflict detectors -- 8.5 Yao's principle -- 8.6 Expected step complexity of randomized implementations of a max register.

9. Reductions and simulations -- 9.1 Simulations with different numbers of processes -- 9.2 The BG simulation -- 9.3 Round-by-round simulations -- 9.4 Uncomputability of consensus number --

Bibliography -- Authors' biographies.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

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.

Also available in print.

Title from PDF title page (viewed on June 20, 2014).

There are no comments on this title.

to post a comment.
Copyright © 2022 Central Library, Indian Institute of Technology Delhi. All Rights Reserved.

Powered by Koha