Papers Accepted to PODC 2010

Regular Papers

Transactional Predication: High-Performance Concurrent Sets and Maps for STM
Bronson, Casper, Chafi, Olukotun

On Maintaining Multiple Versions in STM
Perelman, Fan, Keidar

The Multiplicative Power of Consensus Numbers
Imbs, Raynal

The k-Bakery: Local-spin k-Exclusion Using Non-atomic Reads and Writes

Group Mutual Exclusion in O(log n) RMR
Bhatt, Huang

On Asymmetric Progress Conditions
Imbs, Raynal, Taubenfeld

Verifying Linearizability with Hindsight
O'Hearn, Rinetzky, T. Vechev, Yahav, Yorsh

Eventually Linearizable Shared Objects
Serafini, Dobre, Majuntke, Bokor, Suri

The Topology of Shared-Memory Adversaries
Herlihy, Rajsbaum

Non-blocking Binary Search Trees
Ellen, Fatourou, Ruppert, van Breugel

Adaptive Randomized Mutual Exclusion
Hendler, Woelfel

Distributed Data Classification in Sensor Networks
Eyal, Keidar, Rom

Partial Information Spreading with Application to Distributed Maximum Coverage
Censor, Hillel, Shachnai

Adaptive Runtime Anomaly Prediction for Dynamic Hosting Infrastructures
Tan, Gu, Wang

Efficient Threshold Detection in a Distributed Environment
Emek, Korman

Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
Abraham, Chechik, Gavoille, Peleg

Efficient Distributed Random Walks with Applications
Das Sarma, Nanongkai, Pandurangan, Tetali

Almost-Asynchronous MPC with Faulty Minority
Beerliova-Trubiniova, Hirt, Buus Nielsen

Optimally Hybrid-Secure MPC
Lucas, Raub, Maurer

Meeting the Deadline: On the Complexity of Fault-Tolerant Continuous Gossip
Georgiou, Gilbert, Kowalski

A New Technique For Distributed Symmetry Breaking
Schneider, Wattenhofer

On the Computational Power of Oblivious Robots: Forming a Series of Geometric Patterns
Das, Flocchini, Santoro, Yamashita

Finding Mobile Data under Delay Constraints with Searching Costs
Bar-Noy, Cheilaris, Feng, Levin

On Utilizing Speed in Networks of Mobile Agents
Burman, Beauquier, Clement, Kutten

Expansion and the Cover Time of Parallel Random Walks

Rapid Randomized Pruning for Fast Greedy Distributed Algorithms
Pandit, V. Pemmaraju

roadcasting in Radio Networks with Unreliable Communication
Kuhn, Lynch, Newport, Oshman, Richa

Discrete Load Balancing is (Almost) as Easy as Continuous Load Balancing
Elsaesser, Sauerwald

Locating a Target With an Agent Guided by Unreliable Local Advice
Hanusse, Ilcinkas, Kosowski, Nisse

Distributed Algorithms for Edge Dominating Sets

Fast Flooding over Manhattan
Clementi, Monti, Silvestri

Bayesian Ignorance
Alon, Emek, Feldman, Tennenholtz

Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Barenboim, Elkin

Breaking the O(n^2) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary
King, Saia

Optimal Gradient Clock Synchronization in Dynamic Networks
Lenzen, Kuhn, Locher, Oshman

Online Set Packing and Competitive Scheduling of Multi-part Tasks
Emek, Halldorsson, Mansour, Patt-Shamir, Radhakrishnan, Rawitz

How to Meet When you Forget: Log-space Rendezvous in Arbitrary Graphs
Czyzowicz, Kosowski, Pelc

A Modular Approach to Shared-memory Consensus, with Applications to the Probabilistic-write Model

Constant RMR Solutions to Reader Writer Synchronization
Bhatt, Jayanti

Brief Announcements

View Transactions: Transactional Model with Relaxed Consistency Checks
Afek, Morrison, Tzafrir

Single-Version Permissive STM
Attiya, Hillel

NUMA-aware Transactional Memory
Wang, Lu, Lu

Actions in the Twilight - Concurrent Irrevocable Transactions and Inconsistency Repair
Bieniusa, Middelkoop,Thiemann

On Enhancing Concurrency in Distributed Transactional Memory
Zhang, Ravindran

Queuing or Priority Queuing? On the Design of Cache-Coherence Protocols for Distributed Transactional Memory
Zhang, Ravindran

$k$-shot Distributed Broadcasting in Radio Networks
Koutris, Pagourtzis

A Shared Disk on Distributed Storage
Vijzelaar, Bos, Fokkink

On L-Resilience, Hitting Sets, and Colorless Tasks
Gafni, Kuznetsov

An Efficient Failure Detector for Omission Environments
Cortinas, Soraluze, Lafuente, Larrea

Towards Robust Medium Access in Multi-Hop Networks
Richa, Scheideler, Schmid, Zhang

Routing with Obstacle Avoidance Mechanism with Constant Approximation Ratio
Huc, Jarry, Leone, Rolim

ART : Sub-Logarithmic Decentralized Range Query Processing with Probabilistic Guarantees
Sioutas, Papaloukopoulos, Sakkopoulos, Tsichlas, Manolopoulos, Triantafillou

Pan and Scan
Johnson, Bar-Noy

Complexity and Solution of the Send-Receive Correlation Problem
Zander, Wanke, Kiess, Scheuermann

Distributed Contention Resolution in Wireless Networks
Kesselheim, Vöcking

Sources of Instability in Data Center Multicast
Basin, Birman, Keidar, Vigfusson

Superpeer Formation Amidst Churn and Rewiring
Mitra, Ghose, Ganguly

Self-Monitoring in Dynamic Wireless Networks
Holzer, Pignolet, Smula, Wattenhofer

The Price of Anarchy for Distributed Network Formation in an Adversary Model

Swarming Secrets
Dolev, Garay, Gilboa, Kolesnikov

Distributed Trust Management and Revocation
Kuptsov, Garcia-Morchon, Wehrle, Gurtov

Realizing Secure Multiparty Computation on Incomplete Networks

Anonymity and Trust in Distributed Systems
Backes, Lorenz, Maffei, Pecina

Secret Sharing Based on the Social Behaviors of Players
Nojoumian, Stinson

Improving Social-Network-based Sybil-resilient Node Admission Control
Tran, Li, Subramanian, Chow

Communication Efficient Asynchronous Byzantine Agreement
Patra, Rangan, Chandrasekaran

Perfectly Secure Message Transmission Tolerating Mobile Mixed Adversary with Reduced Phase Complexity
Patra, Chou, Rangan, Chandrasekaran

On the Quest of Optimal Service Ordering in Decentralized Queries
Tsamoura, Gounaris, Manolopoulos

Network Traffic can Optimize Consolidation During Transformation to Virtualization
Sun, Li, Luo

Distributed Almost Stable Marriage
Floreen, Kaski, Polishchuk, Suomela

Decentralized Construction of Multicast Trees Embedded into P2P Overlay Networks based on Virtual Geometric Coordinates
Andreica, Dragus, Sambotin, Tapus

Deterministic Dominating Set Construction in Networks With Bounded Degree
Friedman, Kogan

Efficient Graph Algorithms Without Synchronization
Schneider, Wattenhofer

Tree Decomposition for Faster Concurrent Data Structures
Schneider, Wattenhofer

The Accuracy of Tree-based Counting in Dynamic Networks
Krishnamurthy, Ardelius, Aurell, Dam, Stadler, Wuhib

Adaptive Content Placement for Peer-to-Peer Video-on-Demand Systems
Tan, Massoulie

Exponential Speed-Up of Local Algorithms using Non-Local Communication
Lenzen, Wattenhofer

Asynchronous Bounded Expected Delay Networks
Bakhshi, Endrullis, Fokkink, Pang

Locally-Accessible Implementations for Distributed Shared Memory Multiprocessors

Capacity of Byzantine Agreement with Finite Link Capacity - Complete Characterization of Four-Node Networks
Liang, Vaidya

A Framework for Building Self-Stabilizing Overlay Networks
Berns, Ghosh, Pemmaraju

Revisiting the Power-law Degree Distribution for Social Graph Analysis
Sala, Gaito, Rossi, Zheng, Zhao

Collusion Free Protocol for Rational Secret Sharing

Leader Election vs Pattern Formation
Dieudonne, Petit, Villain

Monotonic Stabilization
Yamauchi, Tixeuil

Modelling MapReduce for Optimal Execution in the Cloud
Wieder, Bhatotia, Post, Rodrigues