SPAA 2009 Conference Program
Contents:
SPAA Best Paper Award:
Reducers and Other Cilk++ Hyperobjects
Matteo Frigo, Pablo Halpern, Charles E. Leiserson, and Stephen Lewin-Berlin
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
The SPAA program is available here.
Christian Scheideler
Last modified: June 19, 2009