Structural Information and Communication Complexity

Name: Structural Information and Communication Complexity | 31st International Colloquium, SIROCCO 2024, Vietri sul Mare, Italy, May 27-29, 2024, Proceedings
Brand: Springer
Price: 139.09 EUR
Availability: OnlineOnly

31st International Colloquium, SIROCCO 2024, Vietri sul Mare, Italy, May 27-29, 2024, Proceedings

Yuval Emek(Herausgeber*in)

Springer (Verlag)

Erschienen am 22. Mai 2024

XIII, 522 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-031-60603-8 (ISBN)

139,09 €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
SIROCCO Prize for Innovation in Distributed Computing (Invited Talk)
Contents
Invited Paper
History Trees and Their Applications
1 Introduction
2 Basic Structure and Algorithms
2.1 History Trees and Construction of a View
2.2 Related Structures for Static Networks
2.3 Basic Applications to Dynamic Networks
3 Variations and Extensions
3.1 Leader Election
3.2 Terminating Counting
3.3 Directed Networks
3.4 Disconnected Networks
3.5 Semi-Synchronous Networks
3.6 Asynchronous Networks
3.7 Port Awareness
3.8 Varying Inputs
3.9 Self-stabilization
3.10 Finite-State Stabilization
3.11 Memoryless Computation
3.12 Congested Networks
References
Regular Papers
An Analysis of Avalanche Consensus
1 Introduction
2 Preliminaries
2.1 Model
2.2 The Snow Family
3 Dynamics of Slush
3.1 Expected Rate of Progress of Slush
3.2 Mapping out the Dependency of on and
4 Bounding the Time to Consensus for Slush
4.1 Lower Bound
4.2 Upper Bound
5 Dynamics of Snowflake and Snowball
6 Security of Snowflake and Snowball
7 Reconciling Security and Fast Consensus
8 Conclusion
References
Awake Complexity of Distributed Minimum Spanning Tree
1 Introduction
1.1 Distributed Computing Model and Complexity Measures
1.2 Our Contributions and Techniques
1.3 Related Work and Comparison
2 Lower Bounds
2.1 Unconditional Lower Bound on Awake Complexity of MST
2.2 Lower Bound on the Product of Awake and Round Complexity
3 MST Algorithms with Optimal Awake Complexity
3.1 Main Ideas and Useful Procedures
3.2 Awake-Optimal Randomized Algorithm
References
All You Need are Random Walks: Fast and Simple Distributed Conductance Testing
1 Introduction
1.1 Technical Overview
2 Preliminaries
3 A Distributed Algorithm for Testing Conductance
3.1 Analysis of the Algorithm
References
k-Center Clustering in Distributed Models
1 Introduction
1.1 Distributed k-Center
1.2 Our Results and Techniques
2 Preliminaries
2.1 The k-Center Problem
2.2 Computational Models
2.3 Communication Complexity
2.4 Related Work
3 The k-Center Problem in the local Model
4 A 2-Approximation in the congest Model
5 A Lower Bound in the congest Model
5.1 A Lower Bound for the 1-Center Problem
5.2 Extending the Lower Bound to the k-Center Problem
6 A 2-Approximation in the clique Model
References
Optimal Memory Requirement for Self-stabilizing Token Circulation
1 Introduction
1.1 Contributions
1.2 Outline of the Paper
2 Model and Definitions
2.1 Algorithm Syntax and Semantics
2.2 Schedulers
2.3 Self-stabilization
2.4 DODAGs
2.5 Bit-by-Bit Communication of Identifier
3 Algorithm
3.1 Variables
3.2 Rules
4 Correctness
5 Conclusion
References
Stand-Up Indulgent Gathering on Rings
1 Introduction
2 Model
3 Stand Up Indulgent Rendezvous
4 Stand-Up Indulgent Gathering
4.1 Overview of the Proof of Correctness
4.2 Geometric Results
4.3 From NE (k), k&4, to L3
4.4 From NE (4) to L3
4.5 From L3 to the Gathered Configuration
5 Concluding Remarks
References
In Search of the Lost Tree
1 Introduction
1.1 Contributions
1.2 Organization of the Paper
2 Definitions
2.1 Temporal Spanning Trees
2.2 Bidirectional Temporal Spanners
2.3 Simple, Strict, Proper, Happy: Generality of Results
3 Temporal Spanning Trees
3.1 NP-Completeness
3.2 Tractability in Simple Temporal Graphs
4 Bi-Spanners of Unrestricted Size
4.1 High-Level Description
4.2 The Algorithm
5 Bi-Spanners of Size k
5.1 Further Restrictions (Open Questions)
6 Conclusion
References
Near-Optimal Fault Tolerance for Efficient Batch Matrix Multiplication via an Additive Combinatorics Lens
1 Introduction
1.1 Our Contribution
1.2 Related Work
1.3 Roadmap
2 Notation
3 An (n) Lower Bound on the Recovery Threshold
4 An neO(logn) Recovery Threshold Upper Bound
5 The Computational Efficiency of Rook Codes
5.1 Bounding Encoding Time of Our Rook Codes Construction
6 Discussion
References
Deterministic Leader Election for Stationary Programmable Matter with Common Direction
1 Introduction
1.1 Related Work and Motivation
1.2 Our Contributions
2 Model and Preliminaries
3 Explicit Termination Impossibility
4 Message Forwarding on Boundaries
5 Algorithm Description
5.1 Grey Leader Election
5.2 Tree Construction
5.3 Component Competition
6 Conclusion and Open Problems
References
Mutual Visibility in Hypercube-Like Graphs
1 Introduction
2 Notation and Preliminaries
3 Hypercube
3.1 An Upper Bound for (Qd)
3.2 Lower Bound and an Approximation Algorithm
4 Cube-Connected Cycles
4.1 Total Mutual Visibility
5 Butterfly
5.1 Total Mutual-Visibility
6 Conclusions
References
Non-negotiating Distributed Computing
1 Introduction
1.1 Context and Objective
1.2 Non-negotiating Distributed Computation
1.3 Results
2 Uniform Non-negotiated Approximate Agreement
2.1 A Uniform Algorithm for 2-Processes Approximate Agreement
2.2 Inherent Slowness of Uniform Non-negotiating Computing
3 Non-negotiated Multidimensional Approximate Agreement
3.1 No Uniform Algorithm Can Solve Multidimensional Approximate Agreement
3.2 Not Uniform General Multidimensional Approximate Agreement Algorithm
4 Universality of Multidimensional Approximate Agreement
5 Conclusion
References
Better Sooner Rather Than Later
1 Introduction
1.1 Two Fundamental Problems in Distributed Computing
1.2 Contention-Related Crash Failures
1.3 Computational Model
1.4 Contributions and Related Work
2 The Consensus Algorithm
2.1 Shared and Local Objects Used by the Algorithm
2.2 An Informal Description of the Algorithm
2.3 A Formal Description and Correctness Proof
3 Optimality of the Algorithm
4 Discussion
References
Highly-Efficient Persistent FIFO Queues
1 Introduction
2 Preliminaries
3 LCRQ: A Brief Description
4 Persistent FIFO Queue Algorithm
4.1 Persistent IQ
4.2 Persistent CRQ
4.3 Persistent LCRQ
5 Performance Evaluation
References
Locally Balanced Allocations Under Strong Byzantine Influence
1 Introduction
1.1 Related Work
2 Problem Specification and Our Results
2.1 Problem Description
2.2 Our Results
3 Probabilistic Analysis of Power of Two Choices Under Byzantine Faults-Proof of Theorem 2
3.1 Overview of the Analysis
3.2 Worst-Case Adversary
3.3 Step 1: Initial Estimate of P(Ei+1 | Ei)
3.4 Step 2: Analysis of Event Ei for i Corresponding to pi 2 lnnm
3.5 Step 3: Finding i* - The Minimum i Satisfying p+i & 2 lnnm
3.6 Step 4: Finalizing the Analysis - Beyond Threshold Parameter +i*
4 Case m e n - Setting Up Initial Value of
5 Case m& 32 nlogn - Proof of Theorem 1
6 Discussion and Open Problems
References
Distributed Fractional Local Ratio and Independent Set Approximation
1 Introduction
2 Preliminaries
3 Distributed Fractional Local Ratio
3.1 Centralized Algorithm
3.2 Distributed Algorithm
4 Improving the Approximation Ratio
4.1 Centralized Algorithm
4.2 Distributed Algorithm
5 8/5-Approximation Algorithm for Maximum Degree 3
References
Towards Singular Optimality in the Presence of Local Initial Knowledge
1 Introduction
1.1 KT- Congest Model
1.2 Challenges, Approach, and Techniques
1.3 Related Work
1.4 Notation and Definitions
2 Fast Subroutines in the KT-2 Congest Model
3 Distributed Danner Construction in the KT-2 Congest Model
3.1 Cluster Growing: Phase 1
3.2 Cluster Growing: Phase 2
3.3 Cluster Merging
4 Conclusion
References
Efficient Wait-Free Linearizable Implementations of Approximate Bounded Counters Using Read-Write Registers
1 Introduction
2 Preliminaries
3 Algorithm for k 2n
3.1 Algorithm Description
3.2 Proof of Linearizability
3.3 Complexity Analysis
4 Algorithm for k &1
4.1 Algorithm Description
4.2 Proof of Linearizability
4.3 Complexity Analysis
5 Algorithm for k 2
5.1 Algorithm Description
5.2 Proof of Linearizability
5.3 Complexity Analysis
6 Conclusion
References
On Distributed Computation of the Minimum Triangle Edge Transversal
1 Introduction
1.1 Our Contribution
1.2 Technical Overview of the CONGEST Lower Bound
1.3 Related Work
2 Hardness of Exact Computation of MTET
2.1 Preliminaries
2.2 A Linear Lower Bound in the LOCAL Model
2.3 A Near-Quadratic Lower Bound in the CONGEST Model
3 A (1+)-Approximation for MTET in the LOCAL Model
4 Faster Approximations for the Minimum Triangle Edge Transversal
References
Stability of P2P Networks Under Greedy Peering
1 Introduction
1.1 Our Results
2 Related Work
3 Model
4 Theoretical Analyses
4.1 An Idealized Game-Theoretic Model
4.2 Single-Exploratory-Greedy
4.3 Reachable Stability
5 Simulations
5.1 Effect of In-Degree Caps
5.2 Network Size
5.3 K-Worst Edges
6 Discussion
References
Universal Coating by 3D Hybrid Programmable Matter
1 Introduction
1.1 Our Results
1.2 Related Work
2 Model and Problem Statement
2.1 Underlying Graph
2.2 Agent Model
2.3 Problem Statement
3 The Coating Algorithm
3.1 High-Level Description and Preliminaries
3.2 Algorithm Details and Pseudocode
3.3 Analysis
3.4 Runtime Analysis
4 Coating in the 3D Hybrid Model
4.1 Emulation of Coatable Surface Graphs
5 Future Work
References
Distributed Binary Labeling Problems in High-Degree Graphs
1 Introduction
1.1 Broader Context
1.2 Binary Labeling Problems
1.3 Overview of Contributions and New Ideas
1.4 Contributions in More Detail
1.5 Key Building Block: A New Rake-and-Compress Variant
1.6 Questions for Future Work
1.7 Roadmap
1.8 Model
2 Logarithmic Lower Bounds
2.1 A General Lower Bound
2.2 Definitions and Problem Transformations
2.3 Problem Reductions
3 Logarithmic Upper Bounds
3.1 Center-Good Problems
3.2 Aggressive Rake-and-Compress
4 Classification of Logarithmic Problems
References
Computing Replacement Paths in the CONGEST Model
1 Introduction
1.1 Preliminaries
1.2 Our Results
1.3 Prior Work
1.4 Our Techniques
2 Directed Weighted Replacement Paths
2.1 Directed Weighted RPaths Lower Bound
2.2 Directed Weighted RPaths Algorithm
3 Directed Unweighted Replacement Paths
3.1 Directed Unweighted RPaths Lower Bound
3.2 Directed Unweighted RPaths Algorithm
3.3 Approximate Directed Weighted RPaths Algorithm
4 Further Research
References
Reaching Agreement Among k out of n Processes
1 Introduction
1.1 The (n, k)-Partial Agreement Problem
1.2 The (n, k, l)-Partial Set Agreement Problem
1.3 Motivation
1.4 Models of Computation
1.5 Known Results
1.6 Content of the Article
2 Asynchronous Partial Agreement: The Binary Case with Implications
3 Asynchronous Partial Agreement: The Multi-valued Case
4 Synchronous Partial Agreement
5 Partial Agreement Using Strong Shared Objects
6 Related Work
7 Discussion
References
On the Bit Complexity of Iterated Memory
1 Introduction
2 Related Work
3 Preliminaries
4 System Model
5 Equivalence Between Bounded and Full-Information IIS
6 f-Vector Analysis for Distinguishability and Iterated Chromatic Subdivision
6.1 Definitions
6.2 f-Vector and the Indistinguishability Graphs
6.3 f-Vector of the Standard Chromatic Subdivision
7 Asymptotic Analysis of f-Vector of the Iterated Chromatic Subdivision
8 Main Results and Ramifications
References
Brief Announcements
Sharding in Permissionless Systems in Presence of an Adaptive Adversary
1 Introduction
2 Model of the System
3 Handling Multiple Chains
3.1 Assigning Validators to Chains
3.2 Creation of the Blocks of a Chain
3.3 Cross Chain Transactions
4 Dedicated Routing Protocol
5 Related Work
6 Conclusion
References
Online Drone Scheduling for Last-Mile Delivery
1 Introduction
2 Drone Scheduling Through Bin Packing with Conflicts
2.1 Computing idNumber
2.2 Computing binNumber
3 Online Variable-Size Drone Scheduling
4 Conclusion
References
Efficient Self-stabilizing Simulations of Energy-Restricted Mobile Robots by Asynchronous Luminous Mobile Robots
1 Introduction
1.1 Background and Motivation
1.2 Contributions
2 Simulation of Rsynch on LUMI
2.1 Simulation of Rsynch with Any Number of Robots
2.2 Optimal Simulation of Rsynch by Asynch with Two Robots
References
Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed Systems
References
On the Existence of Consensus Converging Organized Groups in Large Social Networks
1 Introduction
2 Graph Connectivity and Fast Diffusion of Information
3 Emergence of Organized Structures in Social Networks
4 Conclusions
References
Multi-agent Online Graph Exploration on Cycles and Tadpole Graphs
1 Introduction
2 Cycles
3 Tadpole Graphs
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken