Structural Information and Communication Complexity

Name: Structural Information and Communication Complexity | 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers

Zvi Lotker Boaz Patt-Shamir(Editor)

Springer (Publisher)

Published on 30. October 2018

XIX, 410 pages

E-Book

PDF with digital watermarking

System requirements

978-3-030-01325-7 (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
Invited Talks (Abstracts)
The Distributed Lovász Local Lemma Problem
On Fair Division for Indivisible Goods
College Admissions in Practice
Taking Turing to the Theater (Abstract of Award Lecture)
Contents
Invited Talks and Brief Announcments
Realizability of Graph Specifications: Characterizations and Algorithms
1 Introduction
2 Specifications and Realizations
2.1 Basic Notions
2.2 Boolean Profiles
2.3 Notions of Vertex Happiness
2.4 Approximate Realizations
3 Three Additional Examples
3.1 The Clique Profile
3.2 The Distance Profile
3.3 Realizations by Vertex-Weighted Graphs
4 Extensions, Generalizations and Future Work
References
A Self-Stabilizing Algorithm for Maximal Matching in Link-Register Model
1 Introduction
2 State of the Art
3 Model
4 Algorithm A1 - Under the Unfair Daemon
5 Algorithm A2 - Under the Atomic Register Model and the Fair Daemon
References
Message-Efficient Self-stabilizing Transformer Using Snap-Stabilizing Quiescence Detection
1 Introduction
2 Quiescence Detection Algorithm Q
References
Constant-Space Self-stabilizing Token Distribution in Trees
1 Introduction
2 Preliminaries
3 Algorithms
3.1 Algorithm Base
3.2 Algorithm SyncTokenDist
3.3 Algorithm PIFTokenDist
References
Distributed Counting Along Lossy Paths Without Feedback
1 Background and Problem Settings
2 Proposed Method
3 Conclusion
References
Make&Activate-Before-Break: Policy Preserving Seamless Routes Replacement in SDN
References
Brief Announcement: Fast Approximate Counting and Leader Election in Populations
1 Introduction
2 Related Work
3 Contribution
4 The Model
5 Fast Counting with a Unique Leader
6 Leader Election with Approximate Knowledge of n
References
One-Max Constant-Probability Networks: Results and Future Work
References
Reaching Distributed Equilibrium with Limited ID Space
1 Introduction
2 Model
2.1 Duplication
2.2 Leader Election
2.3 Knowledge Sharing
3 Solution Basis
3.1 Enhancements
4 Contributions
4.1 Leader Election
4.2 Knowledge Sharing
References
Full Papers
Crash-Tolerant Consensus in Directed Graph Revisited (Extended Abstract)
1 Introduction
2 Preliminaries, Definitions and Notations
2.1 Some Properties of Graphs with f Crash-Tolerant Node Connectivity
3 Multi-valued Consensus Protocol Based on Min-Max Strategy
4 Lower Bounds on Round Complexity of Consensus Protocols Based on Min-Max Strategy
4.1 Impossibility of Consensus in f + 1 Phases (Irrespective of the Number of Rounds)
4.2 Impossibility of Consensus with (f+2)(d+1) - 3 Rounds in Total
4.3 Impossibility of Consensus Based on Min-Max Strategy in 2f + 1 Phases with D Rounds
References
A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(logn) Time
1 Introduction
1.1 Related Work
2 Computational Model and Assumptions
3 Informal Description of Algorithm AHC
4 Formal Description of Algorithm AHC
4.1 Pre-processing
4.2 Phase 0
4.3 Phase 1
4.4 Middle Phases
4.5 Final Phases
5 Analysis of Algorithm AHC
5.1 Phases 0 and 1
5.2 Middle Phases
5.3 The Case c& n/7
5.4 The Case cn/7
5.5 Final Phases
6 Proof of Theorem 1
7 Conclusion
References
Simple and Local Independent Set Approximation
1 Introduction
1.1 Our Contribution
1.2 Related Work
2 Performance of Caro-Wei-Turán Bounds
2.1 Caro-Wei in Bounded-Degree Graphs
2.2 Caro-Wei in Sparse Graphs
2.3 Turán Bound
2.4 Limitations of Distributed Algorithms
3 Approximations for Weighted Graphs
3.1 Modified Algorithm
3.2 Analysis
4 Conclusion
References
On the Strongest Message Adversary for Consensus in Directed Dynamic Networks
1 Introduction
2 Related Work
3 The Model SMP
4 Failure Detectors in Asynchronous Systems
5 Message Adversary Simulations and the Strongest Message Adversary for Consensus
6 Consequences of Our Results
7 Conclusions
References
Symmetric Rendezvous with Advice: How to Rendezvous in a Disk
1 Introduction
1.1 Related Work
1.2 Formal Definitions, Notation and Terminology
1.3 Our Results
2 Rendezvous Algorithms in a Disk
2.1 Some Immediate Benchmark Upper Bounds
2.2 Rendezvous with Minimal Randomness
2.3 Improved Rendezvous with 3-Markovian Trajectories
3 Energy-Efficient Rendezvous
3.1 Energy Analysis of Our Infinite-Step Rendezvous Algorithm
3.2 Expected Rendezvous Time - Energy Tradeoffs
4 Conclusion
References
Two Rounds Are Enough for Reconstructing Any Graph (Class) in the Congested Clique Model
1 Introduction
1.1 Our Results
1.2 Some Remarks
1.3 Techniques
1.4 Related Work
2 Preliminaries
2.1 Some Graph Terminology
2.2 Fingerprints
3 Reconstructing Hereditary Graph Classes
4 Reconstructing Arbitrary Graph Classes
5 Revisiting the One Round Case
6 Discussion
References
Space-Efficient Uniform Deployment of Mobile Agents in Asynchronous Unidirectional Rings
1 Introduction
1.1 Background and Related Works
1.2 Our Contribution
2 Preliminaries
2.1 System Model
2.2 The Uniform Deployment Problem
3 Agents Without Multiplicity Detection
3.1 A Lower Bound of Memory Space per Agent
3.2 An Algorithm with O(k + logN) Memory Space per Agent
4 Agents with Weak Multiplicity Detection
4.1 Selection Phase
4.2 Collection Phase
4.3 Deployment Phase
5 Conclusion
References
Explorable Families of Graphs
1 Introduction
1.1 Our Results
1.2 Related Work
2 Characterization of Explorable Families
3 Universal Exploration Algorithm
4 Conclusion
References
A Characterization of t-Resilient Colorless Task Anonymous Solvability
1 Introduction
2 Preliminaries
3 Atomic Weak Set
3.1 Specification and Algorithm
4 Safe Agreement Object
5 t-Resilient Solvable Colorless Tasks
5.1 Topological Approach
5.2 Simulation-Based Approach
6 Conclusion
References
Deterministic Distributed Ruling Sets of Line Graphs
1 Introduction, Motivation and Related Work
2 Ruling Edge Sets of Simple Graphs
2.1 Proposal Technique for Simple Graphs
2.2 From -Ruling Edge Sets to 2-Ruling Edges Sets
3 Ruling Sets of Bounded Diversity Graphs
References
Broadcast with Energy-Exchanging Mobile Agents Distributed on a Tree
1 Introduction
1.1 Related Work
1.2 Preliminairies
2 Testing Feasibility of Broadcast
3 Constructing Broadcast Schedule
4 Final Remarks
References
A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(logNlog/log2log) Rounds
1 Introduction
2 The MWVC Local Ratio Template
3 A Fast Distributed Implementation
3.1 Proof of Theorem 2
4 An Algorithm Without Knowing
References
Online Service with Delay on a Line
1 Introduction
1.1 Related Problems
1.2 Line Metric: Our Contribution
1.3 Preliminaries
2 The Algorithm
2.1 Algorithm Definition
2.2 Correctness
3 Competitiveness
3.1 Waiting and Service Costs
3.2 Critical Requests and Freshness Property
3.3 Moving Towards and Away from OPT
3.4 Charging Scheme
3.5 The Competitive Ratio
4 Final Remarks
References
Mixed Fault Tolerance in Server Assignment: Combining Reinforcement and Backup
1 Introduction
2 Warm-Up: Mixed Fault-Tolerant Dominating Sets
3 Mixed Fault-Tolerant Centers
3.1 Approximating the f-MFT All-Neighbor Centers Problem
3.2 Approximating the f-MFT Neighbor Centers Problem
4 Mixed Fault-Tolerant Facility Location
References
Communication Complexity in Vertex Partition Whiteboard Model
1 Introduction
1.1 Related Work
1.2 Model Definition and Complexity Classes
1.3 Our Results
1.4 Notations
2 Two-party Communication
3 Non-adaptive n-Party Communication
3.1 Non-adaptive Complexity of HAM
4 Lower Bounds and Hierarchy Result for Adaptive Whiteboard Model
4.1 MATCHING Sensitivity
4.2 Grid Graphs with Gadgets and Shuffles
4.3 Adaptive Complexity of the HAM problem
4.4 Round Hierarchy Theorem by the Analysis of the PATHd Problem
References
Time-Bounded Influence Diffusion with Incentives
1 Introduction
1.1 The Model
1.2 Related Work and Our results
2 A Linear-Time Algorithm for Paths
3 An O(n logn) Algorithm for Complete Graphs
4 A Polynomial-Time Algorithm for Trees
References
Balanced Allocations and Global Clock in Population Protocols: An Accurate Analysis
1 Introduction
2 Problem description
3 Analysis
4 Evaluation of the constants
5 Simulations
6 Conclusion
References
On Knowledge and Communication Complexity in Distributed Systems
1 Introduction
2 Model
2.1 Knowledge and Action Models
3 Communication Complexity Basics
4 Communication Complexity of Action Models
5 Action Models and Protocol Trees
5.1 Action Models of Protocol Trees
5.2 Communication Complexity Lower Bounds
5.3 Application Examples
6 Conclusions
References
Connectivity and Minimum Cut Approximation in the Broadcast Congested Clique
1 Introduction
1.1 CongestedClique: Broadcast and Unicast
1.2 Problems
2 Graph Terminology
3 Spanning Forest in the BroadcastCongestedClique
3.1 Minimum Spanning Forest in the BroadcastCongestedClique
3.2 Connected Components Algorithm
4 Minimum Cut Approximation
4.1 Connectivity Certificates and Karger's Sampling
4.2 Sampling with Small Probabilities
4.3 Algorithm
4.4 Complexity in BroadcastCongestedClique
5 Application to Multi-PassSemi-Streaming Model
6 Conclusions
References
Biased Clocks: A Novel Approach to Improve the Ability To Perform Predicate Detection with O(1) Clocks
1 Introduction
2 System Model
2.1 Naive HLC
3 An Idea to Increase Effectiveness of HLC
4 Algorithm for Biased Clocks (BHLC)
4.1 Extension 1: Multiple Simultaneous Instances of BHLC
4.2 Extension 2: Algorithm BHLCr: Resetting Clocks at Cut-Points
4.3 Extension 3: Algorithm BHLCa: Adjusting Message Rate
5 Comparison of HLC and BHLC in Predicate Detection
5.1 Experimental Setup
5.2 Algorithm for Conjunctive Predicate Detection Using BHLC
5.3 Effectiveness of BHLC Under Different System Parameters and Bias B
5.4 Effectiveness of BHLCr
5.5 Effectiveness of BHLC Under Non-uniform Message Distribution
6 Related Work
7 Conclusion
References
Gathering in the Plane of Location-Aware Robots in the Presence of Spies
1 Introduction
1.1 The Background
1.2 The Model and the Problem
1.3 Our Results
1.4 Related Work
1.5 Notation
2 One Byzantine Robot
3 Bounded Number of Byzantine Robots
4 Arbitrary Number of Byzantine Robots
4.1 Grid Rendezvous
4.2 Shrink-Shortest-Interval
5 Conclusion
References
Formalizing Compute-Aggregate Problems in Cloud Computing
1 Introduction
2 Related Work
3 Motivation and Model Description
3.1 Compute-Aggregate Tasks and ``move to root'' Plans
3.2 Moving Aggregation to Data and Aggregation Functions
4 A Taxonomy of Aggregation Functions
4.1 General Case
4.2 Range-Bounded Aggregation Size Functions
4.3 Specific Aggregation Size Functions
5 Conclusion
References
Priority Evacuation from a Disk Using Mobile Robots
1 Introduction
1.1 Model
1.2 Related Work
1.3 Results of the Paper
2 Notation and Preliminaries
2.1 Notation
2.2 Evacuation Algorithms
3 Upper Bound
4 Lower Bound
5 Conclusions
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Structural Information and Communication Complexity

Description

More details

Other editions

Additional editions

Content

System requirements