Structural Information and Communication Complexity

Name: Structural Information and Communication Complexity | 18th International Colloquium, SIROCCO 2011, Gdansk, Poland, June 26-29, 2011
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

18th International Colloquium, SIROCCO 2011, Gdansk, Poland, June 26-29, 2011

Adrian Kosowski Masafumi Yamashita(Herausgeber*in)

Springer (Verlag)

Erschienen am 24. Juni 2011

XI, 317 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22212-2 (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
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

Systemvoraussetzungen

Als PDF speichern Als Link merken