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