PODC 2007


Sunday Evening

17:30 - 19:30 Google Reception


08:45Welcome Address
08:50Keynote Dr. Marc Tremblay, Senior Vice President and Chief Architect Systems Group, Sun Microsystems: Transactional Memory for a Modern Microprocessor
 Multiprocessor, Multicore, Shared Memory [back to top]
Session Chair: Maurice Herlihy
10:15Constant-RMR Implementations of CAS and Other Synchronization Primitives Using Read and Write Operations PDF
Wojciech Golab, Vassos Hadzilacos, Danny Hendler, Philipp Woelfel
10:40SNZI: Scalable NonZero Indicators PPT
Faith Ellen, Yossi Lev, Victor Luchangco, Mark Moir
11:05Abortable and Query-Abortable Objects and their Efficient Implementation
Marcos Aguilera, Svend Frolund, Vassos Hadzilacos, Stephanie Horn, Sam Toueg
11:30Time-Optimal, Space-Efficient Single-Scanner Snapshots & Efficient Multi-Scanner Snapshots using CAS
Panagiota Fatourou, Nikolaos Kallimanis
 Graph Algorithms [back to top]
Session Chair: Yehuda Afek
14:00Reconstructing Approximate Tree Metrics PDF
Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Kunal Talwar, Venugopalan Ramasubramanian
14:25A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs PPT
Beat Gfeller, Elias Vicari
14:50Improved Sparse Covers for Graphs Excluding a Fixed Minor PPT
Costas Busch, Ryan LaFortune, Srikanta Tirthapura
15:15Compact Routing Schemes with Relaxed Guarantees for Networks of Low Doubling Dimension PPT
Goran Konjevod, Andrea Richa, Donglin Xia, Hai Yu
Compact routing with slack PDF
Michael Dinitz
 Peer-to-Peer Systems [back to top]
Session Chair: Pierre Fraigniaud
16:20Towards Fast Decentralized Construction of Locality-Aware Overlay Networks PDF
Aleksandrs Slivkins
16:45On the complexity of greedy routing in ring-based peer-to-peer networks
George Giakkoupis, Vassos Hadzilacos
17:10Constructing Scalable Overlays for Pub-Sub with Many Topics: Problems, Algorithms, and Evaluation PPT
Gregory Chockler, Roie Melamed, Yoav Tock, Roman Vitenberg

20:30 Business Meeting


08:45Keynote Dr. Tom Leighton, Professor of Applied Mathematics MIT, Co-Founder and Chief Scientist Akamai: The Akamai Approach to Achieving Performance and Reliability on the Internet
 Security [back to top]
Session Chair: Idit Keidar
10:15Refined Quorum Systems PPT
Rachid Guerraoui, Marko Vukolic
10:40Efficient Fork-Linearizable Access to Untrusted Shared Memory PPT
Christian Cachin, Abhi Shelat, Alexander Shraer
11:05Verifying distributed erasure-coded data PDF
James Hendricks, Gregory Ganger, Michael Reiter
11:30Truth in advertising: Lightweight verification of route integrity
Edmund Wong, Praveen Balasubramanian, Lorenzo Alvisi, Mohamed Gouda, Vitaly Shmatikov
11:55Countering Web Spam with Credibility-Based Link Analysis
James Caverlee, Ling Liu
12:20Industry-Sponsored Lunch for Students and Postdocs (All other attendees have lunch on their own) hosted by Indranil Gupta
 Brief Announcements
 Track A [back to top]
Session Chair: Seth Gilbert
14:30Partition approach to failure detectors for k-set agreement PDF
Wei Chen, Jialin Zhang, Yu Chen, Xuezheng Liu
14:37Failure Detectors as Schedulers
Alejandro Cornejo, Sergio Rajsbaum, Michel Raynal, Corentin Travers
14:44Bounded Wait-Free Implementation of Optimally Resilient Byzantine Storage without (Unproven) Cryptographic Assumptions
Amitanand Aiyer, Lorenzo Alvisi, Rida Bazzi
14:51Remote storage with byzantine servers
Marcos Aguilera, Ram Swaminathan
14:58On the Minimal Synchrony for Byzantine Agreement
Achour Mostefaoui, Gilles Tredan
15:05Multicoordinated Paxos PDF
Lásaro Camargos, Rodrigo Schmidt, Fernando Pedone
15:12The Complexity of Updating Multi-Writer Snapshot Objects
Hagit Attiya, Faith Ellen, Panagiota Fatourou
15:19From an intermittent rotating star to a leader PDF
Antonio Fernadez, Michel Raynal
15:26Break (25min)
Session Chair: Costas Busch
15:45Constant Phase Efficient Protocols for Perfectly Secure Message Transmission in Directed Graphs
Arpita Patra, Ashish Choudhary, Chandrasekaran Pandu Rangan
15:52Space Adaptation: Privacy-preserving Multiparty Collaborative Mining with Geometric Perturbation PDF
Keke Chen, Ling Liu
15:59Practical Private Computation of Vector Addition-Based Functions PPT
John Canny, Yitao Duan
16:06Integrated Resource Allocation in Heterogeneous SAN Data Centers
Aameek Singh, Madhukar Korupolu, Bhuvan Bamba
16:13Distributed QoS In Heterogeneous Resource Environments
Ajay Gulati, Arif Merchant, Peter Varman
16:20Configurations: A Model For Distributed Data Storage Systems
Bob Mungamuru, Hector Garcia-Molina, Christopher Olston
16:27A Formal Treatment of an Abstract Channel Implementation Using Java Sockets and TCP PPT
Chryssis Georgiou, Peter Musial, Alexander Shvartsman, Elaine Sonderegger
16:34Break (10min)
Session Chair: Rida Bazzi
16:44Transactions and Privatization in Delaunay Triangulation PDF
Michael Scott, Michael Spear, Luke Dalessandro, Virendra Marathe
16:51Privatization Techniques for Software Transactional Memory PPT
Michael Spear, Virendra Marathe, Luke Dalessandro, Michael Scott
16:58From Causal to z-Linearizable Transactional Memory PDF
Pascal Felber, Heiko Sturzrehm, Torvald Riegel, Christof Fetzer
17:05The Power of DCAS: Highly-Concurrent Software Transactional Memory
Hagit Attiya, Eshcar Hillel
17:12Object Replication Degree Customization for High Availability
Ming Zhong, Kai Shen, Joel Seiferas
17:19Pattern Grids, Sharpness, and the Throughput of Infinite Systems PDF
Augustin Chaintreau
17:26An Analysis of Intention Preservation in Group Editors
Du Li, Rui Li
17:33The CoBFIT Toolkit PPT
HariGovind Ramasamy, Mouna Seri, William H. Sanders
 Track B [back to top]
Session Chairs: Alexandrs Slivkins
14:30On Local Representation of Distances in Trees
Cyril Gavoille, Arnaud Labourel
14:37Minimizing the total cost of network measurements in a distributed manner: a primal-dual approach PPT
Baruch Awerbuch, Rohit Khandekar
14:44Game Authority for Robust and Scalable Distributed Selfish-Computer Systems PPT
Shlomi Dolev, Elad M. Schiller, Paul G. Spirakis, Philippas Tsigas
14:51Theory of BAR Games
Allen Clement, Jeff Napper, Harry Li, Jean-Philippe Martin, Lorenzo Alvisi, Michael Dahlin
14:58An algorithm composition scheme preserving monotonicity PPT
Davide Bilo, Luca Forlizzi, Luciano Guala, Guido Proietti
15:05An Incentive Compatible Multi Armed Bandit Mechanism
Rica Gonen, Elan Pavlov
15:12On Cost Sharing Mechanisms in the Network Design Game PPT
Baruch Awerbuch, Rohit Khandekar
15:19Asynchronous Recommendation Systems PDF
Baruch Awerbuch, Aviv Nisgav, Boaz Patt-Shamir
Session Chair: Thomas Moscibroda
15:45Bringing Order To BGP: Decreasing Time and Message Complexity PDF
Anat Bremler-Barr, Nir Chen, Ossi Mokryn, Jussi Kangasharju, Yuval Shavitt
15:52A Denial-of-Service Resistant DHT PPT
Baruch Awerbuch, Christian Scheideler
15:59Measuring Robustness of Superpeer Topologies
Bivas Mitra, Fernando Peruani, Sujoy Ghose, Niloy Ganguly
16:06SuperTrust - A Secure and Efficient Framework for Handling Trust in Super Peer Networks
Tassos Dimitriou, Ghassan Karame, Ioannis Christou
16:13Toward an Optimal Social Network Defense Against Sybil Attacks PPT
Haifeng Yu, Phillip Gibbons, Michael Kaminsky
16:20Trinity: A Distributed Defense Against Transient Spam-bots
Alex Brodsky, Dmitry Brodsky
16:27Non-Searchability of Random Scale-Free Graphs
Philippe Duchon, Nicole Eggemann, Nicolas Hanusse
Session Chair: Srikanta Tirthapura
16:44Distributed Broadcasting and Mapping Protocols in Directed Anonymous Networks PPT
Michael Langberg, Moshe Schwartz, Jehoshua Bruck
16:51Optimal Atomic Broadcast and Multicast Algorithms for Wide Area Networks PPT
Nicolas Schiper, Fernando Pedone
16:58Solvability of Geocasting in Mobile Ad-Hoc Networks
Roberto Baldoni, Kleoni Ioannidou, Alessia Milani
17:05Geographic Gossip on Geometric Random Graphs via Affine Combinations
Hariharan Narayanan
17:12Practical Summation via Gossip PPT
Wesley W. Terpstra, Christof Leng, Alejandro P. Buchmann
17:19Distributed Algorithms for Dynamic Coverage in Sensor Networks PPT
Lan Lin, Hyunyoung Lee
17:26DoS-Resilient Secure Aggregation Queries in Sensor Networks PPT
Haifeng Yu
17:33Self-Stabilizing Counting in Mobile Sensor Networks PDF
Julien Clement, Joffroy Beauquier, Stephane Messika, Laurent Rosaz, Brigitte Rozoy

Tuesday Evening: Awards & Banquet


 Local & Dynamic Algorithms [back to top]
Session Chair: Tim Roughgarden
08:45Distributed Approximate Matching PDF
Zvi Lotker, Boaz Patt-Shamir, Adi Rosen
09:10Controller and Estimator for Fully Dynamic Networks PPT
Amos Korman, Shay Kutten
09:35A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners PDF
Michael Elkin
 Radio Networks and Aggregation [back to top]
Session Chair: Rachid Guerraoui
10:30Broadcasting Time in UDG Radio Networks with Unknown Topology PPT
Yuval Emek, Leszek Gasieniec, Erez Kantor, Andrzej Pelc, David Peleg, Chang Su
10:55Communication in Dynamic Radio Networks
Andrea Clementi, Angelo Monti, Francesco Pasquale, Riccardo Silvestri
11:20Time-Decaying Sketches for Sensor Data Aggregation PPT
Graham Cormode, Srikanta Tirthapura, Bojian Xu
11:45Summarizing Data using Bottom-k Sketches PPT
Edith Cohen, Haim Kaplan
 Fault-Tolerance [back to top]
Session Chair: Hagit Attiya
14:00On the weakest failure detector ever
Rachid Guerraoui, Maurice Herlihy, Petr Kouznetsov, Nancy Lynch, Calvin Newport
14:25Tolerating corrupted communication PDF
Martin Biely, Bernadette Charron-Bost, Antoine Gaillard, Martin Hutle, André Schiper ,Josef Widder
14:50Optimal Inter-Object Correlation When Replicating for Availability PPT
Haifeng Yu, Phillip Gibbons
15:15Specifying and Designing Gracefully Degradable Systems PDF
Vijayan Prabhakaran, Venugopalan Ramasubramanian, Lidong Zhou
 Economical aspects [back to top]
Session Chair: Kamal Jain
16:10Greedy Distributed Optimization of Multi-Commodity Flows PPT
Baruch Awerbuch, Rohit Khandekar
16:35Distributed Network Monitoring and Multicommodity flows: Primal-Dual approach PPT
Baruch Awerbuch, Rohit Khandekar
17:00The Price of Anarchy in Network Creation Games
Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam
17:25Network Formation Games with Local Coalitions
Stefano Leonardi, Piotr Sankowski

Wednesday Evening: Workshop Reception


Whole day: Workshops