Stabilization, Safety, and Security of Distributed Systems: 23rd International Symposium, SSS 2021, Virtual Event, November 17–20, 2021, Proceedings (Theoretical Computer Science and General Issues)

Preface
Organization
Contents
Distributed Computing with the Cloud
	1 Introduction
		1.1 Model Specification
		1.2 Problems Considered and Main Results
		1.3 Related Work
	2 Communication Primitives in CWC
	3 Computing and Writing Combined Values
		3.1 Combining in General Graphs
		3.2 Combining Commutative Operators in Fat Links Network
	4 Non-commutative Operators and the Wheel Settings
	5 CWC Applications
		5.1 Federated Learning in CWC
		5.2 File Deduplication with the Cloud
	6 Conclusion and Open Problems
	References
Byzantine-Tolerant Reliable Broadcast in the Presence of Silent Churn
	1 Introduction
	2 Computing Model
	3 Silent Churn Byzantine-Tolerant Broadcast: Definition
	4 An Algorithm Implementing the SCB-Broadcast Abstraction
		4.1 Signatures, Local Data Structures and Message Types
		4.2 Algorithm
	5 Proof of the Algorithm
	6 Cost of the Algorithm
	7 Conclusion
	References
Building Systems of Systems with Escher
	1 Introduction
	2 Escher Design
		2.1 System Model: Agents and Message Bus
		2.2 Refining Agents
		2.3 Wrappers
		2.4 Deploying and Managing Agents
		2.5 Compatibility with Legacy Services
	3 Implementation
		3.1 Message Merging
		3.2 Message Delivery
		3.3 Implementing Tagging and Merging
		3.4 Garbage Collection of Delivered Messages
	4 Related Work
	5 Conclusion
	References
Deadlock and Noise in Self-Organized Aggregation Without Computation
	1 Introduction
	2 The Gauci et al. Swarm Aggregation Algorithm
	3 Impossibility of Aggregation for n > 3 Robots
	4 Robustness to Error and Noise
	5 Using a Cone-of-Sight Sensor
	6 Conclusion
	References
Failure is (literally) an Option: Atomic Commitment vs Optionality in Decentralized Finance
	1 Introduction
	2 Model
	3 Classical Two-Phase Commit Protocol
	4 Cross-Chain Atomicity
	5 Cross-Chain Atomicity with Optionality
	6 Cross-Chain Atomicity with Transferable Optionality
	7 Related Work
	8 Conclusions
	References
Privacy-Preserving Data Sharing for Medical Research
	1 Introduction
	2 Related Work
	3 Medical Information Workflow
	4 Privacy-Preserving Linking of Patient Data
		4.1 Blinding-Completion Pairs
		4.2 Implementation
		4.3 Key Rotation
	5 Proposed Workflow for Enhanced Security
		5.1 Trust
		5.2 Parties
		5.3 Identifiers
		5.4 Initialization
		5.5 Contribution of Patient Profiles
		5.6 Accessing Medical Data for Research
	6 Threat Analysis
	7 Conclusion
	References
How Do Mobile Agents Benefit from Randomness?
	1 Introduction
		1.1 Our Results
		1.2 Related Work
	2 Model
		2.1 Deterministic Systems
		2.2 Randomized Systems
	3 Indistinguishability
	4 Distinguishability
	5 Conclusion
	References
A Lattice Linear Predicate Parallel Algorithm for the Housing Market Problem
	1 Introduction
	2 Background
		2.1 Gale\'s Top Trading Cycle (TTC) Algorithm for Housing Market
		2.2 LLP Algorithm
		2.3 Notation
	3 Applying LLP Algorithm to the Housing Market Problem
	4 An Efficient Parallel Algorithm for the Housing Market Problem
	References
Security in Asynchronous Interactive Systems
	1 Introduction
	2 The Model
	3 Secure Computation in Interactive Settings
		3.1 The BGW/BCG Notion of Secure Computation
		3.2 Secure Computation and Mediators
		3.3 Beyond Secure Computation
		3.4 Simulating Arbitrary Protocols
		3.5 Universally Composable Security
		3.6 Variant Models
	4 Proof of Theorem 2
	5 Conclusion
	References
A New Problem Setting for Mobile Robots Based on Backscatter-Based Communication and Sensing
	1 Introduction
	2 Ambient Backscatter Communication and Sensing
		2.1 Ambient Backscatter Communication
		2.2 Backscatter Sensing of Humans and Objects
	3 Developed Software Defined Radio (SDR) System
	4 Context Recognition of Humans and Objects Using SDR System
	5 Backscatter-Based Communication and a New Problem Setting for Mobile Robots
	6 Conclusion
	References
Round-Oblivious Stabilizing Consensus in Dynamic Networks
	1 Introduction
	2 Additional Related Work
	3 Basic System Model
	4 Basic Message Adversaries
	5 Round-Oblivious Consensus
		5.1 The Message Adversary STABLEN,D(D+1)
		5.2 A Round-Oblivious Consensus Algorithm for STABLEN,D(D+1)
	6 Impossibility of Consensus with Immediate Acknowledgments
	7 Stabilizing Consensus
		7.1 Extensions of the Basic Model
		7.2 The Message Adversary WEAKSTABN(D+1,D)
		7.3 A Stabilizing Consensus Algorithm for WEAKSTABN(D+1,D)
		7.4 Impossibility of Stabilizing Consensus with Insufficient Stability
	8 Conclusions
	References
Towards a Robust Distributed Framework for Election-Day Voter Check-In
	1 Introduction
	2 Electronic Poll Books
	3 Electronic Pollbooks as a Distributed System
		3.1 The Manual Process
		3.2 Distribution and Consistency: Immediate Challenge
		3.3 Specific Technical Questions
		3.4 Requirements for Electronic Poll Books as Distributed Systems
	4 E-Pollbooks and the Distributed Systems Theory
		4.1 Consistent Data Store with Device Crashes
		4.2 Coordinated Action with Link Failures
		4.3 Availability, Consistency, and Network Partitions
		4.4 Reaching Agreement in the Presence of Crashes and Asynchrony
		4.5 Agreement in the Presence of Malicious Failures
		4.6 The Problem of Reconfiguration in Dynamic Systems
	5 A Broader Look at E-Pollbook Landscape
		5.1 Social and Political Science
		5.2 Computing Theory Foundation
		5.3 Systems: Development, Implementation, and Evaluation
	6 Discussion
	References
Asynchronous Proof-of-Stake
	1 Introduction
		1.1 Relaxing Consensus
		1.2 Intuition
	2 Model
	3 Protocol
		3.1 Transactions
		3.2 Validators
		3.3 Confirmations
		3.4 Adversary
	4 Correctness
	5 Future Work
	6 Related Work
	7 Conclusions
	References
Lack of Quorum Sensing Leads to Failure of Consensus in Temnothorax Ant Emigration
	1 Introduction
	2 Model
		2.1 Timing Model and the Environment
		2.2 Model of Individual Ants Without Quorums
		2.3 Dynamics of the Entire Colony
	3 The Consensus Problem
	4 Failure of Consensus in Two-Nest Environments
		4.1 Analysis of Main Result
	5 Extension: Failure of Consensus in More-Nest Environments
	6 Consensus with Quorum Sensing in Two-Nest Environments
	7 Discussion and Future Work
	References
Location Functions for Self-stabilizing Byzantine Tolerant Swarms
	1 Introduction
	2 Preliminaries
		2.1 A Robot Model
		2.2 Location Functions
		2.3 Function-Based Tasks
	3 t-Byzantine-resilient Self-stabilizing Algorithms Based on Location Functions
		3.1 A General Algorithm
		3.2 Implementation for Polynomial-Based Tasks
		3.3 Implementation for Shape-Based Tasks
	4 Task Scheme
		4.1 Convergence
		4.2 Marching
		4.3 Exploration
	5 Conclusions
	References
Applications and Implications of a General Framework for Self-Stabilizing Overlay Networks
	1 Introduction
		1.1 Problem Overview
		1.2 Main Results and Significance
		1.3 Related Work and Comparison
	2 Preliminaries
		2.1 Model of Computation
		2.2 Complexity Measures
	3 Generalizing Avatar
		3.1 Avatar Definition
		3.2 The Avatar Algorithm
		3.3 Relevant Metrics
		3.4 Overall Complexity
	4 Examples
		4.1 Linear
		4.2 Complete Binary Search Tree
		4.3 Chord
	5 SkipChord
		5.1 Definition
		5.2 Metrics
	6 Discussion and Future Work
	References
Network Scaffolding for Efficient Stabilization of the Chord Overlay Network
	1 Introduction
	2 Preliminaries
		2.1 Model of Computation
		2.2 Performance Metrics
	3 Avatar
		3.1 The Avatar Overlay Network
		3.2 Avatar(CBT)
	4 Avatar(Chord)
		4.1 Overview of Our Approach
		4.2 Chord(N)
		4.3 Building Chord from Cbt
		4.4 Phase Selection
	5 Analysis
	6 Generalizing Our Approach
	7 Concluding Thoughts
	References
The Agreement Power of Disagreement
	1 Introduction
	2 Preliminaries
	3 An Algorithm When = 2
	4 An Algorithm When [min, max]
	5 Concluding Remarks
	References
The Max-Line-Formation Problem
	1 Introduction
	2 Model and Notation
	3 Impossibility Result and Intuition About Square Ranges
		3.1 Impossibility with Circular Ranges
		3.2 Intuition About Square Ranges
	4 OBLOT Algorithm
		4.1 Intuition
		4.2 Algorithm
		4.3 Analysis
	5 LUMI Algorithms
	6 Relation to Gathering and Chain-Formation
	References
Message Delivery in the Plane by Robots with Different Speeds
	1 Introduction
		1.1 Model, Notation and Terminology
		1.2 Related Work
		1.3 Outline and Results of the Paper
	2 Optimal Offline Algorithm for Two Robots
		2.1 Optimal Algorithm When a Robot Starts at the Source
		2.2 Optimal Algorithm in the General Case
	3 Offline 2 Approximation for Multiple Robots
	4 Online Upper Bounds
		4.1 Two Robot Algorithm with Competitive Ratio 17(5+4 2)
		4.2 Multi Robot Algorithm with Competitive Ratio 2
	5 Online Lower Bounds for Two Robots
	6 Conclusion
	References
Exploring a Dynamic Ring Without Landmark
	1 Introduction
		1.1 Related Work
		1.2 Our Contributions
		1.3 Outline of the Paper
	2 Model and Terminology
	3 Exploration by Agents with Chirality
		3.1 Meeting by Agents with Chirality
		3.2 Exploration with Termination by Agents with Chirality
	4 Exploration by Agents Without Chirality
		4.1 Contiguous Agreement
		4.2 Meeting by Agents Without Chirality
		4.3 Exploration with Termination by Agents Without Chirality
	5 Concluding Remarks
	References
Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
	1 Introduction
		1.1 Related Work
		1.2 Our Contributions
	2 Preliminaries
		2.1 Loosely-Stabilizing MIS
	3 Redundant-State Approach
		3.1 Description of Algorithm RS
		3.2 Analysis of RS
	4 Step-Up Approach
		4.1 Description of Algorithm SU
		4.2 Analysis of SU
	5 Repetition Approach
		5.1 Description of Algorithm RE
		5.2 Analysis of RE
	6 Summary
	References
On Regenerating Codes and Proactive Secret Sharing: Relationships and Implications
	1 Introduction
	2 Background and Notation
		2.1 Reed-Solomon Codes
		2.2 Regenerating Codes
		2.3 Secret Sharing Schemes
		2.4 Leakage Model
	3 Related Work
	4 Leakage and Reconstruction: Old Models, New Lens
		4.1 Static Leakage
		4.2 Dynamic Leakage
	5 On the Equivalence of Regenerating Codes and Proactive Secret Sharing
	6 From General Adversary Structures to General Decoding Structures
		6.1 Generalized Decoding in Regenerating Codes
	References
Extending Lattice Linearity for Self-stabilizing Algorithms
	1 Introduction
		1.1 Contributions of the Article
		1.2 Organization of the Article
	2 Literature Study and Discussion on Our Contribution
	3 Preliminaries
		3.1 Modeling Algorithms
		3.2 Lattice Linear Predicates
		3.3 The Communication Model
	4 Service-Demand Based Dominating Set
		4.1 Algorithm for SDDS Problem
	5 Lattice Linear Characteristics of Algorithm 1
		5.1 Propositions Stipulated by the SDDS Problem
		5.2 Guarantee to Reach a Feasible State by Algorithm 1.2
		5.3 Lattice Linearity of Algorithm 1.1
		5.4 Termination of Algorithm 1
		5.5 Eventual Lattice Linearity of Algorithm 1
		5.6 Analysis of Algorithm 1: Time and Space Complexity
	6 Other Examples
		6.1 Vertex Cover
		6.2 Independent Set
		6.3 Coloring
	7 Conclusion
	References
Information Exchange in the Russian Cards Problem
	1 Introduction
	2 Secure Information Exchange
		2.1 Correlated Inputs
		2.2 Informative, Minimally Informative and Safe Protocols
		2.3 Protocols and Johnson Graphs
	3 Minimal Information Exchange
		3.1 Two-Message Minimally Informative Protocol from Singer Sets
		3.2 Safety for Two-Message Minimally Informative Protocols
		3.3 Two-Step Minimally Informative Solution for (3, 3, 1)
	4 Russian Cards Problems
		4.1 Solutions with Six Messages
		4.2 Impossibility of Uniform Solutions
	5 Conclusions
	References
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
	1 Introduction
	2 Preliminaries
	3 Cographs
	4 Distance-Hereditary Graphs
	5 Lower Bounds
	References
Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
	1 Introduction
		1.1 Background and Motivation
		1.2 Our Contribution
	2 Model and Preliminaries
		2.1 The Basics
		2.2 The Models
		2.3 The Schedulers
	3 Simulating Algorithms in Unfair SSYNC by ASYNC LUMI Robots
		3.1 Simulation in ASYNC for Algorithms in Unfair SSYNC
		3.2 Gathering Algorithm with Simulation
	4 Gathering Algorithm in ASYNC with 3 Colors
		4.1 Configurations Becoming OnLDS
		4.2 Correctness of LUMI-Gather-in-ASYNC
	5 Concluding Remarks
	References
Synchronization Modulo k in Dynamic Networks
	1 Introduction
	2 Preliminaries
		2.1 The Computational Model
		2.2 Network Model and Start Model
	3 The Algorithm
		3.1 Pseudo-code and Formal Definition
		3.2 Informal Description of the Algorithm
		3.3 Notation and Preliminary Lemmas
		3.4 Correctness Proof
		3.5 Solvability Results
	4 Complexity Analysis
		4.1 Time Complexity Analysis
		4.2 Reducing Memory Usage
	5 Conclusion and Future Work
	References
Partial Gathering of Mobile Agents in Dynamic Rings
	1 Introduction
		1.1 Background and Related Work
		1.2 Our Contribution
	2 Preliminaries
		2.1 System Model
		2.2 The Partial Gathering Problem
	3 The Case of 3gk8g-2
		3.1 Selection Phase
		3.2 Gathering Phase
	4 The Case of k8g-3
		4.1 Semi-selection Phase
		4.2 Semi-gathering Phase
		4.3 Achievement Phase
	5 Conclusion
	References
Optimal Protocols for 2-Party Contention Resolution
	1 Introduction
		1.1 Prior Work
		1.2 New Results
	2 Problem Formulation
		2.1 Performance Metrics and Existence Issues
	3 Contention Resolution Between Two Parties
		3.1 Avg: Minimizing the Average Transmission Time
		3.2 Min: Minimizing the Earliest Transmission Time
		3.3 Max: Minimizing the Last Transmission Time
	4 Conclusion
	References
Computer Aided Formal Design of Swarm Robotics Algorithms
	References
Delta-State JSON CRDT: Putting Collaboration on Solid Ground
	1 Introduction
	2 Related Work
	3 Overview of the Data Structure
		3.1 Delta-State Decomposition
		3.2 Delta-State Serialization and Adapters
		3.3 Example Architecture of a Collaborative Application
	4 Evaluation
	5 Conclusion
	References
Self-stabilization and Byzantine Tolerance for Maximal Independent Set
	1 Model
	2 With Byzantine Nodes Under the Fair Daemon
	3 Anonymous System Under the Adversarial Daemon
	References
Coordinating Amoebots via Reconfigurable Circuits
	1 Introduction
	2 Reconfigurable Circuit Extension
	3 Problem Statement and Our Contribution
	References
On Optimal Doorway Egress by Autonomous Robots
	1 Introduction
	2 Doorway Egress
	3 Doorway Egress by Point Robots
	4 Doorway Egress by Fat Robots
	5 Concluding Remarks
	References
Byz-GentleRain: An Efficient Byzantine-Tolerant Causal Consistency Protocol
	1 Introduction
	2 Byzantine Causal Consistency
	3 The Byz-GentleRain Protocol
	4 Evaluation
	References
Mitigating Internal, Stealthy DoS Attacks in Microservice Networks
	1 Introduction
	2 Assumptions and Threat Model
	3 Mitigating SILVDDoS
	4 Preliminary Evaluation
	References
Flat-Combining-Based Persistent Data Structures for Non-volatile Memory
	1 Introduction
	2 The DFC Stack
	3 Experimental Evaluation
	References
SodsBC/SodsBC++ & SodsMPC: Post-quantum Asynchronous Blockchain Suite for Consensus and Smart Contracts
	1 Introduction
	2 SodsBC: Post-quantum aBFT Consensus
	3 SodsMPC: Post-quantum Smart Contracts
	References
Distributed Reconfiguration of Spanning Trees
	1 Introduction
	2 Preliminaries
	3 Proposed Algorithm
	4 Discussion and Conclusion
	References
Correction to: Distributed Computingwith the Cloud
	Correction to:Chapter “Distributed Computing with the Cloud”in: C. Johnen et al. (Eds.): Stabilization, Safety, and Securityof Distributed Systems, LNCS 13046,https://doi.org/10.1007/978-3-030-91081-5_1
Author Index