SPAA 2008 Conference Program

List of Accepted Papers

Regular papers:

Guy Blelloch, Phillip Gibbons and S. Harsha Vardhan.
Combinable Memory-Block Transactions

Moses Charikar, Howard Karloff, Claire Mathieu, Seffi Naor and Michael Saks.
Online Multicast with Egalitarian Cost Sharing

Noga Alon, Chen Avin, Michal Koucky, Gady Kozma, Zvi Lotker and Mark R. Tuttle.
Many Random Walks Are Faster Than One

Zvi Lotker, Boaz Patt-Shamir and Seth Pettie.
Improved Distributed Approximate Matching

Christoph Lenzen, Yvonne Anne Oswald and Roger Wattenhofer.
What Can Be Approximated Locally?

Ioannis Koutis and Gary Miller.
Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning

Mauro Sozio and Alessandro Panconesi.
Fast Distributed Scheduling via Primal-Dual

Ioannis Caragiannis, Christos Kaklamanis, Evangelos Kranakis, Danny Krizanc and Andreas Wiese.
Communication in wireless networks with directional antennas

Vijay Menon, Steven Balensiefer, Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Richard Hudson, Bratin Saha and Adam Welc.
Practical Weak-Atomicity Semantics for Java STM

Baruch Awerbuch and Rohit Khandekar.
Cost Sharing Mechanisms for Near-Optimal Traffic Aggregation and Network Design

Warren Schudy.
Finding Strongly Connected Components in Parallel using O(log^2 n) Reachability Queries

Pierre Fraigniaud and Cyril Gavoille.
Polylogarithmic Network Navigability Using Compact Metrics with Small Stretch

Christopher Crutchfield, Zoran Dzunic, Jeremy Fineman, David Karger and Jacob Scott.
Improved Approximations for Multiprocessor Scheduling Under Uncertainty

Hagit Attiya, Rachid Guerraoui and Eric Ruppert.
Partial Snapshot Objects

Emanuele Guido Fusco and Andrzej Pelc.
Trade-offs Between the Size of Advice and Broadcasting Time in Trees

Rui Zhang, Zoran Budimlic and William Scherer.
Commit Phase in Timestamp-based STM

Tak-Wah Lam, Lap Kei Lee, Isaac K.K. To and Prudence W.H. Wong.
Competitive Non-migratory Scheduling for Flow Time and Energy

Michal Hanckowiak, Andrzej Czygrinow and Wojciech Wawrzyniak.
Distributed packing in planar graphs

Cyril Gavoille and Andy Twigg.
Compact Forbidden-set Routing on Planar Graphs

Wing Kai Hon, Rahul Shah, Peter Varman and Jeffrey Scott Vitter.
Tight Competitive Ratios for Parallel Disk Prefetching and Caching

Yaacov Fernandess and Dahlia Malkhi.
On Spreading Recommendations via Social Gossip

Rachid Guerraoui and Michal Kapalka.
On Obstruction-Free Transactions

Indrajit Roy and Nedialko Dimitrov.
A Primal-Dual Resource Augmentation Analysis of a Constant Approximate Algorithm for Stable Coalitions in a Cluster

Special track papers:

Adam Welc, Bratin Saha and Ali-Reza Adl-Tabatabai.
Irrevocable Transactions and their Applications

Edya Ladan Mozes and Charles Leiserson.
A Consistency Architecture for Hierarchical Shared Caches

Michael Spear, Maged Michael and Christoph von Praun.
RingSTM: Scalable Transactions with a Single Atomic Instruction

Torvald Riegel, Christof Fetzer and Pascal Felber.
Automatic Data Partitioning in Software Transactional Memories

Olatunji Ruwase, Phillip Gibbons, Todd Mowry, Vijaya Ramachandran, Shimin Chen, Michael Kozuch and Michael Ryan.
Parallelizing Dynamic Information Flow Tracking

Rezaul Chowdhury and Vijaya Ramachandran.
Cache-efficient Dynamic Programming Algorithms for Multicores

Lars Arge, Michael T. Goodrich, Michael Nelson and Nodari Sitchinava.
Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors

Zvika Guz, Idit Keidar, Avinoam Kolodny and Uri C. Weiser.
Utilizing Shared Data in Chip Multiprocessors with the Nahalal Architecture

Eric Koskinen and Maurice Herlihy.
Dreadlocks: Efficient Deadlock Detection

Eric Koskinen and Maurice Herlihy.
Checkpoints and Continuations instead of Nested Transactions

Milind Kulkarni, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Patrick Carribault, Paul Chew and Kavita Bala.
Scheduling Strategies for Optimistic Parallel Execution of Irregular Programs

Richard Yoo and Hsien-Hsin Lee.
Adaptive Transaction Scheduling for Transactional Memory Systems

Richard Yoo, Yang Ni, Adam Welc, Bratin Saha, Ali-Reza Adl-Tabatabai and Hsien-Hsin Lee.
Kicking the Tires of Software Transactional Memory: Why the Going Gets Tough

Brief announcements:

Kai Shen, Alex Zhang, Terence Kelly and Chris Stewart.
Operational Analysis of Processor Speed Scaling

Kunal Agrawal, ITing Lee and Jim Sukha.
Safe Open-Nested Transactions Through Ownership

Daniel Greenfield and Simon Moore.
Fractal Communication in Software Data Dependency Graphs

Xiongfei Liao, Wu Jigang and Thambipillai Srikanthan.
A Temperature-Aware Virtual Submesh Allocation Scheme for NoC-based Manycore Chips

Reza Dorrigiv, Alejandro Lopez-Ortiz and Alejandro Salinger.
Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)

Amitabha Roy, Keir Fraser and Steven Hand.
A Transactional Approach to Lock Scalability

Shantanu Gupta, Florin Sultan, Srihari Cadambi, Franjo Ivancic and Martin Roetteler.
RaceTM: Detecting Data Races Using Transactional Memory

Behram Khan, Matthew Horsnell, Ian Rogers, Mikel Lujan, Andrew Dinn and Ian Watson.
An Object Based Hardware Transactional Memory System

Andre Brinkmann and Sascha Effert.
Data Replication in P2P Environments

Torsten Hoefler, Peter Gottschling and Andrew Lumsdaine.
Leveraging non-blocking collective communication in high-performance applications

Yongwook Choi, Maleq Khan, Anil Kumar and Gopal Pandurangan.
Work-Efficient Distributed Euclidean Minimum Spanning Tree

Victor Luchangco.
Against Lock-Based Semantics for Transactional Memory

Vittorio Bilo, Angelo Fanelli, Michele Flammini and Luca Moscardelli.
Graphical Congestion Games with Linear Latencies

Posters:

Mark Moir, Kevin Moore and Dan Nussbaum.
The Adaptive Transactional Memory Test Platform

Jaewoong chung, Jiwon seo, Woongki Baek, Chi Cao Minh, Christos Kozyrakis and kunle Olukotun.
Improving Software Concurrency with Hardware-assisted memory Snapshot

Waleed Alsalih, Md. Kamrul Islam, Yurai Nunez Rodriguez and Henry Xiao.
Distributed Voronoi diagram computation in wireless sensor networks

Fei Wei and Huazhong Yang.
Directed Transmission Method, a Fully Asynchronous Approach to Solve Sparse Linear Systems in Parallel

Jaewoong chung, Woongki Baek, Nathan Bronson, Jiwon Seo, Christos Kozyrakis and Kunle Olukotun.
ASeD: Availability, Security, and Debugging Support using Transactional Memory

Conference Program

The conference program can be downloaded in pdf and txt format.

Christian Scheideler

Last modified: September 27, 2007