Stabilization, Safety, and Security of Distributed Systems

Name: Stabilization, Safety, and Security of Distributed Systems | 20th International Symposium, SSS 2018, Tokyo, Japan, November 4-7, 2018, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

20th International Symposium, SSS 2018, Tokyo, Japan, November 4-7, 2018, Proceedings

Taisuke Izumi Petr Kuznetsov(Herausgeber*in)

Springer (Verlag)

Erschienen am 25. Oktober 2018

XIII, 410 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-030-03232-6 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Contents
A Self-stabilizing Hashed Patricia Trie
1 Introduction
1.1 Model
1.2 Related Work
1.3 Our Contribution
2 Hashed Patricia Trie
3 The SHPT Protocol
3.1 Properties of the DHT
3.2 Correcting Edge Information
3.3 Maintaining Connections
3.4 Removal/Creation of Nodes
3.5 Distribution of References to Keys
4 Protocol Analysis
4.1 Correctness
4.2 Overhead
References
Self-stabilizing Overlays for High-Dimensional Monotonic Searchability
1 Introduction
1.1 Model
1.2 Problem Statement
1.3 Our Contribution
1.4 Related Work
2 Topology and Legitimate State
3 Protocol Description
3.1 List Edges
3.2 Quad Edges
3.3 Routing
4 Analysis
4.1 Quadtree
4.2 Geographic Monotonic Searchability
5 Conclusion and Future Work
References
An Adaptive Logging Framework for Persistent Memories
1 Introduction
2 Model
3 Adaptive Logging Framework
4 Experimental Evaluation
5 Concluding Remarks
References
On Underlay-Aware Self-Stabilizing Overlay Networks
1 Introduction
1.1 Model and Definitions
1.2 Our Contribution
2 Related Work
3 Preliminaries
4 Protocol
5 Analysis
6 Conclusion and Outlook
References
A O(logn) Distributed Algorithm to Construct Routing Structures for Pub/Sub Systems
1 Introduction
1.1 State of the Art
1.2 Computational Model and Assumptions
2 Informal Description of Algorithm AFiber
2.1 Relationship to Routing Scheme PSVR
3 Formal Description of Algorithm AFiber
3.1 Phase 0
3.2 Phase 1
3.3 Middle Phases
3.4 The Final Phase
4 Analysis of Algorithm AFiber for Random Graphs
4.1 Phase 1
4.2 Middle Phases
4.3 The Final Phase
5 Extensions
6 Conclusion
References
Self-stabilization and Byzantine Tolerance for Maximal Matching
1 Introduction and State of the Arts
2 Model
3 Maximal Matchings
3.1 Problem Specification
3.2 From legitimacy to weakly-legitimacy
4 2-Spec under the Distributed Daemon
5 1-Spec Under the Central Daemon
6 About 1-Spec and the Distributed Daemon
References
Exploration of Finite 2D Square Grid by a Metamorphic Robotic System
1 Introduction
2 Preliminary
3 Exploration with Global Compass
4 Exploration Without Global Compass
5 Conclusion and Future Work
References
Physical Zero-Knowledge Proof for Makaro
1 Introduction
2 Rules of Makaro
3 Zero-Knowledge Proof for Makaro
3.1 Notations
3.2 Rearrangement Protocol
3.3 Our Construction
4 Security Proofs for Our Construction
5 Conclusion
References
Searching with Increasing Speeds
1 Introduction
1.1 The Model and the Search Problem
1.2 Our Contribution
2 Search on the Line
2.1 Variant (1) - with Full Knowledge
2.2 Variant (2) - with Local Knowledge
3 Search on 2d Plane
3.1 Variant (1) - with Global Knowledge
3.2 Variant (2) - with Local Knowledge
4 Conclusion
References
BEE'S STRATEGY AGAINST BYZANTINES Replacing Byzantine Participants
1 Introduction
2 System Settings
3 Byzantine Detection and Replacement
4 Byzantine Free Fast Termination
5 Using Byzantine Agreement Objects
5.1 Global Hypervisor
5.2 Local Hypervisor
6 Conclusion
References
Simple and Fast Approximate Counting and Leader Election in Populations
1 Introduction
1.1 Related Work
1.2 Contribution
2 The Model
3 Fast Counting with a Unique Leader
3.1 Abstract Description and Protocol
3.2 Analysis
4 Leader Election with Approximate Knowledge of n
4.1 Abstract Description
4.2 The Protocol
4.3 Analysis
4.4 Dropping the Assumption of Knowing logn
5 Experiments
6 Open Problems
References
Reliable Broadcast in Dynamic Networks with Locally Bounded Byzantine Failures
1 Introduction
2 System Model & Problem Statement
3 The Certified Propagation Algorithm (CPA)
4 The Certified Propagation Algorithm on Dynamic Networks
4.1 CPA Safety in Dynamic Networks
4.2 CPA Liveness in Dynamic Networks
5 On the Detection of DCPA Liveness
5.1 Detecting DCPA Liveness on Generic TVGs
5.2 Detecting DCPA Liveness on Restricted TVGs
6 Conclusion
References
Acyclic Strategy for Silent Self-stabilization in Spanning Forests
1 Introduction
2 Preliminaries
3 Algorithm with Acyclic Strategy
4 Move Complexity of Algorithms with Acyclic Strategy
5 Analysis of TE
6 Round Complexity of Algorithms with Acyclic Strategy
7 Related Work and Applications
8 Conclusion
References
On Fast Pattern Formation by Autonomous Robots
1 Introduction
2 Preliminaries
3 A Pattern Formation Framework
4 Pattern Formation on SSYNC Robots with Lights
5 Pattern Formation on ASYNC Robots with Lights
6 Pattern Formation on SSYNC Classical Robots
7 Lower Bound, Time-Optimality and Trade-Offs
8 Concluding Remarks
References
Load Balanced Distributed Directories
1 Introduction
2 Network Model
3 Hierarchical Clustering
4 LB-Spiral Algorithm
5 Analysis of LB-Spiral
References
Relays: A New Approach for the Finite Departure Problem in Overlay Networks
1 Introduction
1.1 System Model
1.2 Problem Statement
1.3 Related Work
1.4 Our Contributions
2 The Relay Layer
2.1 Relays
2.2 Relay Layer Primitives
2.3 Message Processing and Action Handling
2.4 Properties of the Relay Layer
3 Universality of the Relay Approach
References
Clairvoyant State Machine Replications
1 Introduction
2 Related Work
3 Problem and System Model
4 Byblos Description
4.1 Client Code
4.2 Server Code
5 Correctness
6 Eliminating Pending Sets
7 Byzantine Clients
8 Performance
8.1 Performance in Gracious Executions
8.2 Performance in Uncivil Executions
8.3 Other Performance Considerations
References
Set Agreement and Renaming in the Presence of Contention-Related Crash Failures
1 Definitions and Motivation
1.1 Processes, Failures, Communication
1.2 Motivation for Considering -Constrained Failures
1.3 High Level Objects
2 k-Set Agreement and M-Renaming
2.1 k-Set Agreement
2.2 M-Renaming
3 The Results of the Paper at a Glance
3.1 Results Concerning k-Set Agreement
3.2 Results Concerning M-Renaming
4 k-Set Agreement: Algorithm (k2)
5 k-Set Agreement: Proof
6 M-Renaming: Algorithm
7 M-Renaming: Proof
8 From M-Renaming to One-Shot Concurrent Objects
9 Conclusion
References
An Innovative Approach to Achieve Compositionality Efficiently Using Multi-version Object Based Transactional Systems
1 Introduction
2 Building System Model
3 HT-MVOSTM Design and Data Structure
4 Working of HT-MVOSTM
5 Experimental Evaluation
6 Conclusion and Future Work
References
Ring Exploration with Myopic Luminous Robots
1 Introduction
1.1 Background and Motivation
1.2 Our Contributions
2 Preliminaries
2.1 System Model
2.2 Algorithm, Execution, Problem, and Exploration Problem
2.3 Descriptions
3 Full-Synchronous Robots
3.1 Perpetual Exploration
3.2 Terminating Exploration
4 Semi-synchronous and Asynchronous Robots
4.1 Perpetual Exploration
4.2 Terminating Exploration
5 Conclusions
References
Uniform Circle Formation for Swarms of Opaque Robots with Lights
1 Introduction
1.1 Motivation and Contribution of the Paper
2 Preliminaries: The Computational Model and the Problem
3 A Preliminary Step of Our Algorithm and Terminology
4 The Algorithm
4.1 Cycle 1: Pivots Selection and Angle Setting
4.2 Cycle 2: Preparing Safe Diameters Setting
4.3 Cycle 3: Fair Distribution on the Two Half-Disks
4.4 Cycle 4: Rappelling down on the Safe Diameters or Safe Chords
4.5 Cycle 5: Reaching the SEC
5 Conclusions and Future Work
References
Arbitrary Pattern Formation with Four Robots
1 Introduction
2 The Model
3 The H-segment of a Quadrilateral
3.1 The Construction of an H-segment
3.2 The H-coordinates of Four Points
3.3 The H-segment of a Non-orthodiagonal Quadrilateral
3.4 The -square of a Segment
4 4-Robot Pattern Formation Algorithm
4.1 Algorithm Overview
4.2 Algorithm Details
4.3 Proof of Correctness
5 Conclusion
References
Gracefully Degrading Gathering in Dynamic Rings
1 Introduction
2 Model
3 Impossibility Results
4 Gracefully Degrading Gathering
5 Conclusion
References
Concurrent Lock-Free Unbounded Priority Queue with Mutable Priorities
1 Introduction
2 Preliminaries
3 Algorithm
3.1 Lock-Free ADT Operations
3.2 Design Optimizations
4 Correctness Proof
5 Evaluation
6 Conclusion
References
Brief Announcement: Deterministic Leader Election in Self-organizing Particle Systems
1 Introduction
2 System Model
3 Leader Election
References
Brief Announcement: Time Efficient Self-stabilizing Stable Marriage
1 Introduction
2 Self-stabilizing Stable Marriage in O(n2) Moves
References
Brief Announcement: Feasibility of Weak Gathering in Connected-over-Time Dynamic Rings
1 Introduction
2 Preliminaries
3 Impossibility Results
4 A Gathering Algorithm
References
Brief Announcement: Optimal Self-stabilizing Mobile Byzantine-Tolerant Regular Register with Bounded Timestamps
1 Introduction
2 System Model
3 Self-stabilizing Regular Register Specification
4 Optimal Self-stabilizing MBFT Regular Register
5 Concluding Remarks
References
Brief Announcement Continuous vs. Discrete Asynchronous Moves: A Certified Approach for Mobile Robots
1 Continuous vs. Discrete Spaces
2 Related Works
3 Our Contribution
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken