Distributed Computing: 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings

Front Matter....Pages -
CBTree: A Practical Concurrent Self-Adjusting Search Tree....Pages 1-15
Efficient Fetch-and-Increment....Pages 16-30
Show No Weakness: Sequentially Consistent Specifications of TSO Libraries....Pages 31-45
Collecting Information by Power-Aware Mobile Agents....Pages 46-60
Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology....Pages 61-75
A Generalized Algorithm for Publish/Subscribe Overlay Design and Its Fast Implementation....Pages 76-90
Bounded-Contention Coding for Wireless Networks in the High SNR Regime....Pages 91-105
Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks....Pages 106-120
Distributed Online and Stochastic Queuing on a Multiple Access Channel....Pages 121-135
Fast Distributed Computation in Dynamic Networks via Random Walks....Pages 136-150
Dense Subgraphs on Dynamic Networks....Pages 151-165
Lower Bounds on Information Dissemination in Dynamic Networks....Pages 166-180
No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover....Pages 181-194
“Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting....Pages 195-209
Distributed 2-Approximation Algorithm for the Semi-matching Problem....Pages 210-222
Bounds on Contention Management in Radio Networks....Pages 223-237
Efficient Symmetry Breaking in Multi-Channel Radio Networks....Pages 238-252
On Byzantine Broadcast in Loosely Connected Networks....Pages 253-266
RMR-Efficient Randomized Abortable Mutual Exclusion....Pages 267-281
Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks....Pages 282-296
Pessimistic Software Lock-Elision....Pages 297-311
Asynchronous Pattern Formation by Anonymous Oblivious Mobile Robots....Pages 312-325
How to Gather Asynchronous Oblivious Robots on Anonymous Rings....Pages 326-340
Position Discovery for a System of Bouncing Robots....Pages 341-355
Counting-Based Impossibility Proofs for Renaming and Set Agreement....Pages 356-370
Randomized Distributed Decision....Pages 371-385
The Strong At-Most-Once Problem....Pages 386-400
Brief Announcement: Wait-Free Gathering of Mobile Robots....Pages 401-402
Brief Announcement: Distributed Exclusive and Perpetual Tree Searching....Pages 403-404
Brief Announcement: Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks....Pages 405-406
Brief Announcement: Distributed Algorithms for Maximum Link Scheduling in the Physical Interference Model....Pages 407-408
Brief Announcement: A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model....Pages 409-410
Brief Announcement: Deterministic Protocol for the Membership Problem in Beeping Channels....Pages 411-412
Brief Announcement: Probabilistic Stabilization under Probabilistic Schedulers....Pages 413-414
Brief Announcement: An Analysis Framework for Distributed Hierarchical Directories....Pages 415-416
Brief Announcement: Flooding in Dynamic Graphs with Arbitrary Degree Sequence....Pages 417-418
Brief Announcement: Node Sampling Using Centrifugal Random Walks....Pages 419-420
Brief Announcement: Concurrent Wait-Free Red-Black Trees....Pages 421-422
Brief Announcement: A Contention-Friendly, Non-blocking Skip List....Pages 423-424
Brief Announcement: Consensus and Efficient Passive Replication....Pages 425-426
Brief Announcement: Anonymity, Failures, Detectors and Consensus....Pages 427-428
Brief Announcement: Do VNet Embeddings Leak Information about ISP Topology?....Pages 429-430
Brief Announcement: Efficient Private Distributed Computation on Unbounded Input Streams....Pages 431-432
Brief Announcement: Fast Travellers: Infrastructure-Independent Deadlock Resolution in Resource-restricted Distributed Systems....Pages 433-434
Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems....Pages 435-436
Brief Announcement: Naming and Counting in Anonymous Unknown Dynamic Networks....Pages 437-438
Brief Announcement: SplayNets....Pages 439-440
Brief Announcement: Semantics of Eventually Consistent Replicated Sets....Pages 441-442
Brief Announcement: Decoupled and Consensus-Free Reconfiguration for Fault-Tolerant Storage....Pages 443-444
Brief Announcement: Atomic Consistency and Partition Tolerance in Scalable Key-Value Stores....Pages 445-446
Brief Announcement: Weighted Partial Message Matching for Implicit Multicast Systems....Pages 447-448
Back Matter....Pages -