Structural Information and Communication Complexity
19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30 - July 2, 2012, Revised Selected Papers
Published on 25. June 2012
XIII, 340 pages
978-3-642-31104-8 (ISBN)
Description
This book constitutes the refereed proceedings of the 19th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2012, held in Reykjavik, Iceland for 3 days starting June 30, 2012. The 28 revised full papers presented were carefully reviewed and selected from 54 submissions. SIROCCO is devoted to the study of communication and knowledge in distributed systems. Special emphasis is given to innovative approaches and fundamental understanding, in addition to efforts to optimize current designs. The typical areas include distributed computing, communication networks, game theory, parallel computing, social networks, mobile computing (including autonomous robots), peer to peer systems, communication complexity, fault tolerant graph theories, and randomized/probabilistic issues in networks.
More details
Other editions
Additional editions
Guy Even | Magnús M. Halldórsson
Structural Information and Communication Complexity
19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30 - July 2, 2012, Revised Selected Papers
Book
06/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Space Lower Bounds for Low-Stretch Greedy Embeddings
- Introduction
- Hard Crossroads
- A Lower Bound Based on High-Girth Graphs
- A Lower Bound for the Embedding of Flury et al.
- Concluding Remarks
- References
- The Fault Tolerant Capacitated k-Center Problem
- Introduction
- High Level Structure of the Algorithm
- Constant Approximation for the -FT-CKC Problem
- Constant Approximation for the -FT-CCKC Problem
- References
- Notions of Connectivity in Overlay Networks
- Introduction
- Background and Motivation
- The Deep Connectivity Model
- Contribution
- Hardness of Approximation
- Efficient Algorithm for FDC
- Sparsest 2-ERDC Overlay Graphs
- Hardness
- Constructing Sparse 2-ERDC Overlay Graphs
- References
- Changing of the Guards: Strip Cover with Duty Cycling
- Introduction
- Preliminaries
- Strip Cover with Shifts of Size 2
- Round Robin vs. All
- Stretching the Instance
- Perfect Deployment Is the Worst
- Properties of $\gamma*k$
- Strip Cover with Shifts of Size $ k$
- Discussion and Open Problems
- References
- Deterministic Local Algorithms, Unique Identifiers, and Fractional Graph Colouring
- Introduction
- Local Algorithms and Numerical Identifiers
- Contributions
- Comparison with Other Graph Problems
- Fractional Graph Colouring
- Model of Distributed Computing
- Main Results
- Proof of Theorem 1
- Preliminaries
- Communication
- Scheduling Colours
- Coordinates
- First Fragment of the Schedule
- Complete Schedule
- Proof of Theorem 2
- Discussion
- References
- An Algorithm for Online Facility Leasing
- Introduction
- Problem Definition and Notation
- Reduction to a Simplified Model Variant
- Algorithm Description
- Analysis
- Conclusion and Future Work
- References
- Agreement in Directed Dynamic Networks
- Introduction
- Model and Preliminaries
- Required Connectivity Properties
- Solving Consensus by Network Approximation
- Impossibilities and Lower Bounds
- Conclusion
- References
- Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position
- Introduction
- Motivation
- Model and Definitions
- Related Work
- Bounds
- Generalizing One-Dimensional Solutions
- Randomized Point Sets
- Mobility
- Local Algorithm
- Simulation
- Discussion
- References
- Strong Connectivity of Sensor Networks with Double Antennae
- Introduction
- Notation
- Related Work
- Results of the Paper
- Lower Bounds
- Covering Neighbors in MST with Double Antennae
- Connectivity with Optimal Range
- Stretch Factor
- Conclusion
- References
- Distributed Multiple-Message Broadcastin Wireless Ad-Hoc Network sunder the SINR Model
- Introduction
- Related Work
- Network Model and Problem Definitions
- Algorithm
- Algorithm Description
- Analysis
- Lower Bound
- Conclusion
- References
- Wireless Network Stability in the SINR Model
- Introduction
- Model and Preliminaries
- Results and Related Work
- Main Algorithm
- The Scheduling Algorithm
- Implications for the Power Control Problem
- Distributed Implementation
- Extensions and Simulations
- References
- What Can Be Computed without Communications?
- Introduction
- Context and Objective
- Our Results
- Equivalence Classes of Games
- On the Power of Quantum Correlations
- Open Problem
- References
- On Bidimensional Congestion Games
- Introduction
- Model, Definitions and Numerical Lemmas
- Bounds for the Price of Anarchy
- Bounds for the Price of Stability
- References
- Mobile Network Creation Games
- Introduction
- Model and Preliminaries
- Nash Equilibria: Existence and Convergence
- Price of Anarchy
- Extensions and Conclusions
- References
- Homonyms with Forgeable Identifiers
- Introduction
- Model and Definitions
- Impossibility Result
- Authenticated Broadcast
- Byzantine Agreement Algorithms
- Authentication
- Related Works and Perspectives
- References
- Asynchrony and Collusion in the N-party BAR Transfer Problem
- Introduction
- System Model
- NBART Problem
- Asynchronous NBART
- Overview of the Algorithm
- Algorithm in Depth
- Game Theoretic Analysis
- Definitions
- Expected Utility and Solution Concept
- Tolerance to Collusion
- References
- Early Deciding Synchronous Renaming in O(log f) Rounds or Less
- Introduction
- Model and Problem Statement
- Related Work
- A Tight Renaming Algorithm
- A Loose Renaming Algorithm with Improved Round Complexity
- Discussion
- References
- On Snapshots and Stable Properties Detection in Anonymous Fully Distributed Systems
- Introduction
- The Chandy-Lamport Snapshot Algorithm
- Termination Detection of the Chandy-Lamport Snapshot Algorithm
- An Algorithm to Detect Termination of the Local Snapshots Computation
- Two Applications: ``Checkpoint and Rollback Recovery'' and ``Termination Detection''
- Coverings, Stable Properties and Weak Snapshots
- References
- Self-stabilizing (k,r)-Clustering in Clock Rate-Limited Systems
- Introduction
- System Settings
- Self-stabilizing Algorithm for (k,r)-Clustering
- Correctness
- Basic Properties
- Getting Enough Cluster Heads
- Convergence to a Local Minimum
- Discussion
- Conclusions
- References
- Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors
- Introduction
- Base Definitions
- Strongly Correct Processes (wrt the IIS Model)
- From IISn[C*] to ARWn[C]
- Description of the Simulation
- From Strongly Correct Simulators to Correct Simulated Processes
- From ARWn[C] to IISn[C*]
- Description of the Simulation
- Instantiating the Simulation
- From Wait-Freedom to t-Resilience
- References
- Improved Approximation for Orienting Mixed Graphs
- Introduction
- Previous Work
- Our Results
- From Local to Global Orientations
- Improved Approximation for the General Case
- Other Orientation Variants
- Orientation with Fixed Paths
- Orientation in Grid Networks
- References
- Analysis of Random Walks Using Tabu Lists
- Introduction
- Tabu Random Walks and Update Rules
- Tabu Random Walks
- Update Rules
- Examples of Update Rules
- Finite Mean Hitting Times
- Optimal Update Rule for m-Free Graphs
- Impact of the Length of the Update Rules
- Conclusion and Perspectives
- References
- Online Graph Exploration with Advice
- Introduction
- Lower Bounds
- Advice Size for Optimal Solution
- Lower Bound for the Case of No Advice
- Upper Bounds
- Conclusion
- References
- Asynchronous Exploration of an Unknown Anonymous Dangerous Graph with O(1)Pebbles
- Introduction
- Definitions and Basic Constraints
- Impossibilities and Lower Bounds
- Possibility and Upper Bounds
- Communication and Coordination Using Tokens
- Black Hole Search
- Correctness and Complexity
- References
- Time of Anonymous Rendezvous in Trees: Determinism vs. Randomization
- Introduction
- Framework and Preliminaries
- Time of Deterministic Rendezvous
- Time of Randomized Rendezvous
- References
- Randomized Rendezvous of Mobile Agents in Anonymous Unidirectional Ring Networks
- Introduction
- Preliminaries
- Impossibility Results
- Impossibility of Rendezvous with Detection
- Impossibility of Rendezvous without Detection
- A Randomized Algorithm for Rendezvous without Detection
- Conclusion
- References
- Getting Close without Touching
- Introduction
- The Model
- Notation
- The Near-Gathering Problem and Its Solution
- Correctness
- Preliminary Definitions and Observations
- Preservation of Mutual Awareness
- Collision Avoidance
- Termination
- On the Knowledge of n
- Conclusions
- References
- Gathering of Robots on Anonymous Gridswi thout Multiplicity Detection
- Introduction
- Definitions and Notation
- Gathering Algorithms
- Oddodd Grids
- Oddeven Grids
- Eveneven Grids
- Conclusion
- References
- Author Index
