TENTATIVE PROGRAM FOR
SPAA 2001

July 3, 2001, Tuesday

17:00 - 20:00 Registration
19:00 - 20:00 Reception

July 4, 2001, Wednesday

8:50 - 9:00 Opening Session
9:00 - 10:15 Session 1: Routing I
Chair: Pierre Fraigniaud, CNRS and U. Paris-Sud
9:00 - 9:25 Compact routing schemes
M. Thorup, U. Zwick
9:25 - 9:50 Routing without Flow Control
C. Busch, M. Herlihy, R. Wattenhofer
9:50 - 10:15 Fast, minimal, and Oblivious Routing Algorithms on the Mesh with Bounded Queues
A. Litman, S. Moran-Schein
10:15 - 10:35 Break
10:35 - 12:15 Session 2: Routing II
Chair: Friedhelm Meyer auf der Heide, U. Paderborn
10:35 - 11:00 One-to-Many Routing on the Mesh
K. Herley, A. Pietracaprina, G. Pucci
11:00 - 11:25 Simple On-line Algorithms for the Maximum Disjoint Paths Problem
P. Kolman, C. Scheideler
11:25 - 11:50 Competitive Buffer Management for Shared-Memory Switches
E. Hahne, A. Kesselman, Y. Mansour
11:50 - 14:00 Lunch
14:00 - 15:10 Session 3: SPAA Revue I
Chair: Guy Blelloch, CMU
14:00 - 14:10 D-CAT: A Distributed Channel Allocation Strategy Based on a Threshold Scheme for Cellular Mobile Networks
Y. Zhang, X. Jia, S. Das
14:10 - 14:20 A Note on Cycle Covering
J.-C. Bermond, L. Chacon, D. Coudert, F. Tillerot
14:20 - 14:30 Pursuit and Evasion on a Ring: An Infinite Hierarchy for Parallel Real-Time Systems
S. Bruda, S. Akl
14:30 - 14:40 Scheduling Tasks with Small Communication Delays for Clusters of Processors
E. Bampis, R. Giroudeau. A. Kononov
14:40 - 14:50 Library Support for Orthogonal Processor Groups
T. Rauber, R. Reilein, G. Ruenger
14:50 - 15:00 The Push Tree Problem
F. Havet and M. Wennink
15:00 - 15:10 Parallel Controlled Conspiracy Number Search
U. Lorenz
15:10 - 15:30 Break
15:30 - 17:10 Session 4: Networks
Chair: Christos Kaklamanis, CTI and U. of Patras
15:30 - 15:55 Tradeoffs Between Knowledge and Time of Communication in Geometric Radio Networks
A. Dessmark, A. Pelc
15:55 - 16:20 Attack Propagation in Networks
S. Nikoletseas, G. Prasinos, P. Spirakis, C. Zaroliagis
16:20 - 16:45 Deterministic Resource Discovery in Distributed Networks
S. Kutten, D. Peleg, U. Vishkin
16:45 - 17:10 Latency Effects on Reachability in Large-Scale Peer-to-Peer Networks
F. Annexstein, K. Berman, M. Jovanovic
19:00 - ? Business Meeting

July 5, 2001, Thursday

9:00 - 10:15 Session 5: Architecture and Programming Models
Chair: Nancy Amato, Texas A&M
9:00 - 9:25 Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach
D. Naishlos, J. Nuzman, C.-W. Tseng, U. Vishkin
9:25 - 9:50 A Cost Effective Architecture for Vectorizable Numerical and Multimedia Applications
F. Quintana, J. Corbal, R. Espasa, M. Valero
9:50 - 10:15 Automatable Verification of Sequential Consistency
A. Condon, A. Hu
10:15 - 10:35 Break
10:35 - 12:15 Session 6: Data Management and Program Control
Chair: Friedhelm Meyer auf der Heide, U. Paderborn
10:35 - 11:00 Room Synchronizations
G. Blelloch, P. Cheng, P. Gibbons
11:00 - 11:25 A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems
P. Tsigas, Y. Zhang
11:25 - 11:50 Computational Power of Pipelined Memory Hierarchies
G. Bilardi, K. Ekanadham, P. Pattnaik
11:50 - 12:15 Optimal Semi-Oblique Tiling
R. Andonov, S. Balev, S. Rajopadhye, N. Yanev
12:15 - 14:00 Lunch
14:00 - 15:10 Session 7: SPAA Revue II
Chair: Nancy Amato, Texas A&M
14:00 - 14:10 On Tiling of Space-Time Mapped Loop Nests
M. Griebl
14:10 - 14:20 A Parallel Block Algorithm for Exact Triangularization of Rectangular Matrices
J.-G. Dumas, J.-L. Roch
14:20 - 14:30 Eventually Consistent Failure Detectors
M. Larrea, A. Fernandez, S. Arevalo
14:30 - 14:40 Finding Strongly Connected Components in Parallel in Particle Transport Sweeps
W. McLendon III, B. Hendrickson, S. Plimpton, L. Rauchwerger
14:40 - 14:50 A Work-Optimal CGM Algorithm for the LIS Problem
T. Garcia, J.-F. Myoupo, D. Seme
14:50 - 15:00 Modeling Weakly Consistent Memories with Locks
V. Luchangco
15:00 - 15:10 The Power of Duality for Prefetching and Sorting with Parallel Disks
D. Hutchinson, P. Sanders, J. Vitter
15:10 - 15:30 Break
15:30 - 16:45 Session 8: Parallel Discrete Algorithms
Chair:Vijaya Ramachandran, U. Texas
15:30 - 15:55 Finding Large Independent Sets of Hypergraphs in Parallel
H. Shachnai, A. Srinivasan
15:55 - 16:20 Columnsort Lives! An Efficient Out-of-Core Sorting Program
G. Chaudhry, T. Cormen, L. Wisniewski
16:20 - 16:45 Efficient Parallel Exponentiation in GF(2^n) Using Normal Basis Representations
M.-K. Lee, Y. Kim, K. Park, Y. Cho
21:00 - ? Banquet

July 6, 2001, Friday

8:30 - 10:10 Session 9: Scheduling
Chair:Guy Blelloch, CMU
8:30 - 8:55 Stability and Non-Stability of the FIFO Protocol
J.Diaz, D. Koukopoulos, S.Nikoletseas, M.Serna, P. Spirakis, D. Thilikos
8:55 - 9:20 Low-Contention Depth-First Scheduling of Parallel Computations with Write-Once Synchronization Variables
P. Fatourou
9:20 - 9:45 Scheduling on Hierarchical Clusters Using Malleable Tasks
P.-F. Dutot, D. Trystram
9:45 - 10:10 Scheduling Best-Effort and Real-Time Pipelined Applications on Time-Shared Clusters
Y. Zhang, A. Sivasubramaniam
10:10 - 10:30 Break
10:30 - 12:10 Session 10: Data Management
Chair: Phil Gibbons, Bell Labs
10:30 - 10:55 Optimal Prefetching and Caching for Parallel I/O Systems
M. Kallahalla, P. Varman
10:55 - 11:20 Ordering Disks for Double Erasure Codes
M. Cohen, C. Colbourn
11:20 - 11:45 Approximation Algorithms for Data Management in Networks
C. Krick, H. Raecke, M. Westermann
11:45 - 12:10 A Data Tracking Scheme for General Networks
R. Rajaraman, A. Richa, B. Voecking, G. Vuppuluri
12:10 - 14:00 Lunch
14:00 - 15:10 Session 11: Parallel Algorithms
Chair: Michel Cosnard, LORIA-INRIA
14:00 - 14:25 New Spectral Bounds on k-Partitioning of Graphs
R. Elsaesser, T. Luecking, B. Monien
14:25 - 14:50 Efficient Quantum Algorithms for Some Instances of the Non-Abelian Hidden Subgroup Problem
G. Ivanyos, F. Magniez, M. Santha
14:50 - 15:15 Towards Practical Determinstic Write-All Algorithms
B. Chlebus, S. Dobrev, D. Kowalski, G. Malewicz, A. Shvartsman, I. Vrto
15:15 - 15:40 Estimating Simple Functions on the Union of Data Streams
P. Gibbons, S. Tirthapura
15:40 - 16:00 Break
16:00 - 16:50 Session 12: Fault Tolerance
Chair: Pierre Fraigniaud, CNRS and U. Paris-Sud
16:00 - 16:25 Randomized k-Set Agreement
A. Mostefaoui, M. Raynal
16:25 - 16:50 Periodic, Random-Fault-Tolerant Correction Networks
M. Piotrow
16:50 END. See you next year
This page maintained by Cindy Phillips.

Last modified: June 11, 2001