This book constitutes the refereed proceedings of the 26th International Symposium on Distributed Computing, DISC 2012, held in Salvador, Brazil, in October 2012.
The 27 revised full papers presented together with 24 brief announcements were carefully reviewed and selected from 119 submissions. The papers are organized in topical sections on shared memory, mobile agents and overlay networks, wireless and multiple access channel networks, dynamic networks, distributed graph algorithms, wireless and loosely connected networks, robots, and lower bounds and separation.
Inhalt
CBTree: A Practical Concurrent Self-Adjusting Search Tree.- Efficient Fetch-and-Increment.- Show No Weakness: Sequentially Consistent Specifications of TSO Libraries.- Collecting Information by Power-Aware Mobile Agents.- Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology.- A Generalized Algorithm for Publish/Subscribe Overlay Design and Its Fast Implementation.- Bounded-Contention Coding for Wireless Networks in the High SNR Regime.- Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks.- Distributed Online and Stochastic Queuing on a Multiple Access Channel.- Fast Distributed Computation in Dynamic Networks via Random Walks.- Dense Subgraphs on Dynamic Networks.- Lower Bounds on Information Dissemination in Dynamic Networks.- No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover.- "Tri, Tri Again": Finding Triangles and Small Subgraphs in a Distributed Setting.- Distributed 2-Approximation Algorithm for the Semi-matching Problem.- Bounds on Contention Management in Radio Networks.- Efficient Symmetry Breaking in Multi-Channel Radio Networks.- On Byzantine Broadcast in Loosely Connected Networks.- RMR-Efficient Randomized Abortable Mutual Exclusion.- Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks.- Pessimistic Software Lock-Elision.- Asynchronous Pattern Formation by Anonymous Oblivious Mobile Robots.-How to Gather Asynchronous Oblivious Robots on Anonymous Rings.- Position Discovery for a System of Bouncing Robots.- Counting-Based Impossibility Proofs for Renaming and Set Agreement.- Randomized Distributed Decision.- The Strong At-Most-Once Problem.- Brief Announcement: Wait-Free Gathering of Mobile Robots.- Brief Announcement: Distributed Exclusive and Perpetual Tree Searching.- Brief Announcement: Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks.- Brief Announcement: Distributed Algorithms for Maximum Link Scheduling in the Physical Interference Model.- Brief Announcement: A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model.- Brief Announcement: Deterministic Protocol for the Membership Problem in Beeping Channels.- Brief Announcement: Probabilistic Stabilization under Probabilistic Schedulers.- Brief Announcement: An Analysis Framework for Distributed Hierarchical Directories.- Brief Announcement: Flooding in Dynamic Graphs with Arbitrary Degree Sequence.- Brief Announcement: Node Sampling Using Centrifugal Random Walks.- Brief Announcement: Concurrent Wait-Free Red-Black Trees.- Brief Announcement: A Contention-Friendly, Non-blocking Skip List.- Brief Announcement: Consensus and Efficient Passive Replication.- Brief Announcement: Anonymity, Failures, Detectors and Consensus.- Brief Announcement: Do VNet Embeddings Leak Information about ISP Topology.- Brief Announcement: Efficient Private Distributed Computation on Unbounded Input Streams.- Brief Announcement: Fast Travellers: Infrastructure-Independent Deadlock Resolution in Resource-restricted Distributed Systems.- Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems.- Brief Announcement: Naming and Counting in Anonymous Unknown Dynamic Networks.- Brief Announcement: SplayNets: Towards Self-Adjusting Distributed Data Structures.- Brief Announcement: Semantics of Eventually Consistent Replicated Sets.- Brief Announcement: Decoupled and Consensus-Free Reconfiguration for Fault-Tolerant Storage.- Brief Announcement: Atomic Consistency and Partition Tolerance in Scalable Key-Value Stores.- Brief Announcement: Weighted Partial Message Matching for Implicit Multicast Systems. Efficient Fetch-and-Increment.- Show No Weakness: Sequentially Consistent Specifications of TSO Libraries.- Collecting Information by Power-Aware Mobile Agents.- Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology.- A Generalized Algorithm for Publish/Subscribe Overlay Design and Its Fast Implementation.- Bounded-Contention Coding for Wireless Networks in the High SNR Regime.- Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks.- Distributed Online and Stochastic Queuing on a Multiple Access Channel.- Fast Distributed Computation in Dynamic Networks via Random Walks.- Dense Subgraphs on Dynamic Networks.- Lower Bounds on Information Dissemination in Dynamic Networks.- No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover.- "Tri, Tri Again": Finding Triangles and Small Subgraphs in a Distributed Setting.- Distributed 2-Approximation Algorithm for the Semi-matching Problem.- Bounds on Contention Management in Radio Networks.- Efficient Symmetry Breaking in Multi-Channel Radio Networks.- On Byzantine Broadcast in Loosely Connected Networks.- RMR-Efficient Randomized Abortable Mutual Exclusion.- Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks.- Pessimistic Software Lock-Elision.- Asynchronous Pattern Formation by Anonymous Oblivious Mobile Robots.-How to Gather Asynchronous Oblivious Robots on Anonymous Rings.- Position Discovery for a System of Bouncing Robots.- Counting-Based Impossibility Proofs for Renaming and Set Agreement.- Randomized Distributed Decision.- The Strong At-Most-Once Problem.- Brief Announcement: Wait-Free Gathering of Mobile Robots.- Brief Announcement: Distributed Exclusive and Perpetual Tree Searching.- Brief Announcement: Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks.- Brief Announcement: Distributed Algorithms for Maximum Link Scheduling in the Physical Interference Model.- Brief Announcement: A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model.- Brief Announcement: Deterministic Protocol for the Membership Problem in Beeping Channels.- Brief Announcement: Probabilistic Stabilization under Probabilistic Schedulers.- Brief Announcement: An Analysis Framework for Distributed Hierarchical Directories.- Brief Announcement: Flooding in Dynamic Graphs with Arbitrary Degree Sequence.- Brief Announcement: Node Sampling Using Centrifugal Random Walks.- Brief Announcement: Concurrent Wait-Free Red-Black Trees.- Brief Announcement: A Contention-Friendly, Non-blocking Skip List.- Brief Announcement: Consensus and Efficient Passive Replication.- Brief Announcement: Anonymity, Failures, Detectors and Consensus.- Brief Announcement: Do VNet Embeddings Leak Information about ISP Topology.- Brief Announcement: Efficient Private Distributed Computation on Unbounded Input Streams.- Brief Announcement: Fast Travellers: Infrastructure-Independent Deadlock Resolution in Resource-restricted Distributed Systems.- Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems.- Brief Announcement: Naming and Counting in Anonymous Unknown Dynamic Networks.- Brief Announcement: SplayNets: Towards Self-Adjusting Distributed Data Structures.- Brief Announcement: Semantics of Eventually Consistent Replicated Sets.- Brief Announcement: Decoupled and Consensus-Free Reconfiguration for Fault-Tolerant Storage.- Brief Announcement: Atomic Consistency and Partition Tolerance in Scalable Key-Value Stores.- Brief Announcement: Weighted Partial Message Matchi…