PODC 2010 Program


Main Menu Home Scope Call for Papers Important Dates Program Committee Conference Committee Steering Committee Submission Accepted Papers Program Awards (new!) Invited Speakers Registration Local Information Student Travel Grants Visa Information Workshops Related Conferences PODC Home Page	Program
Sunday, July 25 15h00 - 16h00: Registration and Welcome Reception 16h00 - 18h00: 60'th Birthday celebration of Danny Dolev and Eli Gafni Landmarks in Distributed Computing: Celebrating the Research of Dolev and Gafni. Speakers include: Afek, Attiya, Bar-Noy, Keidar, Guerraoui, Merritt, Rajsbaum, and Shavit. Monday, July 26 8h15 - 9h00: Invited Talk Hagit Attiya (Technion) The inherent complexity of transactional memory and what to do about it. 9h00 - 10h00: Session 1 (regular papers) Session chair: Ruppert 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 10h00 - 10h30: Break 10h30 - 11h30: Session 2.a (regular papers) Session chair: Rodrigues The k-Bakery: Local-spin k-Exclusion Using Non-atomic Reads and Writes Danek Group Mutual Exclusion in O(log n) RMR Bhatt, Huang On Asymmetric Progress Conditions Imbs, Raynal, Taubenfeld 11h30 - 12h30: Session 2.b (brief announcements) Session chair: Rodrigues 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 12h30 - 14h00: Lunch 14h00 - 15h00: Session 3.a (regular papers) Session chair: Gilbert 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 15h00 - 16h00: Session 3.b (brief announcements) Session chair: Gilbert 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 16h00 - 16h30: Break 16h30 - 17h45: Session 4 (regular papers) Session chair: 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 18h00 - 19h30: Business Meeting (and Beer) Tuesday, July 27 8h15 - 9h00: Invited Talk Pierre Fraigniaud (CNRS) On distributed computational complexities: are you Volvo-driving or NASCAR-obsessed? 9h00 - 10h00: Session 5 (regular papers) Session chair: Hendler 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 10h00 - 10h30: Break 10h30-11h30: Session 6.a (regular papers) Session chair: Cachin 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 11h30 - 12h30: Session 6.b (brief announcements) Session chair: Cachin The Price of Anarchy for Distributed Network Formation in an Adversary Model Kliemann Swarming Secrets Dolev, Garay, Gilboa, Kolesnikov Distributed Trust Management and Revocation Kuptsov, Garcia-Morchon, Wehrle, Gurtov Realizing Secure Multiparty Computation on Incomplete Networks Vaya 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 12h30 - 14h00: Lunch 14h00 - 15h00: Session 7.a (regular papers) Session chair: Fernandez 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 15h00 - 16h00: Session 7.b (brief announcements) Session chair: Fernandez 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 16h00 - 16h30: Break 16h30 - 17h45: Session 8 (regular papers) Session chair: Petit 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 Sauerwald Rapid Randomized Pruning for Fast Greedy Distributed Algorithms Pandit, V. Pemmaraju 19h00 - 23h00: Banquet and Award Ceremony Wednesday, July 28 8h15 - 9h00: Invited Talk Eric Brewer (Berkeley) On a certain freedom: exploring the CAP space. 9h00 - 10h00: Session 9 (regular papers) Session chair: Kowalski 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 10h00 - 10h30: Break 10h30 - 11h30: Session 10.a (regular papers) Session chair: Aguilera Distributed Algorithms for Edge Dominating Sets Suomela Fast Flooding over Manhattan Clementi, Monti, Silvestri Bayesian Ignorance Alon, Emek, Feldman, Tennenholtz 11h30 - 12h30: Session 10.b (brief announcements) Session chair: Aguilera Asynchronous Bounded Expected Delay Networks Bakhshi, Endrullis, Fokkink, Pang Locally-Accessible Implementations for Distributed Shared Memory Multiprocessors Golab 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 Shareef Leader Election vs Pattern Formation Dieudonne, Petit, Villain Monotonic Stabilization Yamauchi, Tixeuil Modelling MapReduce for Optimal Execution in the Cloud Wieder, Bhatotia, Post, Rodrigues 12h30 - 14h00: Lunch 14h00 - 16h30: Session 11 (best paper session) Session chair: Fatourou 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 Aspnes Constant RMR Solutions to Reader Writer Synchronization Bhatt, Jayanti 17h00-20h00: The LADIS workshop begins Thursday, July 29 SNDS 2010: The 1st Workshop on Social Networks and Distributed Systems LADIS 2010: The 4th ACM SIGOPS/SIGACT Workshop on Large Scale Distributed Systems and Middleware (starting on Wednesday) WRAS 2010: The 3rd ACM SIGOPS/SIGACT Workshop on Reliability and Security

Program

Sunday, July 25

15h00 - 16h00: Registration and Welcome Reception

16h00 - 18h00: 60'th Birthday celebration of Danny Dolev and Eli Gafni

Landmarks in Distributed Computing: Celebrating the Research of Dolev and Gafni.
Speakers include: Afek, Attiya, Bar-Noy, Keidar, Guerraoui, Merritt, Rajsbaum, and Shavit.

Monday, July 26

8h15 - 9h00: Invited Talk

Hagit Attiya (Technion)
The inherent complexity of transactional memory and what to do about it.

9h00 - 10h00: Session 1 (regular papers)

Session chair: Ruppert

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

10h00 - 10h30: Break

10h30 - 11h30: Session 2.a (regular papers)

Session chair: Rodrigues

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

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

On Asymmetric Progress Conditions
Imbs, Raynal, Taubenfeld

11h30 - 12h30: Session 2.b (brief announcements)

Session chair: Rodrigues

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

12h30 - 14h00: Lunch

14h00 - 15h00: Session 3.a (regular papers)

Session chair: Gilbert

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

15h00 - 16h00: Session 3.b (brief announcements)

Session chair: Gilbert

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

16h00 - 16h30: Break

16h30 - 17h45: Session 4 (regular papers)

Session chair: 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

18h00 - 19h30: Business Meeting (and Beer)

Tuesday, July 27

8h15 - 9h00: Invited Talk

Pierre Fraigniaud (CNRS)
On distributed computational complexities: are you Volvo-driving or NASCAR-obsessed?

9h00 - 10h00: Session 5 (regular papers)

Session chair: Hendler

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

10h00 - 10h30: Break

10h30-11h30: Session 6.a (regular papers)

Session chair: Cachin

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

11h30 - 12h30: Session 6.b (brief announcements)

Session chair: Cachin

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

Swarming Secrets
Dolev, Garay, Gilboa, Kolesnikov

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

Realizing Secure Multiparty Computation on Incomplete Networks
Vaya

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

12h30 - 14h00: Lunch

14h00 - 15h00: Session 7.a (regular papers)

Session chair: Fernandez

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

15h00 - 16h00: Session 7.b (brief announcements)

Session chair: Fernandez

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

16h00 - 16h30: Break

16h30 - 17h45: Session 8 (regular papers)

Session chair: Petit

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
Sauerwald

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

19h00 - 23h00: Banquet and Award Ceremony

Wednesday, July 28

8h15 - 9h00: Invited Talk

Eric Brewer (Berkeley)
On a certain freedom: exploring the CAP space.

9h00 - 10h00: Session 9 (regular papers)

Session chair: Kowalski

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

10h00 - 10h30: Break

10h30 - 11h30: Session 10.a (regular papers)

Session chair: Aguilera

Distributed Algorithms for Edge Dominating Sets
Suomela

Fast Flooding over Manhattan
Clementi, Monti, Silvestri

Bayesian Ignorance
Alon, Emek, Feldman, Tennenholtz

11h30 - 12h30: Session 10.b (brief announcements)

Session chair: Aguilera

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

Locally-Accessible Implementations for Distributed Shared Memory Multiprocessors
Golab

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
Shareef

Leader Election vs Pattern Formation
Dieudonne, Petit, Villain

Monotonic Stabilization
Yamauchi, Tixeuil

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

12h30 - 14h00: Lunch

14h00 - 16h30: Session 11 (best paper session)

Session chair: Fatourou

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
Aspnes

Constant RMR Solutions to Reader Writer Synchronization
Bhatt, Jayanti

17h00-20h00: The LADIS workshop begins

Thursday, July 29

SNDS 2010: The 1st Workshop on Social Networks and Distributed Systems

LADIS 2010: The 4th ACM SIGOPS/SIGACT Workshop on Large Scale Distributed Systems and Middleware
(starting on Wednesday)

WRAS 2010: The 3rd ACM SIGOPS/SIGACT Workshop on Reliability and Security