Distributed Computing [[electronic resource] ] : 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings / / edited by Yoram Moses

• Pubblicazione: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
• Edizione: 1st ed. 2015.
• Descrizione fisica: 1 online resource (XXI, 678 p. 83 illus.)
• Disciplina: 004.36
• Soggetto topico: Computer networks; Data structures (Computer science); Information theory; Software engineering; Application software; Computer Communication Networks; Data Structures and Information Theory; Software Engineering; Computer and Information Systems Applications
• Persona (resp. second.): MosesYoram
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Intro -- Preface -- Organization -- Awards and Keynote Lecture -- The 2015 Edsger W. Dijkstra Prizein Distributed Computing -- The 2015 Doctoral Dissertation Awardin Distributed Computing -- DISC 2015 Invited Lecture:System Algorithms for the Cloud and Big Data -- Contents -- On the Computational Complexity of MapReduce -- 1 Introduction -- 2 Background and Previous Work -- 2.1 MapReduce -- 2.2 Complexity -- 3 Models -- 3.1 MapReduce and MRC -- 3.2 Nonuniformity -- 3.3 Other Models of Parallel Computation -- 4 Space Complexity Classes in MRC0 -- 5 Hierarchy Theorems -- 6 Discussion and Open Problems -- References -- Efficient Counting with Optimal Resilience -- 1 Introduction -- 1.1 Contributions -- 1.2 Prior Work -- 1.3 Structure of the Article -- 2 Preliminaries -- 3 Optimal Resilience Boosting -- 3.1 The Road Map -- 3.2 Agreeing on a Common Counter (Once in a While) -- 3.3 Reaching Consensus -- 3.4 Proofs of Theorems 1 and 2 -- 4 Less Communication After Stabilisation -- 5 Discussion -- References -- The Computational Power of Beeps -- 1 Introduction -- 2 Model -- 3 Leader Election -- 3.1 Leader Election Lower Bound -- 3.2 The Universal Leader Election Algorithm -- 3.3 Optimal Leader Election -- 3.4 Fast Leader Election with Sub-Optimal State -- 3.5 Fast Leader Election with O(1) States and High Probability -- 4 Solving General Distributed Decision Problems -- References -- Byzantine Fireflies -- 1 Introduction -- 2 Model and Problem -- 3 Lower Bound -- 4 Known Beeping Period -- 4.1 Algorithm (Known Period Synchronous Beeping - KPSB) -- 4.2 Informal Description -- 4.3 Correctness Proof -- 5 Unknown Beeping Period -- 5.1 Preliminaries -- 5.2 Algorithm (Unknown Period Synchronous Beeping - UPSB) -- 5.3 Informal Description -- 5.4 Correctness Proof -- 6 Average Beeping Period -- 6.1 Lower Bound -- 6.2 Preliminaries. ; 6.3 Algorithm (Average Period Synchronous Beeping - APSB) -- 6.4 Informal Description -- 6.5 Correctness Proof -- 7 Synchronous Lighting -- 7.1 Problem -- 7.2 Algorithm (Average Period Synchronous Lighting - APSL) -- 7.3 Correctness Proof -- 8 Conclusion -- References -- Wait-Freedom is Harder Than Lock-Freedom Under Strong Linearizability -- 1 Introduction -- 2 Preliminaries -- 3 Impossibilities -- 3.1 Group Valency and Super Valency -- 3.2 Impossibility Proof -- 4 Lock-Free Implementations -- 5 Discussion -- References -- Simulating a Shared Register in an Asynchronous System that Never Stops Changing -- 1 Introduction -- 2 Model -- 3 The CCReg Algorithm -- 4 Correctness Proof -- 5 Discussion -- References -- Plane Formation by Synchronous Mobile Robots in the Three Dimensional Euclidean Space -- 1 Introduction -- 2 Robot Model -- 3 Symmetry in 3D-Space -- 4 Proof of Theorem 1 -- 4.1 Necessity -- 4.2 Sufficiency -- 5 Conclusion -- References -- Anonymous Graph Exploration with Binoculars -- 1 Introduction -- 2 Exploration with Binoculars -- 2.1 The Model -- 2.2 The Exploration Problem -- 2.3 Our Results -- 3 Definitions and Notations -- 3.1 Graphs -- 3.2 Simplicial Complexes -- 4 First Impossibility Result and Lower Bound -- 5 Exploration of FC -- 5.1 Presentation of the Algorithm -- 5.2 Correction of the Algorithm -- 6 Complexity of the Exploration Problem -- 7 Conclusion -- Limit Behavior of the Multi-agent Rotor-Router System -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Results -- 2 Model and Preliminaries -- 3 Periodicity of the Rotor-Router System -- 4 Stabilization Time of the Rotor-Router System -- 5 Simulation of the Rotor-Router -- 6 Conclusion -- References -- Elastic Configuration Maintenance via a Parsimonious Speculating Snapshot Solution -- 1 Introduction -- 1.1 Related Work -- 2 Problem Model -- 3 SpSn Read-Write Solution. ; 4 SpSn Message-Passing Solution -- 5 Dynamic Reconfiguration Using SpSn -- 6 Application: Read-Write Store -- 7 Conclusions -- References -- SmartMerge: A New Approach to Reconfiguration for Atomic Storage -- 1 Introduction -- 2 System Model -- 3 Problem: Atomic Storage Using Smart Merge -- 4 Algorithm: Atomic Storage Using Smart Merge -- 5 Related Work -- 6 Conclusion -- References -- Towards Automatic Lock Removal for Scalable Synchronization -- 1 Introduction -- 2 Transformation -- 2.1 Lock-Based Data Structures -- 2.2 Combining Optimism and Pessimism -- 2.3 Transforming the Code Phases -- 3 Evaluation -- 4 Related Work -- 5 Discussion -- References -- Inherent Limitations of Hybrid Transactional Memory -- 1 Introduction -- 2 Preliminaries -- 3 Hybrid Transactional Memory (HyTM) -- 4 HyTM Instrumentation -- 5 Linear Instrumentation Lower Bound -- 6 Instrumentation-Optimal HyTM Algorithms -- 7 Related Work -- 8 Concluding Remarks -- References -- Why Non-blocking Operations Should be Selfish -- 1 Introduction -- 2 Preliminaries -- 3 Equivalence of Amortised Measures of Contention -- 4 Evaluation of the Selfish Linked List -- 4.1 The Selfish Linked List Algorithm -- 4.2 Experimental Evaluation -- 5 Towards a More Refined Notion of Contention -- 6 Related Work -- 7 Conclusion -- References -- Hybrid Transactional Memory Revisited -- 1 Introduction -- 2 The Hybrid Cohorts Approach -- 3 Implementation -- 4 Evaluation -- 4.1 Microbenchmark Performance -- 4.2 STAMP Performance -- 4.3 Memcached Performance -- 5 Conclusions and Future Work -- References -- Grasping the Gap Between Blocking and Non-Blocking Transactional Memories -- 1 Introduction -- 2 TM Model and Properties -- 3 Lower Bounds for Obstruction-Free TMs -- 3.1 Impossibility of Invisible Reads -- 3.2 Stall Complexity -- 3.3 RAW/AWAR Complexity -- 4 Upper Bound for Opaque Progressive TMs. ; 5 Related Work -- 6 Concluding Remarks -- References -- Fast Consensus for Voting on General Expander Graphs -- 1 Introduction -- 1.1 Background on Distributed Pull Voting -- 1.2 Main Results -- 2 Expected Change in Weight after One Step of Voting -- 3 Proof of Theorem 1 -- 4 Specific Examples and Notes on Eigenvalue Gaps -- References -- Randomness vs. Time in Anonymous Networks -- 1 Introduction -- 1.1 Related Work -- 2 Preliminaries -- 3 Tailor-Made 2-Hop Coloring -- 4 Trade-off Lower Bound -- Fast Byzantine Leader Election in Dynamic Networks -- 1 Introduction -- 1.1 Computing Model and Problem Definition -- 2 The Byzantine Leader Election Algorithm -- 2.1 Preliminaries and Technical Tools -- 2.2 A Byzantine Leader Election Algorithm -- 3 Conclusion -- Local Information in Influence Networks -- 1 Introduction -- 1.1 Related Work -- 2 Model and Definition -- 2.1 Influence Network Model -- 2.2 k-Hop Influence Network and Local Decision Algorithm -- 3 Hierarchy of Algorithms -- 4 Algorithms -- 4.1 Preliminaries -- 4.2 Byzantine-Safe Algorithm -- 4.3 Rational-Safe Algorithms -- 4.4 Protocol-Safe Algorithms -- 4.5 Possible-Safe Algorithms -- 4.6 Putting Everything Together -- 5 Conclusion -- References -- Amalgamated Lock-Elision -- 1 Introduction -- 2 Amalgamated Lock-Elision -- 2.1 Algorithm Overview -- 2.2 Algorithm Details -- 3 Performance Evaluation -- 3.1 Micro-benchmarks -- 3.2 Various Red-Black Tree Sizes -- 3.3 KyotoCabinet -- 4 Conclusion -- References -- Transactional Interference-Less Balanced Tree -- 1 Introduction -- 2 Background -- 3 Reducing the Interference of Structural Operations -- 4 TxCF-Tree -- 4.1 Structural Operations -- 4.2 Semantic Operations -- 5 Correctness -- 6 Evaluation -- 7 Conclusions -- References -- Analyzing the Performance of Lock-Free Data Structures: A Conflict-Based Model -- 1 Introduction -- 2 Related Work. ; 3 Problem Statement -- 3.1 Running Program and Targeted Platform -- 3.2 Examples and Issues -- 3.2.1 Immediate Upper Bounds -- 3.2.2 Conflicts -- 3.2.3 Process -- 4 Execution without Hardware Conflicts -- 4.1 Setting -- 4.1.1 Notations and Definitions -- 4.2 Cyclic Executions -- 4.3 Throughput Bounds -- 5 Expansion and Complete Throughput Estimation -- 5.1 Expansion -- 5.2 Throughput Estimate -- 6 Experimental Evaluation -- 6.1 Setting -- 6.2 Synthetic Tests -- 6.3 Treiber's Stack -- 6.4 Discussion -- 6.5 Back-Off Tuning -- 7 Conclusion -- References -- A Constructive Approach for Proving Data Structures' Linearizability -- 1 Introduction -- 2 Preliminaries -- 3 Base Point Analysis -- 4 Linearizability Using Base Point Analysis -- 4.1 Update Operations -- 4.2 Read-Only Operations -- 5 Roadmap for Proving Linearizability -- 5.1 Stage I: Base Conditions -- 5.2 Stage II: Linearizability of Update Operations -- 5.3 Stage III: Linearizability of Read-Only Operations -- 6 Discussion -- References -- Modular Verification of Concurrency-Aware Linearizability -- 1 Introduction -- 2 Motivating Examples -- 2.1 Exchanger -- 2.2 Elimination Stack -- 3 Concurrency-Aware Linearizability (CAL) -- 3.1 A Formal Definition of Concurrency-Aware Linearizability -- 4 Specifying Concurrency-Aware Concurrent Objects -- 5 Verifying the Exchanger and the Elimination Stack -- 5.1 Verifying the Exchanger -- 6 Related Work -- References -- Transaction Chopping for Parallel Snapshot Isolation -- 1 Introduction -- 2 Operational Specification of PSI -- 3 Axiomatic Specification of PSI -- 4 Equivalence of the Specifications -- 5 Chopping PSI Transactions -- 6 Related Work -- References -- Computing in Additive Networks with Bounded-Information Codes -- 1 Introduction -- 1.1 Contributions and Methods -- 1.2 Comparison with Related Work -- 2 Background: Additive Networks and BCC. ; 3 New Tools.
• Sommario/riassunto: This book constitutes the proceedings of the 29th International Symposium on Distributed Computing, DISC 2015, held in Tokyo, Japan, in October 2015. The 42 full papers and 14 short papers presented in this volume were carefully reviewed and selected from 143 submissions. The papers feature original contributions to theory, design, implementation, modeling, analysis, or application of distributed systems and networks.
• Titolo autorizzato: Distributed computing
• ISBN: 3-662-48653-9
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996466193103316
• Lo trovi qui: Univ. di Salerno
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 9363