Structural Information and Communication Complexity: 28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28 – July 1, 2021, Proceedings (Lecture Notes in Computer Science)

This book constitutes the refereed conference proceedings of the 28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021, held in Wrocław, Poland, in June 2021. Due to COVID-19, the conference will be held online. The 20 full papers presented in this book were carefully reviewed and selected from 48 submissions. The papers are solicited from all areas of study of local structural knowledge and global communication and computational complexities. Among the typical areas are distributed computing, communication networks, game theory, parallel computing, social networks, mobile computing Preface Laudatio Selected Publications Related to Friedhelm Meyer auf der Heide’s Contribution: Organization Abstracts of Invited Talks Collecting Coupons is Faster with Friends Structure Structuring Structures Distributed Zero-Knowledge Proofs Contents Keynote Talk Collecting Coupons is Faster with Friends 1 Introduction 1.1 The Formal Problem Setting 1.2 Preliminaries 2 What Happens with No Exchanges? 3 What Happens with Unlimited Exchanges? 4 Minimizing Exchanges for Optimal Collection Rounds 5 Conclusions and Open Problems References Distributed Graph Algorithms Distributed Algorithms for Fractional Coloring 1 Introduction 2 The LOCAL Model of Computation 3 Maximum Degree 4 Coloring the Grid 5 Sparse Graphs References Distributed Graph Problems Through an Automata-Theoretic Lens 1 Introduction 2 Representation of LCLs as Automata 2.1 Formalizing LCLs as Node-Edge-Checkable Problems 2.2 Turning Node-Edge-Checkable Problems into Automata 3 Classification of All LCL Problems on Cycles 3.1 Flexibility and Synchronizing Words 3.2 Results 4 Classification of All LCL Problems on Paths References Near-Optimal Scheduling in the Congested Clique 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 3 Deterministic Scheduling 4 Randomized Scheduling 4.1 Scheduling Through Random Shuffling 4.2 Scheduling Through Random Delays 5 Discussion References Superfast Coloring in CONGEST via Efficient Color Sampling 1 Introduction 1.1 Related Work 2 Intuition and Preliminaries 2.1 Sampling Colors with Shared Randomness 2.2 Tools and Notation 3 Efficient Color Sampling with Representative Sets 4 (1+)-Vertex Coloring 5 Edge Coloring 5.1 (2+)-Edge Coloring 5.2 (2-1)-Edge and (1+)-Edge Coloring 6 Conclusions References Concurrency, Consensus and Dynamics Wait-Free Approximate Agreement on Graphs 1 Introduction 1.1 Graphical Approximate Agreement 1.2 Contributions 2 Related Work 3 Models 4 Impossibility of Asynchronous Wait-Free Cycle Agreement 5 Impossibility of Extension-Based Proofs 6 Impossibility Results via Reductions 7 Upper Bounds for Asynchronous Systems 7.1 A 1-Resilient Algorithm for General Graphs 7.2 A Wait-Free Asynchronous Algorithm for Nicely Bridged Graphs References Fragmented Objects: Boosting Concurrency of Shared Large Objects 1 Introduction 2 Model 3 Fragmented Objects 3.1 Block Object 3.2 Fragmented Object 4 Fragmented Linearizability 5 Implementing Files as Fragmented Coverable Objects 6 Preliminary Evaluation 7 Conclusions References Threshold-Based Network Structural Dynamics 1 Introduction 2 Preliminaries 2.1 (,)-Dynamics - Thresholded Network Dynamics 2.2 Related Work 3 Taking the Minimum 4 (,)-Dynamics with = and a Proper Potential Function on the Degrees 5 (,)-Dynamics Stabilization for Arbitrary Scheduler 6 Turing-Completeness 7 Extensions 8 Conclusion References The Epigenetic Consensus Problem 1 Introduction 2 Model 3 The Epigenetic Consensus Problem 4 Algorithms 4.1 A Naive Algorithm 4.2 The Epigenetic Consensus Algorithm 5 Analysis: Preliminaries 5.1 The Gambler's Ruin Problem with Ties Allowed 5.2 Chernoff Bound 5.3 Additional Assumptions About the Model 6 Analysis: The Probability of Reaching Agreement on the Majority Value 7 Analysis: Computing the Expected Number of Steps 8 Simulations and Analysis of Real Biological Data 9 Discussion References Mobile Robots and Agents New Approximation Algorithms for the Heterogeneous Weighted Delivery Problem 1 Introduction 1.1 Related Work 2 Preliminaries and Notation 3 The Constant Approximation Algorithm for Few Agents 3.1 Auxiliary Graph 3.2 The Case of 1 Active Agent 3.3 How to Deal with More Active Agents 3.4 O(k*)-Aproximation 4 Agents of Two Types 4.1 Reducing 2-VWHTSP to 2-HTSP 4.2 Reducing VWHTSP to 2-VWHTSP 4.3 Reducing the HWD Problem to VWHTSP 5 A Polylogarithmic Approximation for the General Case References Graph Exploration by Energy-Sharing Mobile Agents 1 Introduction 1.1 Model 1.2 Related Work 1.3 Results of the Paper 2 Exploring a Path 3 Exploring a Tree 4 General Graphs 4.1 NP Hardness for 3-Regular Graphs 4.2 An Approximation Algorithm for General Graphs 5 Conclusion References Two-Agent Tree Evacuation 1 Introduction 2 Related Work 3 Preliminaries 4 Global Communication 5 Local Communication 6 Conclusion References Pebble Guided Near Optimal Treasure Hunt in Anonymous Graphs 1 Introduction 1.1 Model and Problem Definition 1.2 Our Results 1.3 Related Work 2 The Treasure Hunt Algorithm 3 Lower Bound 4 Conclusion References Security and Efficiency of Network Communication GMA: A Pareto Optimal Distributed Resource-Allocation Algorithm 1 Introduction 2 Preliminaries: Formalizing Resource Allocation 3 Introducing the GMA Algorithm 3.1 Step 1: Towards No-Over-Allocation 3.2 Step 2: A General Solution for No-Over-Allocation 3.3 Step 3: Monotonic and Pareto-Optimal Allocations 4 Proofs of GMA's Properties 4.1 Proof of No-Over-Allocation ([reqspsnospsoveruse]C1) 4.2 Proof of Optimality ([reqspsoptimality]Opt) 5 GMA Provides Meaningful Allocations 5.1 Simulation Setup 5.2 Results 6 Related Work 7 Discussion and Conclusion References Testing Equality Under the Local Broadcast Model 1 Introduction 2 Notation 3 Problem Statement and Cost Function 4 Lower Bound 5 Simple Protocols 6 Upper Bound 7 Conclusion and Open Problems References A Distributed Computing Perspective of Unconditionally Secure Information Transmission in Russian Cards Problems 1 Introduction 2 Secure Information Transmission 2.1 The Input Complex 2.2 Informative and Safe Protocols 3 Protocol as Vertex Coloring 3.1 Representing Indistinguishability by Johnson Graphs 3.2 Protocol as Vertex Coloring of a Johnson Graph 3.3 General Bounds 4 Minimal Information Transmission 4.1 Minimal Information with 2 Messages 4.2 Reducing Informative to Minimally Informative Protocols 5 The Modular Protocol modn for c+r=1 5.1 modn Is Informative and Coding Theory 5.2 If c+r= 1 Then modn Is Safe 6 Informative Transmission: The General Case c+r1 7 Conclusions A Appendix References Synchronous Concurrent Broadcasts for Intermittent Channels with Bounded Capacities 1 Introduction 2 State of the Art 3 Notation and Model 4 Handling Intermittent Channels 4.1 Algorithm AAFI 4.2 Correctness and Complexity of Algorithm AAFI 5 Multi-source Broadcasts 6 Multi-message Broadcasts 7 Discussion and Conclusion References Network and Graph Structures Fault-Tolerant Distance Labeling for Planar Graphs 1 Introduction 1.1 Related Work 1.2 Our Results 2 Preliminaries 3 Single-Fault Labeling for Reporting Shortest Paths 4 Labeling for Counting Shortest Paths 5 A Lower Bound on Labels for Counting Shortest Paths References Constant Round Distributed Domination on Graph Classes with Bounded Expansion 1 Introduction 2 Preliminaries 3 Covers and Pseudo-covers 4 Finding Dominators 5 Cleaning up 6 The Algorithm 7 Conclusion References Approximate Minimum Directed Spanning Trees Under Congestion 1 Introduction 2 Preliminaries 3 Exact MDST Computation 4 (1+eps)-approximate MDST from SSSP Approximation 4.1 Shortcuts and Dummy Nodes 4.2 Proving Theorem 3 References Distributed Detection of Clusters of Arbitrary Size 1 Introduction 2 Algorithm Description 3 Analysis of the Algorithm 3.1 Analysis of the Averaging Phase 3.2 Estimating the Cluster Size 3.3 Analysis of the Small Detection Phase 3.4 Analysis of the Large Detection Phase 3.5 Proof of the Main Result References Author Index This book constitutes the refereed conference proceedings of the 28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021, held in Wroclaw, Poland, in June 2021.