| 9:00am - 9:10am |
Welcome
|
| 9:10am - 10:25am |
Session 1: Routing I
|
| 9:10am - 9:35am |
On Delivery Times in Packet Networks under Adversarial Traffic
Adi Rosen and Michael S. Tsirkin
|
| 9:35am - 10:00am |
Adaptive Channel Queue Routing on k-ary n-cubes
Arjun Singh, William J. Dally, Amit Gupta, and Brian Towles
|
| 10:00am - 10:25am |
Compact Name-Independent Routing with Minimum Stretch
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup
|
| 10:25am - 10:50am |
Break |
| 10:50am - 12:30pm |
Session 2: Peer-To-Peer Systems
|
| 10:50am - 11:15am |
Object location in realistic networks
Kirsten Hildrum, Robert Krauthgamer, and John Kubiatowicz
|
| 11:15am - 11:40am |
Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems
David R. Karger and Matthias Ruhl
|
| 11:40am - 12:05am |
Consistent, Order-Preserving Data Management in Distributed Storage Systems
Baruch Awerbuch and Christian Scheideler
|
| 12:05am - 12:30pm |
Geometric Generalizations of the Power of Two Choices
John W. Byers, Jeffrey Considine, and Michael Mitzenmacher
|
| 12:30pm - 2:30pm |
Lunch |
| 2:30pm - 3:45pm |
Session 3: Caching I
|
| 2:30pm - 2:55pm |
Fighting Against Two Adversaries: Page Migration in Dynamic Networks
Marcin Bienkowski, Miroslaw Korzeniowski, and Friedhelm Meyer auf der Heide
|
| 2:55pm - 3:20pm |
Online Hierarchical Cooperative Caching
Xiaozhou Li, C. Greg Plaxton, Mitul Tiwari, and Arun Venkataramani
|
| 3:20pm - 3:45pm |
New Results on Web Caching with Request Reordering
Susanne Albers
|
| 3:45pm - 4:15pm |
Break |
| 4:15pm - 5:30pm |
Session 4: Routing II
|
| 4:15pm - 4:40pm |
Packet-Mode Policies for Input-Queued Switches
Dan Guez, AlexKesselman, and Adi Rosen
|
| 4:40pm - 5:05pm |
Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines
Fan Chung, Ronald Graham, and George Varghese
|
| 5:05pm - 5:30pm |
Lower Bounds for Approximating Sparse Graphs and M-Matrices
Gary L. Miller and Peter C. Richter
|
| 5:45pm - 7:30pm |
Business Meeting |
| 9:10am - 10:50am |
Session 5: Algorithms
|
| 9:10am - 9:35am |
Balanced Graph Partitioning
Konstantin Andreev and Harald Raecke
|
| 9:35am - 10:00am |
Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms
Pierre-Francois Dutot, Lionel Eyraud, Gregory Mounie, and Denis Trystram
|
| 10:00am - 10:25am |
On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson
|
| 10:25am - 10:50am |
An NC Algorithm for Finding a Maximal Acyclic Set in a Graph
Aaron Windsor
|
| 10:50am - 11:15am |
Break |
| 11:15am - 12:30pm |
Session 6: Networks I
|
| 11:15am - 11:40am |
Scheduling Against an Adversarial Network
Stefano Leonardi, Alberto Marchetti-Spaccamela, and Friedhelm Meyer auf der Heide
|
| 11:40am - 12:05am |
On Achieving Optimized Capacity Utilization in Application Overlay Networks with Multiple Competing Sessions
Yi Cui, Baochun Li, and Klara Nahrstedt
|
| 12:05am - 12:30am |
Pagoda: A Dynamic Overlay Network for Routing, Data Management, and Multicasting
Ankur Bhargava, Kishore Kothapalli, Chris Riley, Christian Scheideler, and Mark Thober
|
| 12:30pm - 2:30pm |
Lunch |
| 2:30pm - 3:45pm |
Session 7: Algorithmic Game Theory
|
| 2:30pm - 2:55pm |
Sharing the Cost of Multicast Transmissions in Wireless Network
V. Bilo, C. Di Francescomarino, M. Flammini, and G. Melideo
|
| 2:55pm - 3:20pm |
Selfish Load Balancing and Atomic Congestion Games
Subhash Suri, Csaba D. Toth, and Yunhong Zhou
|
| 3:20pm - 3:45pm |
How to Route and Tax Selfish Unsplittable Traffic
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Pino Persiano
|
| Late afternoon - evening |
Outing and Dinner |
| 9:00am - 10:15am |
Session 8: Shared Memory and Architecture
|
| 9:00am - 9:25am |
A Scalable Lock-free Stack Algorithm
Danny Hendler, Nir Shavit, and Lena Yerushalmi
|
| 9:25am - 9:50am |
DCAS is not a Silver Bullet for Nonblocking Algorithm Design
Simon Doherty, David L. Detlefs, Lindsay Groves, Christine H. Flood, Victor Luchangco, Paul A. Martin, Mark Moir, Nir Shavit, and Guy L. Steele, Jr.
|
| 9:50am - 10:15am |
Efficient Orchtestration of Sub-Word Parallelism in Media Processors
John Oliver, Venkatesh Akella, and Frederic T. Chong
|
| 10:15am - 10:30am |
Break |
| 10:30am - 11:45pm |
Session 9: Caching II
|
| 10:30am - 10:55am |
Effectively Sharing a Cache Among Threads
Guy E. Blelloch and Phillip B. Gibbons
|
| 10:55am - 11:20am |
Cache-Oblivious Shortest Paths in Graphs Using Buffer Heap
Rezaul Alam Chowdhury and Vijaya Ramachandran
|
| 11:20am - 11:45am |
Online Algorithms for Prefetching and Caching on Parallel Disks
Rahul Shah, Peter Varman, and Jeffrey Scott Vitter
|
| 11:45am - 12:00am |
Break |
| 12:00pm - 12:50pm |
SPAA Revue
|
| 12:00pm - 12:10pm |
Improved Combination of Online Algorithms for Acceptance and Rejection
David P. Bunde and Yishay Mansour
|
| 12:10pm - 12:20pm |
Time Complexity of Practical Parallel Steiner Point Insertion Algorithms
Dan A. Spielman, Shang-hua Teng, and Alper Ungor
|
| 12:20pm - 12:30pm |
The Inherent Queuing Delay of Parallel Packet Switches
Hagit Attiya and David Hay
|
| 12:30pm - 12:40pm |
Efficient Search in Unstructured Peer-to-Peer Networks
Vicent Cholvi, Pascal Felber, and Ernst Biersack
|
12:40pm - 12:50pm |
The Potential in Energy Efficiency of a Speculative Chip-Multiprocessor
Yuu Tanaka and Toshinori Sato and Takenori Koushiro
|
| 12:50pm - 2:45pm |
Lunch |
| 2:45pm - 4:00pm |
Session 10: Networks II
|
| 2:45pm - 3:10pm |
Online Algorithms for Network Design
Adam Meyerson
|
| 3:10pm - 3:35pm |
Expansion Properties of (Secure) Wireless Networks
Alessandro Panconesi and Jaikumar Radhakrishnan
|
| 3:35pm - 4:00pm |
The Effect of Random Faults on Network Expansion
Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, and Christian Scheideler
|
| 4:00pm - 4:15pm |
Break |
| 4:15pm - 5:30pm |
Session 11: Distributed Computation
|
| 4:15pm - 4:40pm |
Dynamic Analysis of the Arrow Distributed Protocol
Fabian Kuhn and Roger Wattenhofer
|
| 4:40pm - 5:05pm |
Optimal Early Stopping Uniform Consensus in Synchronous Systems with Process Omission Failures
Philippe Raipin Parvedy and Michel Raynal
|
| 5:05pm - 5:30pm |
Writing-All Deterministically and Optimally Using a Non-Trivial Number of Asynchronous Processors
Dariusz Kowalski and Alex Shvartsman
|
| 5:30pm |
END. |