LEADER 12418nam 22008055 450 001 996466193103316 005 20230223224422.0 010 $a3-662-48653-9 024 7 $a10.1007/978-3-662-48653-5 035 $a(CKB)4340000000001301 035 $a(SSID)ssj0001585051 035 $a(PQKBManifestationID)16262957 035 $a(PQKBTitleCode)TC0001585051 035 $a(PQKBWorkID)14865354 035 $a(PQKB)11059304 035 $a(DE-He213)978-3-662-48653-5 035 $a(MiAaPQ)EBC6281331 035 $a(MiAaPQ)EBC5594815 035 $a(Au-PeEL)EBL5594815 035 $a(OCoLC)932170923 035 $a(PPN)190529172 035 $a(EXLCZ)994340000000001301 100 $a20151003d2015 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aDistributed Computing$b[electronic resource] $e29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings /$fedited by Yoram Moses 205 $a1st ed. 2015. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2015. 215 $a1 online resource (XXI, 678 p. 83 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9363 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-662-48652-0 327 $aIntro -- 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. 327 $a6.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. 327 $a4 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. 327 $a5 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. 327 $a3 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. 327 $a3 New Tools. 330 $aThis 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. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9363 606 $aComputer networks 606 $aData structures (Computer science) 606 $aInformation theory 606 $aSoftware engineering 606 $aApplication software 606 $aComputer Communication Networks 606 $aData Structures and Information Theory 606 $aSoftware Engineering 606 $aComputer and Information Systems Applications 615 0$aComputer networks. 615 0$aData structures (Computer science). 615 0$aInformation theory. 615 0$aSoftware engineering. 615 0$aApplication software. 615 14$aComputer Communication Networks. 615 24$aData Structures and Information Theory. 615 24$aSoftware Engineering. 615 24$aComputer and Information Systems Applications. 676 $a004.36 702 $aMoses$b Yoram$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996466193103316 996 $aDistributed computing$9104445 997 $aUNISA