Principles of Distributed Systems: 17th International Conference, OPODIS 2013, Nice, France, December 16-18, 2013. Proceedings (Lecture Notes in Computer Science, 8304)

This book constitutes the refereed proceedings of the 17th International Conference on Principles of Distributed Systems, OPODIS 2013, held in Nice, France, in December 2013. The 19 papers presented together with two invited talks were carefully reviewed and selected from 41 submissions. The conference is an international forum for the exchange of state-of-the-art knowledge on distributed computing and systems. Papers were sought soliciting original research contributions to the theory, specification, design and implementation of distributed systems. Principles of Distributed Systems Preface 5 Organization 6 Table of Contents 11 Tutorial Summary: Paxos Explained from Scratch 13 1 Introduction 13 2 A Stateful Service: Assumptions and Notation 14 3 Fault Tolerance with Two Servers 15 4 Server Crashes 16 5 Network Partitions 17 6 Leader Change 18 7 Five Servers 20 8 Summary 21 On Two-Party Communication Through Dynamic Networks 23 1 Introduction 23 1.1 Our Contribution 24 1.2 Organization of the Paper 24 2 Models and Problems 25 3 Related Work 26 4 Relating Counting to Communication through a Dynamic Network 27 4.1 Special Dynamic Networks and the Same Predecessor Problem 28 4.2 Dynamic Channel Networks and the Set Equality Problem 29 4.3 Two-Party Communication and the Set Equality Problem 30 5 Conclusion and Future Prospects 33 Eventual Leader Election in Evolving Mobile Networks 35 1 Introduction 35 2 Related Work 36 3 Model for Eventual Leader Election in Mobile Systems 38 3.1 Communication Model 38 3.2 Process Model 39 3.3 Network Connectivity 40 3.4 The Class 40 4 An Eventual Leader Oracle for Mobile Systems 40 4.1 Stable Query-Response Communication Mechanism 40 4.2 Behavioral Property 41 4.3 An Eventual Leader Election Algorithm 42 5 Proof of Correctness 45 6 Conclusion 48 Self-stabilizing Leader Election in Population Protocols over Arbitrary Communication Graphs 50 1 Introduction 50 2 Model and Definitions 53 2.1 Population Protocol 53 2.2 Run, Behaviour, Oracle and Implementation 55 3 Specific Behaviours and Oracles 57 3.1 Eventual Leader Election Behaviour ELE 57 3.2 Oracles ?(k,d) 57 4 Impossibility of Leader Election under Local Fairness with Uniform Initialization 58 5 Leader Election under Global Fairness with Uniform Initialization 59 6 Self-stabilizing Leader Election Using ?(2,1) under Global Fairness 60 7 Impossibility of Self-stabilizing Implementation of ? Using ELE under Global Fairness 62 8 Discussion and Open Problems 63 $\alpha$-Register 65 1 Introduction 65 2 Computational Model and Definition of -Registers 67 3 Single-Writer Multiple-Reader -Register 69 3.1 Proof of the Protocol 73 4 Lower bound 77 5 Conclusion 78 How (Not) to Shoot in Your Footwith SDN Local Fast Failover 80 1 Introduction 80 2 You Must Shoot in Your Foot! 82 3 How Not to Shoot in Your Foot! 85 3.1 Randomized Failover 86 3.2 Deterministic Failover 88 4 Beyond Worst-Case Failures 92 5 Related Work 93 6 Conclusion 94 Message Passing or Shared Memory: Evaluating the Delegation Abstraction for Multicores 95 1 Introduction 95 2 Delegation 97 3 Communication 97 4 Benchmarks 99 4.1 Concurrent Hash Maps 99 4.2 Concurrent Linked Lists 100 4.3 Workloads 100 5 Performance Results 101 5.1 Hash Map 101 5.2 Linked List 102 5.3 Fairness 104 Hardware-Related Details 105 6 Discussion 106 7 Related Work 107 8 Conclusions 108 Reputation-Based Mechanisms for Evolutionary Master-Worker Computing 110 1 Introduction 110 2 Model 113 3 Reputation-Based Mechanism 115 4 Analysis 116 5 Simulations 119 6 Conclusions and Future work 123 State-Driven Testing of Distributed Systems 126 1 Introduction 126 2 Related Work 127 3 Basic Concepts and Problem Statement 128 4 A State-Driven Testing Approach 130 4.1 The Workload Search Phase 131 4.2 The Testing Phase 132 5 Case Study 133 6 Experimental Evaluation 136 7 Conclusion 139 Self-stabilizing Resource Discovery Algorithm 141 1 Introduction 141 2 Models and Definitions 145 3 Description of Resource Discovery Algorithm RDS 148 4 Algorithm Analysis 151 5 Discussion 154 Hybrid Distributed Consensus 157 1 Introduction 157 2 Preliminaries 159 2.1 Basic Model and Assumptions 159 2.2 Benign Failures 160 2.3 Additional Services 160 3 Hybrid Consensus with Benign Failures 161 3.1 Problem Statement 161 3.2 Lower Bounds 162 3.3 Upper Bounds 164 4 Related Work 167 5 Discussion 168 6 Non-Blocking Atomic Commit 170 Speculative Concurrent Processing with Transactional Memory in the Actor Model 172 1 Introduction 172 2 Background and Related Work 173 3 Problem Statement 175 4 Message Processing Model 176 5 Implementation 177 6 Evaluation 178 6.1 Read-Dominated Workload 180 6.2 Write-Dominated Workload 182 6.3 Non-blocking Concurrent Processing 183 6.4 Comparison to Habanero-Scala 184 6.5 Discussion 185 6 Conclusion 185 An Optimal Broadcast Algorithm for Content-Addressable Networks 188 1 Introduction 188 2 Related Works and Objectives 189 2.1 Context and Motivation 189 2.2 Positioning 190 2.3 Related Works 191 2.4 M-CAN 192 3 Efficient Broadcast Algorithm 193 3.1 Principles 193 3.2 Broadcast Algorithm 194 3.3 Properties of the Algorithm 196 4 Evaluation 198 4.1 Variation of the Number of Peers 199 5 Conclusion 201 On Local Fixing 203 1 Introduction 203 2 Model 205 2.1 tributed Computing 205 2.2 Network Problems 206 2.3 Examined Graph Changes 206 3 Related Work 207 4 Results 209 4.1 Graph Change Relationships 209 4.2 Vertex Counting 210 4.3 Minimum Dominating Set 211 4.4 Maximal Independent Set 212 4.5 Maximal Matching 213 4.6 Spanning Trees 213 4.7 Minimum Spanning Trees 214 4.8 Shortest Paths Trees 214 4.9 Maximum Flow 215 4.10 Leader Election 215 A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention 218 1 Introduction 218 2 Related Work 220 3 Overview of Main Ideas 221 4 The Algorithm 223 5 Correctness and Linearizability 227 6 Performance Evaluation 229 7 Conclusion 231 VirtuCast: Multicast and Aggregation with In-Network Processing 233 1 Introduction 233 2 The Constrained Virtual Steiner Arborescence Problem 235 3 VirtuCast Algorithm 238 3.1 IP Formulation 238 3.2 Decomposition Algorithm 240 4 Computational Evaluation 244 5 Related Work 245 6 Conclusion 246 Mobile Byzantine Agreement on Arbitrary Network 248 1 Introduction 248 2 Preliminaries 250 2.1 System Model 250 2.2 Fault Model: Mobile Byzantine Faults 250 2.3 Mobile Byzantine Agreement Problem 251 2.4 MBA: Banu et al.'s Mobile Byzantine Agreement Algorithm 252 3 Upper Bound on the Number of Faulty Processes 254 4 Two Mobile Byzantine Agreement Algorithms 256 4.1 Algorithm DP-Byz 256 4.2 Algorithm KP-Byz 259 5 Conclusion 261 On Scheduling Algorithms for MapReduce Jobs in Heterogeneous Clouds with Budget Constraints 263 1 Introduction 263 2 Background and Related Work 266 3 Problem Formulation 267 3.1 Workflow Model 267 3.2 Budget Constraints 268 4 Budget-Driven Algorithms 268 4.1 Optimization under Budget Constraints 269 4.2 Efficiency Improvements 270 5 Empirical Studies 273 5.1 Impact of Time-Price Table Size 274 5.2 Impact of Workflow Size 275 6 Conclusions 275 Fast and Scalable Queue-Based Resource Allocation Lock on Shared-Memory Multiprocessors 278 1 Introduction 278 2 Background 280 2.1 Mutual Exclusion and Resource Allocation 280 2.2 Atomic Primitives and Synchronization 281 3 Algorithms 282 3.1 Handle Locking Request with FIFO Queue 282 3.2 Acquiring and Releasing Locks 283 4 Related Work 285 4.1 Resource Allocation Solutions 285 4.2 Queue-Based Algorithms 286 5 Performance Evaluation 286 5.1 Single-Thread Overhead 287 5.2 Resource Scalability 288 5.3 Thread Scalability 290 5.4 Performance Consistency 290 6 Conclusion and Future Work 291 Author Index 293 Front Matter....Pages - Tutorial Summary: Paxos Explained from Scratch....Pages 1-10 On Two-Party Communication through Dynamic Networks....Pages 11-22 Eventual Leader Election in Evolving Mobile Networks....Pages 23-37 Self-stabilizing Leader Election in Population Protocols over Arbitrary Communication Graphs....Pages 38-52 α -Register....Pages 53-67 How (Not) to Shoot in Your Foot with SDN Local Fast Failover....Pages 68-82 Message Passing or Shared Memory: Evaluating the Delegation Abstraction for Multicores....Pages 83-97 Reputation-Based Mechanisms for Evolutionary Master-Worker Computing....Pages 98-113 State-Driven Testing of Distributed Systems....Pages 114-128 Self-stabilizing Resource Discovery Algorithm....Pages 129-144 Hybrid Distributed Consensus....Pages 145-159 Speculative Concurrent Processing with Transactional Memory in the Actor Model....Pages 160-175 An Optimal Broadcast Algorithm for Content-Addressable Networks....Pages 176-190 On Local Fixing....Pages 191-205 A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention....Pages 206-220 VirtuCast: Multicast and Aggregation with In-Network Processing....Pages 221-235 Mobile Byzantine Agreement on Arbitrary Network....Pages 236-250 On Scheduling Algorithms for MapReduce Jobs in Heterogeneous Clouds with Budget Constraints....Pages 251-265 Fast and Scalable Queue-Based Resource Allocation Lock on Shared-Memory Multiprocessors....Pages 266-280 Back Matter....Pages - This book constitutes the refereed proceedings of the 16th International Conference on Principles of Distributed Systems, OPODIS 2012, held in Rome, Italy, in December 2012. The 24 papers presented were carefully reviewed and selected from 89 submissions. The conference is an international forum for the exchange of state-of-the-art knowledge on distributed computing and systems. Papers were sought soliciting original research contributions to the theory, specification, design and implementation of distributed systems.