Distributed Computing

Name: Distributed Computing | 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings

Yoram Moses(Editor)

Springer (Publisher)

Published on 3. October 2015

XXI, 678 pages

E-Book

PDF with digital watermarking

System requirements

978-3-662-48653-5 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

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
4 Symmetry Breaking Tasks
4.1 Leader Election
5 Approximation Tasks: Degree Approximation
6 Revealing Asymmetry -- Distributed Tournament
7 Discussion
References
Specifying Concurrent Problems:Beyond Linearizability and up to Tasks
1 Introduction
2 Limitations of Linearizability and Set-Linearizability
3 Concurrent Objects
3.1 System Model
3.2 The Notion of an Interval-Sequential Object
3.3 An Example: The Validity Task
4 Interval-Linearizability
5 Tasks and Interval-Sequential Objects
References
From Geometric Semantics to Asynchronous Computability
1 Introduction
2 Concurrent Semantics of Asynchronous Read/Write Protocols
2.1 Interleaving Semantics of Atomic Read/Write Protocols
2.2 Directed Geometric Semantics
2.3 Equivalence of the Standard and Geometric Semantics
3 Protocol Complexes, Derived from the Concurrent Semantics
3.1 Protocol Complex
3.2 Construction of the Protocol Complex from the Directed Geometric Semantics
3.3 Particular Case of 1-Round Immediate Snapshot Protocols
4 Conclusion and Future Work
On the Optimal Space Complexity of Consensus for Anonymous Processes
1 Introduction
2 Space Complexity Lower Bound
2.1 A Square-Root Lower Bound
2.2 Linear Lower Bound
3 Extensions
References
Compressing Communication in Distributed Protocols
1 Introduction
1.1 Our Results
1.2 Related Work
1.3 Overview of Our Techniques
2 Preliminaries
3 Compressing Communication in Distributed Protocols
3.1 Static Adversaries
4 Public-Coin Protocols
References
Privacy-Conscious Information Diffusion in Social Networks
1 Introduction
2 The Diffusion Algorithm
2.1 Privacy
2.2 Dissemination
3 Experiments
4 Conclusion
References
Fair Distributed Computation of Reactive Functions
1 Introduction
2 Preliminaries and Model
3 Utility-Based Fairness and Protocol Optimality
4 Fair and Reactive 2PC
4.1 Better Fairness Through More Rounds
4.2 The Fair Reactive Protocol
4.3 Lower Bounds
References
Smoothed Analysis of Dynamic Networks
1 Introduction
2 Dynamic Graphs, Networks, and Types
3 Smoothing Dynamic Graphs
4 Connected and Pairing Dynamic Network Types
4.1 Connected Network
4.2 Pairing Network
5 Flooding
5.1 Lower Bound
5.2 An O(n2/3logn / k1/3) Upper Bound for General Networks
6 Random Walks
6.1 Preliminaries
6.2 Upper Bounds
6.3 Lower Bounds
7 Aggregation
7.1 Lower Bound
References
Fault Tolerant Reachability for Directed Graphs
1 Introduction
1.1 Related Work
1.2 Organization of the Paper
2 Preliminaries
3 DFS Tree Versus Arbitrary Tree
4 Semidominators with Respect to Arbitrary Trees
5 FTRS for any Arbitrary Tree
6 Algorithm for Computing Semidominators and Valid Sequences
6.1 Data Structure
7 Computation of Dominators from Semidominators
References
Locally Optimal Load Balancing
1 Introduction
1.1 Centralised Algorithms
1.2 Local Solutions and Local Algorithms
1.3 Smoothing with Moving Average
1.4 Contributions
2 Related Work
3 Negative Results
3.1 Load Balancing on Paths and Cycles
3.2 Match-and-Balance Algorithms
3.3 Careful Algorithms
3.4 Oblivious Algorithms
4 Discrete Load Balancing in Paths and Cycles
5 Discrete Load Balancing in General Graphs
6 Fractional Load Balancing in General Graphs
7 Conclusions
References
Distributed Large Independent Sets in One Round on Bounded-Independence Graphs
1 Introduction
2 Poly-Logarithmic Approximation on Bounded-Independence Graphs
3 Distributed Algorithm with Single Bit Messages
4 Lower Bound for One-Round Algorithms on General Graphs
5 Lower Bound for d-dimensional Unit Sphere Graphs
References
Tight Bounds for MIS in Multichannel Radio Networks
1 Introduction
2 Preliminaries
3 Algorithm Description
4 Analysis
4.1 Guarantees from the Decay Filter
4.2 Definitions for the Herald Filter
4.3 Candidate Election---Nodes in States A (and L')
4.4 Handshake & Red-Blue Protocol---States L', H', L, H
4.5 Joining the MIS---Nodes in States M and E
4.6 Progress and Runtime
References
Nonuniform SINR+Voroni Diagrams Are Effectively Uniform
1 Introduction
1.1 Background and Motivation
1.2 Geometric Notions and Wireless Networks
2 Convexity of SINR+Voronoi Zones
2.1 Proof Outline
2.2 Convexity without Background Noise
2.3 Convexity with Background Noise
3 Fatness of SINR+Voronoi Zones
4 Applications
4.1 The Power Control Voronoi Diagram (PCVD) Problem
4.2 The Closest Station Point Location Problem
5 Conclusion
References
Stable Leader Election in Population Protocols Requires Linear Time
1 Introduction
2 Preliminaries
3 Main Results
3.1 Impossibility of Sublinear Time Stable Leader Election
3.2 More General Impossibility Result in Terms of Inapplicable Transitions and Dense Configurations
4 Technical Tools
4.1 Bottleneck Transitions Require Linear Time
4.2 Sublinear Time from Dense Configurations Implies Bottleneck Free Path from Configurations with Every State ``Populous''
4.3 Transition Ordering Lemma
5 Proof of Theorem 3.2
References
Hardware Transactions in Nonvolatile Memory
1 Introduction
1.1 Related Work
2 Persistent HTM
2.1 Problem Definition
2.2 Data Store Flow
3 PHTM Implementation
3.1 Hardware Ramifications
3.2 Software Details
3.3 Correctness and Liveness
4 Evaluation
4.1 Hardware Emulation
4.2 Compared Algorithms
4.3 Benchmarks
5 Conclusion
References
Space-Optimal Counting in Population Protocols
1 Introduction
2 Model and Notations
3 Space-Optimal Counting under Global Fairness
4 Space-Optimal Counting under Weak Fairness
5 Conclusion and Perspectives
References
Brief Announcement: On the Voting Time of the Deterministic Majority Process
Brief Announcement: Rumor Spreading with Bounded In-Degree
Brief Announcement: On the Power of One Bitin Graph Exploration Without Backtracking
Brief Announcement: Uniform Information Exchange in Multi-channel Wireless Ad HocNetworks
Brief Announcement: Self-stabilizing Virtual Synchrony
Brief Announcement: Distributed Task Allocation in Ant Colonies
Brief Announcement: A Concurrency-Optimal List-Based Set
Brief Announcement: HTM-Assisted Combining
Brief Announcement: Left-Right - AConcurrency Control Technique with Wait-Free Population Oblivious Reads
Brief Announcement: Tight Space Bounds for Memoryless Anonymous Consensus
Brief Announcement: On the Uncontended Complexity of Anonymous Consensus
Brief Announcement: AnonymousObstruction-free(n, k)-Set Agreement with n - k + 1 Atomic Read/Write Registers
Brief Announcement: Faster Data Structures in Transactional Memory Using Three Paths
Brief Announcement: Space Bounds for Reliable Multi-Writer Data Store Inherent Cost of Read/Write Primitives
DISC 2015 Special Poster Session List
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Distributed Computing

Description

More details

Other editions

Additional editions

Content

System requirements