| Description |
1 online resource (xxiii, 139 pages) : illustrations |
| Series |
Synthesis Lectures on Distributed Computing Theory |
|
Synthesis lectures on distributed computing theory.
|
| Contents |
Intro -- List of Figures -- List of Algorithms -- List of Tables -- Preface -- Acknowledgments -- Distributed Universality -- Introduction -- A Very Short Historical Perspective -- On the Nature of Distributed Computing -- Basic Asynchronous Read/Write Model CARW_n,t[] -- On Atomicity -- Concurrent Objects -- On Progress Conditions -- Universal Construction -- An LL/SC-Based Wait-Free Universal Construction -- Extending CARW_n,t[] with LL/SC -- A Simple Wait-Free Universal Construction in CARW_n,t[LL/SC] -- From Weak-LL/SC to LL/SC -- An MMswap-Based Wait-Free Universal Construction |
|
Extending CARW[] with MMswap -- A Wait-Free Universal Construction in CARW[MMswap] -- Comparing LL/SC and MMswap -- Extensions -- The Case of Large Objects -- On the Implementation Side: Disjoint-Access Parallelism -- On the Object Side: Abortable Objects -- From Operations on Memory Locations to Agreement Objects -- Primitive Operations vs. Objects -- A Fundamental Agreement Object: Consensus -- Implementing Wait-Free Consensus in Enriched CARW_n,t[] Models -- A Simple Wait-Free Consensus-Based Universal Construction -- Generalizing Universality -- Universal Construction ̀̀1 Among k'' |
|
Ultimate Universal Construction ̀̀ Among k'' -- Universal Construction vs. Software Transactional Memory -- Conclusion -- Consensus Numbers and Beyond -- Preliminaries -- The Consensus Hierarchy -- Two Agreement Objects -- The Consensus Hierarchy -- A Glance Inside the Consensus Number Land -- Life in the ̀̀Consensus Number 1'' Land -- The Family of ̀̀Write and Read Next'' Objects -- Computability Power of WRN_k in a k-Process System -- When There are More than k Processes -- Infinite Hierarchy Inside the ̀̀Consensus Number 1'' Land -- Life in Each ̀̀Consensus Number 2'' Land |
|
The Family of AEG_m,k Objects -- The Consensus Number of an AEG_m,k Object is m -- An Infinite Hierarchy Inside Each ̀̀Consensus Number m'' Land, m 2 -- Conclusion -- Distributed Recursivity -- Introduction -- Computation Model, Distributed Task, and Examples of Tasks -- Computation Model -- The Notion of a Distributed Task -- The Write-Snapshot Task -- The Adaptive Renaming Task -- A Pattern for Recursive Distributed Algorithms -- Linear Time Recursion -- A Recursive Write-Snapshot Algorithm -- Proof of the Algorithm -- Example of an Execution -- Branching Time Recursion |
|
A Recursive Renaming Algorithm -- Example of an Execution -- Conclusion -- The BG Simulation -- Introduction -- Distributed Task -- Notion of a Task -- Algorithm Solving a Task -- BG Simulation: Preliminaries -- Notation -- SWMR Snapshot-Based Communication -- Simulated Processes vs. Simulator Processes -- Base Object Used in Both Simulations: safe_agreement -- The safe_agreement Object Type -- An Algorithm Implementing the safe_agreement Type -- Proof of the Safe-Agreement Algorithm -- BG Simulation for Colorless Tasks -- The Memory MEM[1..(t+1)] Shared by the Simulators |
|
Algorithm Implementing the sim_write_i,j() Operation |
| Summary |
Theory is what remains true when technology is changing. So, it is important to know and master the basic concepts and the theoretical tools that underlie the design of the systems we are using today and the systems we will use tomorrow. This means that, given a computing model, we need to know what can be done and what cannot be done in that model. Considering systems built on top of an asynchronous read/write shared memory prone to process crashes, this monograph presents and develops the fundamental notions that are universal constructions, consensus numbers, distributed recursivity, power of the BG simulation, and what can be done when one has to cope with process anonymity and/or memory anonymity. Numerous distributed algorithms are presented, the aim of which is being to help the reader better understand the power and the subtleties of the notions that are presented. In addition, the reader can appreciate the simplicity and beauty of some of these algorithms |
| Bibliography |
Includes bibliographical references |
| Subject |
Electronic data processing -- Distributed processing.
|
|
Computer system failures.
|
|
Computer storage devices.
|
|
Computer storage devices
|
|
Computer system failures
|
|
Electronic data processing -- Distributed processing
|
| Form |
Electronic book
|
| ISBN |
9781636393308 |
|
1636393306 |
|
3031792130 |
|
9783031792137 |
|
