| 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 |
| 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 |
| 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 |