SPAA 2009 Conference Program


SPAA Best Paper Award:

Reducers and Other Cilk++ Hyperobjects
Matteo Frigo, Pablo Halpern, Charles E. Leiserson, and Stephen Lewin-Berlin

List of Accepted Papers

Regular papers:

Matteo Frigo, Pablo Halpern, Charles E. Leiserson and Stephen Lewin-Berlin.
Reducers and Other Cilk++ Hyperobjects

MohammadHossein Bateni, Lukasz Golab, MohammadTaghi Hajiaghayi and Howard Karloff.
Scheduling to Minimize Staleness and Stretch in Real-Time Data Warehouses

Ho-Leung Chan, Jeff Edmonds and Kirk Pruhs.
Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

Matthias Baumgart, Christian Scheideler and Stefan Schmid.
A DoS-Resilient Information System for Dynamic Data Management

Patrik Floreen, Joel Kaasinen, Petteri Kaski and Jukka Suomela.
An optimal local approximation algorithm for max-min linear programs

Gero Greiner, Tim Nonner and Alexander Souza.
The Bell is Ringing in Speed-Scaled Multiprocessor Scheduling

Bernadette Charron-Bost, Antoine Gaillard, Jennifer Welch and Josef Widder.
Routing without Ordering

Grey Ballard, James Demmel, Olga Holtz and Oded Schwartz.
Communication-optimal Parallel and Sequential Cholesky decomposition

Zhewei Wei, Ke Yi and Qin Zhang.
Dynamic External Hashing: The Limit of Buffering

Heiner Ackermann, Simon Fischer, Martin Hoefer and Marcel Schöngens.
Distributed Algorithms for QoS Load Balancing

Kunal Agrawal, Anne Benoit, Fanny Dufosse and Yves Robert.
Mapping Filtering Streaming Applications With Communication Costs

Hagit Attiya, Eshcar Hillel and Alessia Milani.
Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory

Jan Mehler and Friedhelm Meyer auf der Heide.
Power-Aware Online File Allocation in Mobile Ad Hoc Networks

Srikanth Sastry, Scott Pike and Jennifer Welch.
The Weakest Failure Detector for Wait-free Dining Under Eventual Weak Exclusion

Harald Raecke and Adi Rosen.
Approximation Algorithms for Time-Constrained Scheduling on Line Networks

Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda and Prasad Raghavendra.
Buffer Management for Colored Packets with Deadlines

Marios Mavronicolas and Thomas Sauerwald.
A Randomized, O(log w)-Depth 2-Smoothing Network

Aydın Buluç, Jeremy T. Fineman, Matteo Frigo, John R. Gilbert and Charles E. Leiserson.
Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication Using Compressed Sparse Blocks

Michele Flammini, Alberto Marchetti Spaccamela, Gianpiero Monaco, Luca Moscardelli and Shmuel Zaks.
On the complexity of the Regenerator Placement Problem in Optical Networks

Pierre Fraigniaud and Amos Korman.
On Randomized Representations of Graphs Using Short Labels

Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Robert Geva, Yang Ni and Adam Welc.
Towards Transactional Memory Semantics for C++

Aviv Nisgav and Boaz Patt-Shamir.
Finding Similar Users in Social Networks

Cosmin E. Oancea, Alan Mycroft and Tim Harris.
A Lightweight In-Place Implementation for Software Thread-Level Speculation

Bogdan Chlebus and Dariusz R. Kowalski.
Locally scalable randomized consensus for synchronous crash failures

Arne Vater, Christian Schindelhauer and Christian Ortolf.
Classifying Peer-to-Peer Networking Coding Schemes

Yossi Lev, Victor Luchangco and Marek Olszewski.
Scalable Reader-Writer Locks (

Fuad Tabba, Mark Moir, James Goodman, Andrew Hay and Cong Wang.
NZTM: Nonblocking Zero-indirection Transactional Memory

Dmitri Perelman and Idit Keidar.
On Avoiding Spare Aborts in Transactional Memory

Aleksandar Dragojevic, Yang Ni and Ali-Reza Adl-Tabatabai.
Optimizing Transactions for Captured Memory

Fabian Kuhn.
Local Weak Coloring Algorithms and Implications on Deterministic Symmetry Breaking

Weirong Jiang and Viktor Prasanna.
Field-Split Parallel Architecture for High Performance Multi-Match Packet Classification Using FPGAs

Marcos Aguilera and Ram Swaminathan.
Remote storage with byzantine servers

Fabian Kuhn, Thomas Locher and Rotem Oshman.
Gradient Clock Synchronization in Dynamic Networks

Daniel Spoonhower, Guy E. Blelloch, Robert Harper and Phillip B. Gibbons.
Beyond Nested Parallelism: Tight Bounds on Work-Stealing Overheads for Parallel Futures

Koji Kobayashi, Shuichi Miyazaki and Yasuo Okabe.
Competitive Buffer Management for Multi-Queue Switches in QoS Networks using Packet Buffering Algorithms

Brief announcements:

Melih Onus and Andrea W. Richa.
Brief Announcement: Parameterized Maximum and Average Degrees in Topic-based Publish-Subscribe Overlay Network Design

Bradley Kuszmaul.
Brief Announcement: TeraByte TokuSampleSort Sorts 1TB in 197s

Raphael Eidenbenz and Roger Wattenhofer.
Brief Announcement: Good Programming in Transactional Memory: Game Theory Meets Multicore Architecture

Guy Blelloch, Phillip Gibbons and Harsha Vardhan Simhadri.
Brief Announcement: Low-Depth Cache-Oblivious Algorithms

James Levy, Anand Ganti, Cynthia Phillips, Benjamin Hamlet, Malcolm Carroll, Andrew Landahl, Thomas Gurrieri and Robert Carr.
Brief Announcement: The impact of classical electronics constraints on a solid-state logical qubit memory

Jim Sukha.
Brief Announcement: A Lower Bound on the Parallelism of Depth-Restricted Work Stealing

Sotirios Kentros, Aggelos Kiayias, Nicolas Nicolaou and Alexander Shvartsman.
Brief Announcement: At-Most-Once Semantics in Asynchronous Shared Memory

George Caragea, A. Beliz Saybasili, Xingzhi Wen and Uzi Vishkin.
Brief Announcement: Performance Potential of an Easy-to-Program PRAM-On-Chip Prototype Versus State-of-the-Art Processor

Conference Program

The SPAA program is available here.

Christian Scheideler
Last modified: June 19, 2009