PROGRAM FOR SPAA 2004


June 27, 2004, Sunday

6pm - 9pm Registration at Sala del Llac (Campus Nord)
7pm - 9pm Reception at Jardins del Rectorat (Garden in front of Sala del Llac, Campus Nord - UPC)

June 28, 2004, Monday

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

June 29, 2004, Tuesday

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

June 30, 2004, Wednesday

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.

The page maintained by
Cindy Phillips <caphill@sandia.gov>

Last modified: June 22, 2004