PROGRAM FOR SPAA 2002

August 10, 2002, Saturday

6:30pm - 9:30pm Registration

7pm - 9pm Reception

August 11, 2002, Sunday

9:45am - 10:15am Continental Breakfast

10:15am - 10:30am Opening Remarks

10:30am - 11:55am Session 1

10:30am - 10:55am Worst-case Traffic for Oblivous Routing Functions
B. Towles, W. J. Dally

11:00am - 11:25am Locality-Preserving Randomized Oblivious Routing on Torus Networks
A. Singh, W. Dally, B. Towles, A. K. Gupta

11:30am - 11:55am ~O(Congestion + Dilation) Hot-Potato Routing on Leveled Networks
C. Busch

12:00pm - 1:30pm Lunch

1:30pm - 2:30pm Keynote Address
Andrew Chien, Entropia U. California, San Diego

2:30pm - 2:45pm break

2:45pm - 4:10pm Session 2

2:45pm - 3:10pm Distributed Caching Independent of the Network Size
M. Westermann

3:15pm - 3:40pm Distribted Data Location in a Dynamic Network
K. Hildrum, J. D. Kubiatowicz, S. Rao, B. Y. Zhao

3:45pm - 4:10pm Compact, adaptive placement schemes for non-uniform distribution requirements
A. Brinkmann, K. Salzwedel, C. Scheideler

4:10pm - 4:30pm Break

4:30pm - 5:55pm Session 3

4:30pm - 4:55pm Distributed Streams Algorithms for Sliding Windows
P. B. Gibbons, S. Tirthapura

5:00pm - 5:25pm High Performance Dynamic Lock-Free Hash Tables and List-Based Sets
M. M. Michael

5:30pm - 5:55pm Scalability and Resource Usage of an OLAP Benchmark on Clusters of PCs
M. Taufer, T. Stricker, R. Weber

8pm - 10pm Business Meeting

August 12, 2002, Monday

8:00am - 8:30am Continental Breakfast

8:30am - 9:55am Session 4

8:30am - 8:55am Two Techniques for Reconciling Algorithm Parallelism with Memory Constraints
U. Vishkin

9:00am - 9:25am A General Compiler Framework for Speculative Multithreading
A. Bhowmik, M. Franklin

9:30am - 9:55am Optimal Organizations for Pipelined Hierarchical Memories
G. Bilardi, K. Ekanadham, P. Pattnaik

9:55am - 10:15am Break

10:15am - 11:40am Session 5

10:15am - 10:40am Scheduling Reductions on Realistic Machines
Gautam , S. Rajopadhye, P. Quinton

10:45am - 11:10am Two Processor Scheduling with Real Release Times and Deadlines
H. Wu, J. Jaffar

11:15 - 11:40pm Extra Processors versus Future Information in Optimal Deadline Scheduling
C.Y. Koo, T.W. Lam, J. Ngan, K.K. To

11:40pm - 1:00pm Lunch

1:00pm - 2:00pm SPAA Revue

1:00pm - 1:10pm The Lazy Adversary Conjecture Fails
E. Peserico

1:10pm - 1:20pm AT^2L^2 = N^2/2 for Fast Fourier Transform in Multilayer VLSI
C.-H. Yeh

1:20pm - 1:30pm Rapid Prototyping Methodology For multi-DSP TI C6X Platforms
J.F. Nezan, O. Deforges, M. Raulet

1:30pm - 1:40pm Energy Estimation of Nested Loop Programs
F. Hannig, J. Teich

1:40pm - 1:50pm Sequential Consistency as Lazy Linearizability
M. Raynal

1:50pm - 2:00pm Vector Clocks, Constraint Graphs, and Verification of Memory Consistency Models
H. W. Cain, M. H. Lipasti

2:00pm - 2:20pm Break

2:20pm - 3:45pm Session 6

2:20pm - 2:45pm Exploiting Flexibly Assignable Work to Improve Load Balance
A.Pinar, B. Hendrickson

2:50pm - 3:15pm Work Dealing
D. Hendler, N. Shavit

3:20pm - 3:45pm Optimal tiling for the RNA base pairing problem
F. Almeida, R. Andonov, D. Gonzolez, L.M. Moreno, V. Poirriez, C. Rodriguez

3:45pm - 4:05pm Break

4:05pm - 5:00pm Session 7

4:05pm - 4:30pm Universal stability of undirected graphs in the adversarial queueing model
C. Alvarez, M. Blesa, M. Serna

4:35pm - 5:00pm New Stability Results for Adversarial Queuing
Z. Lotker, B. Patt-Shamir, A. Rosen

5:30pm - 11:00pm (approx) Outing to Folklorama

August 13, 2002, Tuesday

8:30am - 9:00am Continental Breakfast

9:00am - 10:25am Session 8

9:00am - 9:25am Capture of an Intruder by Mobile Agents
L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro

9:30am - 9:55am Tracking Immediate Predecessors in Distributed Computations
E. Anceaume, J.-M. Helary, M. Raynal

10:00am - 10:25am Gossiping to Reach Consensus
B. S. Chlebus, D. R. Kowalski

10:25am - 10:45am Break

10:45am - 12:10pm Session 9

10:45am - 11:10am Energy, Congestion, and Dilation in Radio Networks
F. Meyer auf der Heide, C. Schindelhauer, K. Volbert, M. Grunewald

11:15am - 11:40am Parallel Scheduling in Next Generation Wireless Networks
L. Becchetti, S. Diggavi, S. Leonardi, A. Marchetti-Spaccamela, S. Muthukrishnan, T. Nandagopal, A. Vitaletti

11:45am - 12:10pm A Lightweight Idempotent Messaging Protocol for Faulty Networks
J. Brown, J.P. Grossman, T. Knight

12:10pm - 1:30pm Lunch
1:30pm - 1:55pm Session 10

1:30pm - 1:55pm Nearest Common Ancestors: A survey and a new distributed algorithm
S. Alstrup, C. Gavoille, H. Kaplan, T. Raulie

2:00pm - 2:25pm Algorithms for Fault-Tolerant Routing in Circuit Switched Networks
A. Bagchi, A. Chaudhary, P. Kolman, C. Scheideler

2:30pm - 2:55pm Parallel Dynamic Programming For Solving The String Editing Problem on a CGM/BSP
C. E. R. Alves, E. N. Caceres, F. Dehne, S. W. Song

3:00pm - 3:25pm Heuristics for Semi-External Depth First Search on Directed Graphs
J. F. Sibeyn, J. Abello, U. C. Meyer

3:25pm END. See you next year

This page maintained by Cindy Phillips.

Last modified: July 10, 2002

9:45am - 10:15am	Continental Breakfast
10:15am - 10:30am	Opening Remarks
10:30am - 11:55am	Session 1
10:30am - 10:55am	Worst-case Traffic for Oblivous Routing Functions B. Towles, W. J. Dally
11:00am - 11:25am	Locality-Preserving Randomized Oblivious Routing on Torus Networks A. Singh, W. Dally, B. Towles, A. K. Gupta
11:30am - 11:55am	~O(Congestion + Dilation) Hot-Potato Routing on Leveled Networks C. Busch
12:00pm - 1:30pm	Lunch
1:30pm - 2:30pm	Keynote Address Andrew Chien, Entropia U. California, San Diego
2:30pm - 2:45pm	break
2:45pm - 4:10pm	Session 2
2:45pm - 3:10pm	Distributed Caching Independent of the Network Size M. Westermann
3:15pm - 3:40pm	Distribted Data Location in a Dynamic Network K. Hildrum, J. D. Kubiatowicz, S. Rao, B. Y. Zhao
3:45pm - 4:10pm	Compact, adaptive placement schemes for non-uniform distribution requirements A. Brinkmann, K. Salzwedel, C. Scheideler
4:10pm - 4:30pm	Break
4:30pm - 5:55pm	Session 3
4:30pm - 4:55pm	Distributed Streams Algorithms for Sliding Windows P. B. Gibbons, S. Tirthapura
5:00pm - 5:25pm	High Performance Dynamic Lock-Free Hash Tables and List-Based Sets M. M. Michael
5:30pm - 5:55pm	Scalability and Resource Usage of an OLAP Benchmark on Clusters of PCs M. Taufer, T. Stricker, R. Weber
8pm - 10pm	Business Meeting

8:00am - 8:30am	Continental Breakfast
8:30am - 9:55am	Session 4
8:30am - 8:55am	Two Techniques for Reconciling Algorithm Parallelism with Memory Constraints U. Vishkin
9:00am - 9:25am	A General Compiler Framework for Speculative Multithreading A. Bhowmik, M. Franklin
9:30am - 9:55am	Optimal Organizations for Pipelined Hierarchical Memories G. Bilardi, K. Ekanadham, P. Pattnaik
9:55am - 10:15am	Break
10:15am - 11:40am	Session 5
10:15am - 10:40am	Scheduling Reductions on Realistic Machines Gautam , S. Rajopadhye, P. Quinton
10:45am - 11:10am	Two Processor Scheduling with Real Release Times and Deadlines H. Wu, J. Jaffar
11:15 - 11:40pm	Extra Processors versus Future Information in Optimal Deadline Scheduling C.Y. Koo, T.W. Lam, J. Ngan, K.K. To
11:40pm - 1:00pm	Lunch
1:00pm - 2:00pm	SPAA Revue
1:00pm - 1:10pm	The Lazy Adversary Conjecture Fails E. Peserico
1:10pm - 1:20pm	AT^2L^2 = N^2/2 for Fast Fourier Transform in Multilayer VLSI C.-H. Yeh
1:20pm - 1:30pm	Rapid Prototyping Methodology For multi-DSP TI C6X Platforms J.F. Nezan, O. Deforges, M. Raulet
1:30pm - 1:40pm	Energy Estimation of Nested Loop Programs F. Hannig, J. Teich
1:40pm - 1:50pm	Sequential Consistency as Lazy Linearizability M. Raynal
1:50pm - 2:00pm	Vector Clocks, Constraint Graphs, and Verification of Memory Consistency Models H. W. Cain, M. H. Lipasti
2:00pm - 2:20pm	Break
2:20pm - 3:45pm	Session 6
2:20pm - 2:45pm	Exploiting Flexibly Assignable Work to Improve Load Balance A.Pinar, B. Hendrickson
2:50pm - 3:15pm	Work Dealing D. Hendler, N. Shavit
3:20pm - 3:45pm	Optimal tiling for the RNA base pairing problem F. Almeida, R. Andonov, D. Gonzolez, L.M. Moreno, V. Poirriez, C. Rodriguez
3:45pm - 4:05pm	Break
4:05pm - 5:00pm	Session 7
4:05pm - 4:30pm	Universal stability of undirected graphs in the adversarial queueing model C. Alvarez, M. Blesa, M. Serna
4:35pm - 5:00pm	New Stability Results for Adversarial Queuing Z. Lotker, B. Patt-Shamir, A. Rosen
5:30pm - 11:00pm (approx)	Outing to Folklorama

8:30am - 9:00am	Continental Breakfast
9:00am - 10:25am	Session 8
9:00am - 9:25am	Capture of an Intruder by Mobile Agents L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro
9:30am - 9:55am	Tracking Immediate Predecessors in Distributed Computations E. Anceaume, J.-M. Helary, M. Raynal
10:00am - 10:25am	Gossiping to Reach Consensus B. S. Chlebus, D. R. Kowalski
10:25am - 10:45am	Break
10:45am - 12:10pm	Session 9
10:45am - 11:10am	Energy, Congestion, and Dilation in Radio Networks F. Meyer auf der Heide, C. Schindelhauer, K. Volbert, M. Grunewald
11:15am - 11:40am	Parallel Scheduling in Next Generation Wireless Networks L. Becchetti, S. Diggavi, S. Leonardi, A. Marchetti-Spaccamela, S. Muthukrishnan, T. Nandagopal, A. Vitaletti
11:45am - 12:10pm	A Lightweight Idempotent Messaging Protocol for Faulty Networks J. Brown, J.P. Grossman, T. Knight
12:10pm - 1:30pm Lunch
1:30pm - 1:55pm	Session 10
1:30pm - 1:55pm	Nearest Common Ancestors: A survey and a new distributed algorithm S. Alstrup, C. Gavoille, H. Kaplan, T. Raulie
2:00pm - 2:25pm	Algorithms for Fault-Tolerant Routing in Circuit Switched Networks A. Bagchi, A. Chaudhary, P. Kolman, C. Scheideler
2:30pm - 2:55pm	Parallel Dynamic Programming For Solving The String Editing Problem on a CGM/BSP C. E. R. Alves, E. N. Caceres, F. Dehne, S. W. Song
3:00pm - 3:25pm	Heuristics for Semi-External Depth First Search on Directed Graphs J. F. Sibeyn, J. Abello, U. C. Meyer
3:25pm	END. See you next year