Sunday, July 17th, 2005
18:00-21:00 Reception (sponsored by Google)
Monday, July 18th, 2005
7:30- 8:20 Continental Breakfast
8:20-10:10 Session 1: Verification and Security (Session chair: Boaz Patt-Shamir, Tel-Aviv U.)
A Topological Characterization of Weakness
Cindy Eisner, Dana Fisman and John HavlicekProof Labeling Schemes
Amos Korman, Shay Kutten and David PelegEfficient Dependency Tracking for Relevant Events in Shared-Memory Systems
Anurag Agarwal and Vijay K. GargPolicy-Hiding Access Control in Open Environment
Jiangtao Li and Ninghui LiBrief Announcement: A Flexible Framework for Secret Handshakes
Gene Tsudik and Shouhuai XuBrief Announcement: Strong Detection of Misconfigurations
Raj Kumar Rajendran, Vishal Misra and Dan Rubenstein
10:10-10:30 Break
10:30-12:10 Session 2: Joint Session (Session chair: James Aspnes, Yale U.)
Distance Estimation and Object Location via Rings of Neighbors
Aleksandrs SlivkinsBuilding Scalable and Robust Peer-to-Peer Overlay Networks for Broadcasting using Network Coding
Kamal Jain, Laszlo Lovasz and Philip A. Chou(SPAA) Coloring Unstructured Radio Networks
Thomas Moscibroda and Roger Wattenhofer(SPAA) Name Independent Routing for Growth Bounded Networks
Ittai Abraham and Dahlia Malkhi
12:10-13:45 Lunch
13:45-15:35 Session 3: Distributed Data Structures (Session chair: Dahlia Malkhi, Microsoft Research and Hebrew U.)
On the Locality of Bounded Growth
Fabian Kuhn, Thomas Moscibroda and Roger WattenhoferSkip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets
Lars Arge, David Eppstein and Michael GoodrichEfficient Lookup on Unstructured Topologies
Ruggero Morselli, Bobby Bhattacharjee, Michael A. Marsh and Aravind SrinivasanQuorum Placement in Networks
Anupam Gupta, Bruce Maggs, Florin Oprea and Michael K. ReiterBrief Announcement: Ring-like DHTs and the Postage Stamp Problem
Mahadev Konar and Alexander E. MohrBrief Announcement: The Overlay Network Content Distribution Problem
Chip Killian, Michael Vrable, Alex C. Snoeren, Amin Vahdat and Joseph Pasquale
15:35-16:05 Break
16:05-17:35 Session 4: Optimization (Session chair: Jared Saia, UNM)
The Price of Selfish Behavior in Bilateral Network Formation
Jacomo Corbo and David C. ParkesFacility Location: Distributed Approximation
Thomas Moscibroda and Roger WattenhoferPrimal-Dual Based Distributed Algorithms for Vertex Cover with Semi-Hard Capacities
F. Grandoni, J. Konemann, A. Panconesi and M. SozioBrief Announcement: On the Expected Overpayment of VCG Mechanisms in Large Networks
David R. Karger and Evdokia NikolovaBrief Announcement: An Incentive-compatible Capacity Assignment Algorithm for Bulk Data Distribution Using P2P
Simon G. M. Koo, C. S. George Lee and Karthik KannanBrief Announcement: Distributed Algorithmic Mechanism Design for Scheduling
Thomas E. Carroll and Daniel Grosu
17:35-18:00 Poster Session
20:00-22:00 Business Meeting and Rump Session
Tuesday, July 19th, 2005
7:30- 8:20 Continental Breakfast
8:20-10:10 Session 5: Radio Networks (Session chair: Bogdan Chlebus, UC Denver)
Faster Communication in Known Topology Radio Networks
Leszek Gasieniec, David Peleg and Qin XinOn Reliable Broadcast in a Radio Network
Vartika Bhandari and Nitin H. aidyaMaximal Independent Sets in Radio Networks
Thomas Moscibroda and Roger WattenhoferOn Selection Problem in Radio Networks
Dariusz KowalskiBrief Announcement: Broadcast in Radio Networks in the presence of Byzantine Adversaries
Vinod VaikuntanathanBrief Announcement: Exploring the consistency problem space
Nishith Krishna, Marc Shapiro and Karthik Bhargavan
10:10-10:40 Break
10:40-11:40 Invited Talk
TBA
Elias Koutsoupias
11:40-13:45 Lunch
13:45-15:35 Session 6: Consensus (Session chair: Rachid Guerraoui, EPFL)
Fast fault-tolerant agreement algorithms
Carole Delporte-Gallet, Hugues Fauconnier, Stephanie Horn and Sam TouegThe Combined Power of Conditions and Failure Detectors to Solve Asynchronous Set Agreement
Achour Mostefaoui, Sergio Rajsbaum and Michel RaynalThe weakest failure detector to solve nonuniform consensus.
Jonathan Eisler, Vassos Hadzilacos and Sam TouegConsensus and Collision Detectors in Wireless Ad Hoc Networks
Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport and Tina NolteBrief Announcement: Minimal System Conditions to Implement Unreliable Failure Detectors
Antonio Fernendez, Ernesto Jimenez and Sergio ArevaloBrief Announcement: On the Possibility and the Impossibility of Message-Driven Self-Stabilizing Failure Detection
Martin Hutle and Josef Widder
15:35-16:05 Break
16:05-17:35 Session 7: Routing (Session chair: Marcos Aguilera, HP Labs)
Routing Complexity of Faulty Networks
Omer Angel, Itai Benjamini, Eran Ofek and Udi WiederFeedback Control for Router Congestion Resolution
Xiaojie Gao and Leonard J. SchulmanCompetitive Weighted Throughput Analysis of Greedy Protocols on DAGs
Eyal Gordon and Adi RosenBrief Announcement: Continuous Containment and Local Stabilization in Path-vector Routing
Hongwei Zhang and Anish AroraBrief Announcement: Gradient Clock Synchronization in Sensor Networks
Lennart Meier and Lothar ThieleBrief Announcement: Evaluation of Tree-based Data Gathering Algorithms for Wireless Sensor Networks
Melody Moh, Marie Dumont, Teng-Sheng Moh, Takeo Hamada, and Ching-Fong Su
17:45-18:45 Awards Ceremony and Dijkstra Prize Lecture
19:00-22:00 Banquet
Wednesday, July 20th, 2005
8:20-10:10 Session 8: Contention (Session chair: Mark Moir, Sun Microsystems)
Advanced Contention Management for Dynamic Software Transactional Memory
William N. Scherer III and Michael L. ScottEfficient Multi-Word Locking Using Randomization
Phuong Hoai Ha, Philippas Tsigas, Mirjam Wattenhofer and Roger WattenhoferToward a Theory of Transactional Contention Managers
Rachid Guerraoui, Maurice Herlihy and Bastian PochonStochastic Analysis of Distributed Deadlock Scheduling
Yibei Ling and Shigang ChenBrief Announcement: Analysis of a Randomized Contention-Resolution Protocol for Distributed Access
Gopal Pandurangan and Gahyun ParkBrief Announcement: Improved Asynchronous Group Mutual Exclusion
David Lin, Teng-Sheng Moh and Melody Moh
10:10-10:30 Break
10:30-12:10 Session 9: Joint Session (Session chair: Paul Spirakis, U. Patras)
Adaptive Routing with Stale Information
Simon Fischer and Berthold VockingA Network Pricing Game for Selfish Traffic
Ara Hayraptetyan, Eva Tardos and Tom Wexler(SPAA) Using Elimination to Implement Scalable FIFO Queues
Mark Moir, Daniel Nussbaum, Ori Shalev and Nir Shavit(SPAA) Collaborate with Strangers to Find Own Preferences
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir and Mark Tuttle
12:10-13:45 Lunch
13:45-15:15 Session 10: Peer-to-Peer (Session chair: Haifeng Yu, Intel Research Pittsburgh)
Correctness of a Gossip Based Membership Protocol
Andre Allavena, Alan Demers and John HopcroftA Scheme for Load Balancing in Heterogenous Distributed Hash Tables
George Giakkoupis and Vassos HadzilacosOn the Establishment of Distinct Identities in Overlay Networks
Rida Bazzi and Goran KonjevodBrief Announcement: Controlled Quorum Selection in Arbitrary Topologies
Xinjie Li and Monica BrockmeyerBrief Announcement: Coupling for Markov Decision Processes: Application to Self-Stabilization with Arbitrary Schedulers
Laurent Fribourg and Stephane MessikaBrief Announcement: Virtual Stationary Automata for Mobile Networks
Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch and Tina Nolte
15:15-15:45 Break
15:45-17:15 Session 11: Broadcast (Session chair: Shlomi Dolev, Ben-Gurion U.)
Simultaneous Broadcast Revisited
Alejandro Hevia and Daniele MicciancioFeasibility and Complexity of Broadcasting with Random Transmission Failures
Andrzej Pelc and David PelegReliable Broadcast in Unknown Fixed-Identity Networks
Lakshminarayanan Subramanian, Randy H. Katz, Volker Roth, Scott Shenker and Ion StoicaBrief Announcement: Dynamic Interoperable Point-to-Point Connection of MPI Implementations
Michal Kouril and Jerome L. PaulBrief Announcement: Wait-Free Implementation of Multiple-Writers/Multiple-Readers Atomic Byzantine Data Storage Systems
Rida Bazzi and Yin DingBrief Announcement: Abstractions for Implementing Atomic Objects in Dynamic Systems
Roy Friedman, Michel Raynal and Corentin Travers
Last modified: Tue Jun 7 14:13:20 EST 2005