SPAA 2011 Conference Program


List of Accepted Papers

Regular papers:

Thomas Locher
Finding Heavy Distinct Hitters in Data Streams

Victor Pankratius and Ali-Reza Adl-Tabatabai
A Study of Transactional Memory vs. Locks in Practice

Guy Even and Moti Medina
Online Packet-Routing in Grids with Bounded Buffers

James Aspnes and Faith Ellen
Tight bounds for anonymous adopt-commit objects

Grey Ballard, James Demmel, Olga Holtz and Oded Schwartz
Graph Expansion and Communication Costs of Fast Matrix Multiplication

Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Vahid Liaghat
On a Local Protocol for Concurrent File Transfers

Susanne Albers, Antonios Antoniadis and Gero Greiner
On Multi-Processor Speed Scaling with Migration

Michael Goodrich
Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data

Cyril Gavoille and Christian Sommer
Sparse Spanners vs. Compact Routing

Martin Hoefer, Thomas Kesselheim and Berthold Voecking
Approximation Algorithms for Secondary Spectrum Auctions

Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna and Giuseppe Persiano
Convergence to Equilibrium of Logit Dynamics for Strategic Games

Thomas Erlebach, Tom Grant and Frank Kammer
Maximising Lifetime for Fault-Tolerant Target Coverage in Sensor Networks

Patrick Briest and Christoph Raupach
The Car Sharing Problem

Bastian Degener, Barbara Kempkes, Tobias Langner, Friedhelm Meyer Auf Der Heide, Peter Pietrzyk, and Roger Wattenhofer
A tight runtime bound for synchronous gathering of autonomous robots with limited visibility

Michael Sindelar, Ramesh Sitaraman and Prashant Shenoy
Sharing-Aware Algorithms for Virtual Machine Colocation

Martin Wimmer and Jesper Larsson Träff
Work-stealing for mixed-mode parallelism by deterministic team-building

Mohammadamin Fazli, Shayan Ehsani, Abbas Mehrabian, Sina Sadeghian Sadeghabad, Morteza Saghafian, Saber Shokatfadaee and Mohammadali Safari
On a Bounded Budget Network Creation Game

Yossi Azar, Aviv Nisgav and Boaz Patt-Shamir
Recommender Systems With Non-Binary Grades

Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald and Christian Scheideler
Stabilizing Consensus with the Power of Two Choices

Umut Acar, Andrew Cotter, Benoît Hudson and Duru Türkoglu
Parallelism in Dynamic Well-Spaced Point Sets

Yuan Tang, Rezaul Chowdhury, Bradley Kuszmaul, Chi-Keung Luk and Charles Leiserson
The Pochoir Stencil Compiler

Peter Kling and Friedhelm Meyer Auf Der Heide
Convergence of Local Communication Chain Strategies via Linear Transformations

Panagiota Fatourou and Nikolaos Kallimanis
A Highly-Efficient Wait-Free Universal Costruction

Victoria Caparros Cabezas and Phillip Stanley-Marbell
Parallelism and Data Movement Characterization of Contemporary Application Classes

Håkan Sundell, Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas
A Lock-Free Algorithm for Concurrent Bags

Guy Blelloch, Jeremy Fineman, Phillip Gibbons and Harsha Vardhan Simhadri
Scheduling Irregular Parallel Computations on Hierarchical Caches

Torvald Riegel, Patrick Marlier, Martin Nowack, Pascal Felber and Christof Fetzer
Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations

Sebastian Kniesburges, Christian Scheideler and Andreas Koutsopoulos
Re-Chord: A self-stabilizing Chord overlay network

Silvio Lattanzi, Benjamin Moseley, Siddharth Suri and Sergei Vassilvitskii
Filtering: A Method for Solving Graph Problems in MapReduce

Benjamin Moseley, Anirban Dasgupta, Ravi Kumar and Tamas Sarlos
On Scheduling in Map-Reduce and Flow-Shops

Guy Blelloch, Anupam Gupta, Ioannis Koutis, Gary Miller, Richard Peng and Kanat Tangwongsan
Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs

Edya Ladan-Mozes, I-Ting Lee and Dmitriy Vyukov
Location-Based Memory Barriers

Guy Blelloch, Richard Peng and Kanat Tangwongsan
Linear-Work Greedy Parallel Approximation Algorithms for Set Covering and Variants

Dave Dice, Virendra Marathe and Nir Shavit
Flat-Combining NUMA Locks

Mark C. Jeffrey and J. Gregory Steffan
Understanding Bloom Filter Intersection for Lazy Address-Set Disambiguation

Brief announcements:

Lei Li, Tianshi Chen, Yunji Chen, Ling Li, Cheng Qian and Weiwu Hu
Program Regularization in Verifying Memory Consistency

Francesco Versaci and Keshav Pingali
Processor Allocation for Optimistic Parallelization

Tyler Crain, Damien Imbs and Michel Raynal
Read invisibility, virtual world consistency and permissiveness are compatible

Michael Goodrich and Michael Mitzenmacher
Parallel and External-Memory Multimaps

H B Acharya and Mohamed Gouda
RedRem: A Parallel Redundancy Remover

Grey Ballard, Andrew Gearhart and James Demmel
Communication Bounds for Heterogeneous Architectures

Vincent Gramoli and Rachid Guerraoui
Transaction Polymorphism

Guillaume Aupy, Anne Benoit, Fanny Dufossé and Yves Robert
Reclaiming the energy of a schedule: models and algorithms

Bernadette Charron-Bost, Matthias Függer, Jennifer L. Welch and Josef Widder
Full Reversal Routing as a Linear Dynamical System

Youngjoon Jo and Milind Kulkarni
Locality-enhancing loop transformations for parallel tree traversal algorithms

Alejandro López-Ortiz and Alejandro Salinger
Paging for Multicore Processors

Mieszko Lis, Keun Sup Shim, Myong Hyon Cho, Christopher Fletcher, Omer Khan and Srinivas Devadas
A Computation Migration Architecture for Distributed Shared Memory Without Directories

David Dice
A Partitioned Ticket Lock

David Dice and Oleksandr Otenko
MultiLane : a concurrent blocking multiset

George Caragea and Uzi Vishkin
Better Speedups for Parallel Max-Flow