Structural Information and Communication Complexity
18th International Colloquium, SIROCCO 2011, Gdansk, Poland, June 26-29, 2011
Published on 24. June 2011
XI, 317 pages
978-3-642-22212-2 (ISBN)
Description
This book constitutes the refereed proceedings of the 18th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2011, held in Gdansk, Poland, in June 2011. The 24 revised full papers presented together with 1 survey lecture and 2 invited talks were carefully reviewed and selected from 57 submissions. The papers are organized in topical section on fault tolerance, routing, mobile agents, mobile robots, probabilistic methods, distributed algorithms on graphs, and ad-hoc networks.
More details
Other editions
Additional editions
Adrian Kosowski | Masafumi Yamashita
Structural Information and Communication Complexity
18th International Colloquium, SIROCCO 2011, Gdansk, Poland, June 26-29, 2011
Book
06/2011
1st Edition
Springer
€53.49
Shipment within 5-7 days
Content
- Title
- Preface
- Conference Organization
- Table of Contents
- Invited Talks
- Random Walks, Interacting Particles, Dynamic Networks: Randomness Can Be Helpful
- Introduction
- Terminology
- Speeding Up Random Walks
- Multiple and Interacting Particles
- Coalescing Particle Systems
- Searching Dynamic Graphs
- References
- SINR Maps: Properties and Applications
- References
- Survey Talk
- A Survey on Some Recent Advances in Shared Memory Models
- Introduction
- What Is a Task?
- Base Shared Memory Model
- The Iterated Write-Snapshot Model
- The Iterated Write-Snapshot Model
- A Mathematical View
- A Recursive Write-Snapshot Algorithm
- Enriching a System with a Failure Detector
- From the Wait-Free Model to the Adversary Model
- Adversary Models vs. Wait-Free Model: The BG Simulation
- Conclusion
- References
- Fault Tolerance
- Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults
- Introduction
- Definitions and Notation
- TheProblems
- Broadcastability
- Proof of Main Theorem
- Solvability of Consensus vs. Broadcast
- Conclusion
- References
- Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing (Extended Abstract)
- Introduction
- SystemModels
- Failures and Admissibility
- State Transition Traces
- Transformation Real-Time to Classic Model
- Transformation Classic to Real-Time Model
- Example: The Byzantine Generals
- Conclusions
- References
- Self-stabilizing Hierarchical Construction of Bounded Size Clusters
- Introduction
- Preliminaries
- Problem Specification
- Basic Idea of Our Solution
- Cluster Construction
- Construction of the Cluster Tree
- Conclusion
- References
- The Universe of Symmetry Breaking Tasks
- Introduction
- Computation Model
- Decision Tasks
- The Family of Generalized Symmetry Breaking (GSB) Tasks
- Definition and Basic Properties
- Instances of Generalized Symmetry Breaking Tasks
- The Structure of Symmetric GSB Tasks
- The Structural Results
- Complexity and Computability
- Hardest GSB Tasks: Universality of the "426830A n,n,1,1"526930B -GSB Task
- Easiest GSB Tasks: Solvability of GSB Tasks with No Communication
- Hierarchy Results, GSB Tasks of Intermediate Difficulty
- From a Slot Task to a Renaming Task
- To Conclude: A Few GSB-Related Open Problems
- References
- Routing
- Determining the Conditional Diagnosability of k-Ary n-Cubes Under the MM* Model
- Introduction
- Preliminaries
- Properties of k-Ary n-Cubes
- MainResults
- Concluding Remarks
- References
- Medium Access Control for Adversarial Channels with Jamming
- Introduction
- Preliminaries
- Properties of k-Ary n-Cubes
- Main Results
- Concluding Remarks
- References
- Full Reversal Routing as a Linear Dynamical System
- Introduction
- Preliminaries
- Notation and Definitions
- The Full Reversal Algorithm
- Complexity Measures
- Full Reversal as a Linear Dynamical System
- Interleaving of FR Steps
- Work Vector of Greedy FR Executions
- Dynamical Systems and Graph Properties
- Work Complexity
- Time Complexity
- Applications
- Time Complexity Bounds on Trees
- Generalization
- Discussion
- References
- Partial is Full
- Introduction
- Preliminaries
- The LR Algorithm
- Complexity Measures
- The FR Executions
- Reduction to FR Executions
- The Graph Transformation
- Dynamics in LR Executions
- The Routing Failure
- Application
- The Acyclicity Issue
- Exact Complexity of the LR Algorithm
- Conclusions
- References
- Mobile Agents/Robots (I)
- Convergence with Limited Visibility by Asynchronous Mobile Robots
- Introduction
- Model and Definitions
- Connectivity Preservation with 1-Bounded Asynchrony
- Connectivity Invariant
- Invariant Preservation
- Move Toward
- Move Around
- Algorithm
- Algorithm with Unlimited Visibility
- Convergence
- Conclusions and Open Questions
- References
- Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally
- Introduction
- Problem Description, Model and Notation
- The -Bounded Go-To-The-Middle Strategy
- The Worst-Case Number of Rounds
- Maximum Distance Traveled by a Robot
- The Continuous Go-To-The-Middle Strategy
- Conclusion and Outlook
- References
- Asynchronous Mobile Robot Gathering from Symmetric Configurations without Global Multiplicity Detection
- Introduction
- Preliminaries
- Algorithm
- First Phase: An Algorithm to Construct a Single 1.Block
- Second Phase: An Algorithm to Achieve the Gathering
- Concluding Remarks
- References
- Mobile Agents/Robots (II)
- Gathering Asynchronous Oblivious Agents with Local Vision in Regular Bipartite Graphs
- Introduction
- Our Results
- Discussion of Assumptions
- Related Work
- Terminology and Preliminaries
- The Impossibility Result
- The Algorithm
- References
- Gathering of Six Robots on Anonymous Symmetric Rings
- Introduction
- Related Work and Our Results
- Definitions and Notation
- Resolution Algorithm
- General Case
- Multiplicities and Seven Nodes Case
- Correctness for the General Algorithm
- Conclusion
- References
- Tight Bounds for Scattered Black Hole Search in a Ring
- Introduction
- Our Model
- Impossibility Results
- A BHS Scheme with Movable Tokens
- BHS Schemes with Unmovable Tokens
- Oriented Rings
- Unoriented Rings
- Conclusions
- References
- Improving the Optimal Bounds for Black Hole Search in Rings
- Introduction
- The Problem
- Main Contributions
- Related Work
- Definitions and Basic Techniques
- Exact Bounds on Cost of Black Hole Search
- Improved Lower Bound
- Matching Upper Bound
- Optimizing Also Ideal Time
- References
- Probabilistic Methods
- The Cover Times of Random Walks on Hypergraphs
- Introduction
- Proof of Theorem 1
- Proof of Theorem 2: Preliminaries
- Random Walk Background
- Tree-Like Vertices
- Construction of an Equivalent (Contracted) Graph
- Conditions and Parameters for Lemma 2
- Proof of Theorem 2: Estimate the Cover Time C(H)
- Upper Bound on the Cover Time C(H)
- Lower Bound on the Cover Time C(H)
- Proof of Theorem 2: Estimate I(H) and CE(H)
- References
- Routing in Carrier-Based Mobile Networks
- Introduction
- Model
- Optimal Algorithm
- Competitive Analysis
- Conclusions and Future Work
- References
- On the Performance of a Retransmission-Based Synchronizer
- Introduction
- Retransmitting under Probabilistic Message Loss
- Calculating the Expected Round Duration
- Round Durations as a Markov Chain
- Using (r) to Compute
- Results
- Rate of Convergence
- Simulations
- Related Work
- References
- Distributed Algorithms on Graphs
- Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth
- Introduction
- Model and Definitions
- Related Work
- Deterministic Coloring
- Coloring Depending on the Chromatic Number
- Conclusion
- References
- Multiparty Equality Function Computation in Networks with Point-to-Point Links
- Introduction
- Related Work
- Models and Problem Definition
- Communication Model
- Protocol
- Problem Definitions
- Upper Bound of the Complexity
- Equivalent MEQ-AD Protocols
- MEQ-AD(3,6)
- Edge Coloring Representation of MEQ-AD(3,K)
- MEQ-AD(3,2k)
- About MEQ-CD
- MEQ Problem with Larger n
- Conclusion
- References
- Network Verification via Routing Table Queries
- Introduction
- Basic Definitions
- The Routing-Table Query Model
- Lower Bounds on the Size of Feasible Solutions
- Verifying Graphs of Diameter 2
- Optimal Algorithms for Classical Topologies
- Paths
- Trees
- Conclusions
- References
- Social Context Congestion Games
- Introduction
- Model and Definitions
- Results for the Class SCSG(G,f)
- Results for the Class SCLCG(G,f)
- Results for the Class SCSCG(G,f)
- Conclusions
- References
- Ad-hoc Networks
- Network Synchronization and Localization Based on Stolen Signals
- Introduction
- Related Work
- Estimating Distances
- Centralized Localization and Synchronization
- Outlook
- References
- Optimal Time Data Gathering in Wireless Networks with Omni-Directional Antennas
- Introduction
- The Model
- Our Results and Related Work
- Scheduling in Trees
- Trees with Non-zero Node Weights
- Trees with General Weight Distribution
- General Topologies
- The Approximation Algorithm
- Complexity Results
- References
- Author Index
