Principles of Distributed Systems 1st Edition by Hein Meling 9783319038490 3319038494

1 Introduction

2 A Stateful Service: Assumptions and Notation

3 Fault Tolerance with Two Servers

4 Server Crashes

5 Network Partitions

6 Leader Change

7 Five Servers

8 Summary

On Two-Party Communication Through Dynamic Networks

1 Introduction

1.1 Our Contribution

1.2 Organization of the Paper

2 Models and Problems

3 Related Work

4 Relating Counting to Communication through a Dynamic Network

4.1 Special Dynamic Networks and the Same Predecessor Problem

4.2 Dynamic Channel Networks and the Set Equality Problem

4.3 Two-Party Communication and the Set Equality Problem

5 Conclusion and Future Prospects

Eventual Leader Election in Evolving Mobile Networks

1 Introduction

2 Related Work

3 Model for Eventual Leader Election in Mobile Systems

3.1 Communication Model

3.2 Process Model

3.3 Network Connectivity

3.4 The Class

4 An Eventual Leader Oracle for Mobile Systems

4.1 Stable Query-Response Communication Mechanism

4.2 Behavioral Property

4.3 An Eventual Leader Election Algorithm

5 Proof of Correctness

6 Conclusion

Self-stabilizing Leader Election in Population Protocols over Arbitrary Communication Graphs

1 Introduction

2 Model and Definitions

2.1 Population Protocol

2.2 Run, Behaviour, Oracle and Implementation

3 Specific Behaviours and Oracles

3.1 Eventual Leader Election Behaviour ELE

3.2 Oracles ?(k,d)

4 Impossibility of Leader Election under Local Fairness with Uniform Initialization

5 Leader Election under Global Fairness with Uniform Initialization

6 Self-stabilizing Leader Election Using ?(2,1) under Global Fairness

7 Impossibility of Self-stabilizing Implementation of ? Using ELE under Global Fairness

8 Discussion and Open Problems

$alpha$-Register

1 Introduction

2 Computational Model and Definition of -Registers

3 Single-Writer Multiple-Reader -Register

3.1 Proof of the Protocol

4 Lower bound

5 Conclusion

How (Not) to Shoot in Your Footwith SDN Local Fast Failover

1 Introduction

2 You Must Shoot in Your Foot!

3 How Not to Shoot in Your Foot!

3.1 Randomized Failover

3.2 Deterministic Failover

4 Beyond Worst-Case Failures

5 Related Work

6 Conclusion

Message Passing or Shared Memory: Evaluating the Delegation Abstraction for Multicores

1 Introduction

2 Delegation

3 Communication

4 Benchmarks

4.1 Concurrent Hash Maps

4.2 Concurrent Linked Lists

4.3 Workloads

5 Performance Results

5.1 Hash Map

5.2 Linked List

5.3 Fairness

Hardware-Related Details

6 Discussion

7 Related Work

8 Conclusions

Reputation-Based Mechanisms for Evolutionary Master-Worker Computing

1 Introduction

2 Model

3 Reputation-Based Mechanism

4 Analysis

5 Simulations

6 Conclusions and Future work

State-Driven Testing of Distributed Systems

1 Introduction

2 Related Work

3 Basic Concepts and Problem Statement

4 A State-Driven Testing Approach

4.1 The Workload Search Phase

4.2 The Testing Phase

5 Case Study

6 Experimental Evaluation

7 Conclusion

Self-stabilizing Resource Discovery Algorithm

1 Introduction

2 Models and Definitions

3 Description of Resource Discovery Algorithm RDS

4 Algorithm Analysis

5 Discussion

Hybrid Distributed Consensus

1 Introduction

2 Preliminaries

2.1 Basic Model and Assumptions

2.2 Benign Failures

2.3 Additional Services

3 Hybrid Consensus with Benign Failures

3.1 Problem Statement

3.2 Lower Bounds

3.3 Upper Bounds

4 Related Work

5 Discussion

6 Non-Blocking Atomic Commit

Speculative Concurrent Processing with Transactional Memory in the Actor Model

1 Introduction

2 Background and Related Work

3 Problem Statement

4 Message Processing Model

5 Implementation

6 Evaluation

6.1 Read-Dominated Workload

6.2 Write-Dominated Workload

6.3 Non-blocking Concurrent Processing

6.4 Comparison to Habanero-Scala

6.5 Discussion

6 Conclusion

An Optimal Broadcast Algorithm for Content-Addressable Networks

1 Introduction

2 Related Works and Objectives

2.1 Context and Motivation

2.2 Positioning

2.3 Related Works

2.4 M-CAN

3 Efficient Broadcast Algorithm

3.1 Principles

3.2 Broadcast Algorithm

3.3 Properties of the Algorithm

4 Evaluation

4.1 Variation of the Number of Peers

5 Conclusion

On Local Fixing

1 Introduction

2 Model

2.1 tributed Computing

2.2 Network Problems

2.3 Examined Graph Changes

3 Related Work

4 Results

4.1 Graph Change Relationships

4.2 Vertex Counting

4.3 Minimum Dominating Set

4.4 Maximal Independent Set

4.5 Maximal Matching

4.6 Spanning Trees

4.7 Minimum Spanning Trees

4.8 Shortest Paths Trees

4.9 Maximum Flow

4.10 Leader Election

A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention

1 Introduction

2 Related Work

3 Overview of Main Ideas

4 The Algorithm

5 Correctness and Linearizability

6 Performance Evaluation

7 Conclusion

VirtuCast: Multicast and Aggregation with In-Network Processing

1 Introduction

2 The Constrained Virtual Steiner Arborescence Problem

3 VirtuCast Algorithm

3.1 IP Formulation

3.2 Decomposition Algorithm

4 Computational Evaluation

5 Related Work

6 Conclusion

Mobile Byzantine Agreement on Arbitrary Network

1 Introduction

2 Preliminaries

2.1 System Model

2.2 Fault Model: Mobile Byzantine Faults

2.3 Mobile Byzantine Agreement Problem

2.4 MBA: Banu et al.’s Mobile Byzantine Agreement Algorithm

3 Upper Bound on the Number of Faulty Processes

4 Two Mobile Byzantine Agreement Algorithms

4.1 Algorithm DP-Byz

4.2 Algorithm KP-Byz

5 Conclusion

On Scheduling Algorithms for MapReduce Jobs in Heterogeneous Clouds with Budget Constraints

1 Introduction

2 Background and Related Work

3 Problem Formulation

3.1 Workflow Model

3.2 Budget Constraints

4 Budget-Driven Algorithms

4.1 Optimization under Budget Constraints

4.2 Efficiency Improvements

5 Empirical Studies

5.1 Impact of Time-Price Table Size

5.2 Impact of Workflow Size

6 Conclusions

Fast and Scalable Queue-Based Resource Allocation Lock on Shared-Memory Multiprocessors

1 Introduction

2 Background

2.1 Mutual Exclusion and Resource Allocation

2.2 Atomic Primitives and Synchronization

3 Algorithms

3.1 Handle Locking Request with FIFO Queue

3.2 Acquiring and Releasing Locks

4 Related Work

4.1 Resource Allocation Solutions

4.2 Queue-Based Algorithms

5 Performance Evaluation

5.1 Single-Thread Overhead

5.2 Resource Scalability

5.3 Thread Scalability

5.4 Performance Consistency

6 Conclusion and Future Work