SPAA 2011 Conference Program
Contents:
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