Structural Information and Communication Complexity: 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14–16, 2015, Post-Proceedings

Front Matter....Pages -
Communication Patterns and Input Patterns in Distributed Computing....Pages 1-15
Clock Synchronization and Estimation in Highly Dynamic Networks: An Information Theoretic Approach....Pages 16-30
Node Labels in Local Decision....Pages 31-45
Exact Bounds for Distributed Graph Colouring....Pages 46-60
Essential Traffic Parameters for Shared Memory Switch Performance....Pages 61-75
Scheduling Multipacket Frames with Frame Deadlines....Pages 76-90
A Randomized Algorithm for Online Scheduling with Interval Conflicts....Pages 91-103
Online Admission Control and Embedding of Service Chains....Pages 104-118
Optimizing Spread of Influence in Social Networks via Partial Incentives....Pages 119-134
Approximation Algorithms for Multi-budgeted Network Design Problems....Pages 135-148
Simple Distributed Δ + 1 Coloring in the SINR Model....Pages 149-163
Nearly Optimal Local Broadcasting in the SINR Model with Feedback....Pages 164-178
Byzantine Gathering in Networks....Pages 179-193
Signature-Free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n2) Messages, and Constant Time....Pages 194-208
A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation....Pages 209-223
Path-Fault-Tolerant Approximate Shortest-Path Trees....Pages 224-238
A Faster Computation of All the Best Swap Edges of a Tree Spanner....Pages 239-253
Randomized OBDD-Based Graph Algorithms....Pages 254-269
On Fast and Robust Information Spreading in the Vertex-Congest Model....Pages 270-284
Information Spreading by Mobile Particles on a Line....Pages 285-298
On Space and Time Complexity of Loosely-Stabilizing Leader Election....Pages 299-312
Wait-Free Gathering Without Chirality....Pages 313-327
Treasure Hunt with Advice....Pages 328-341
Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond....Pages 342-356
Collaborative Exploration by Energy-Constrained Mobile Robots....Pages 357-369
Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model....Pages 370-384
A Separation of n-consensus and (n + 1)-consensus Based on Process Scheduling....Pages 385-398
Under the Hood of the Bakery Algorithm: Mutual Exclusion as a Matter of Priority....Pages 399-413
The Computability of Relaxed Data Structures: Queues and Stacks as Examples....Pages 414-428
Comparison-Based Interactive Collaborative Filtering....Pages 429-443
Coalescing Walks on Rotor-Router Systems....Pages 444-458
Secure Multi-party Shuffling....Pages 459-473
Back Matter....Pages -