Structural Information and Communication Complexity

Name: Structural Information and Communication Complexity | 19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30 - July 2, 2012, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30 - July 2, 2012, Revised Selected Papers

Guy Even Magnús M. Halldórsson(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 25. Juni 2012

XIII, 340 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-31104-8 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken