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

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)

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.