ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016


Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond

Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Preserving Happens-before in Persistent Memory

Joseph Izraelevitz, Hammurabi Mendes, Michael L. Scott

Brief Announcement: Preserving Happens-before in Persistent Memory

Details
Author Comments: Follow-on work appears as Linearizability of Persistent Memory Objects under a Full-System-Crash Failure Model,'' by Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. 30th International Symposium on Distributed Computing (DISC), Paris, France, September 2016. An extended version of the DISC paper is available as TR 999, Computer Science Department, University of Rochester, July 2016 (http://hdl.handle.net/1802/31255).
Discussion Comments: 0
Sharing: Not able to share produced artifacts
Verification: Authors have verified information

Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis

William E. Devanny, Michael T. Goodrich, Kristopher Jetviroj

Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Relaxed Byzantine Vector Consensus

Zhuolun Xiang, Nitin H. Vaidya

Brief Announcement: Relaxed Byzantine Vector Consensus

Details
Discussion Comments: 0
Verification: Authors have not verified information

Just Join for Parallel Ordered Sets

Guy E. Blelloch, Daniel Ferizovic, Yihan Sun

Just Join for Parallel Ordered Sets

Details
Discussion Comments: 0
Verification: Authors have not verified information

Parallel Shortest Paths Using Radius Stepping

Guy E. Blelloch, Yan Gu, Yihan Sun, Kanat Tangwongsan

Parallel Shortest Paths Using Radius Stepping

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Transactional Data Structure Libraries

Alexander Spiegelman, Guy Golan-Gueta, Idit Keidar

Brief Announcement: Transactional Data Structure Libraries

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Practical Solution to the Cactus Stack Problem

Chaoran Yang, John M. Mellor-Crummey

A Practical Solution to the Cactus Stack Problem

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced artifacts
Verification: Authors have verified information

Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow Time

Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley

Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow Time

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

Sungjin Im, Maryam Shadloo

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines

Sungjin Im, Janardhan Kulkarni

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines

Details
Discussion Comments: 0
Verification: Authors have not verified information

General Profit Scheduling and the Power of Migration on Heterogeneous Machines

Sungjin Im, Benjamin Moseley

General Profit Scheduling and the Power of Migration on Heterogeneous Machines

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

Kamal Al-Bawani, Matthias Englert, Matthias Westermann

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

Details
Discussion Comments: 0
Verification: Authors have not verified information

Asymptotically Optimal Gathering on a Grid

Andreas Cord-Landwehr, Matthias Fischer, Daniel Jung, Friedhelm Meyer auf der Heide

Asymptotically Optimal Gathering on a Grid

Details
Discussion Comments: 0
Verification: Authors have not verified information

Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers

David Dinh, Harsha Vardhan Simhadri, Yuan Tang

Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Better Bounds for Coalescing-Branching Random Walks

Michael Mitzenmacher, Rajmohan Rajaraman, Scott T. Roche

Better Bounds for Coalescing-Branching Random Walks

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Multicore Path to Connectomics-on-Demand

Nir Shavit

A Multicore Path to Connectomics-on-Demand

Details
Discussion Comments: 0
Verification: Author has not verified information

Brief Announcement: Dynamic Determinacy Race Detection for Task Parallelism with Futures

Rishi Surendran, Vivek Sarkar

Brief Announcement: Dynamic Determinacy Race Detection for Task Parallelism with Futures

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Improved Approximation Algorithms for Scheduling Co-Flows

Samir Khuller, Manish Purohit

Brief Announcement: Improved Approximation Algorithms for Scheduling Co-Flows

Details
Discussion Comments: 0
Verification: Authors have not verified information

Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

Anat Bremler-Barr, Yotam Harchol, David Hay, Yacov Hel-Or

Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Mingmou Liu, Xiaoyin Pan, Yitong Yin

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Details
Discussion Comments: 0
Verification: Authors have not verified information

Latency-Hiding Work Stealing: Scheduling Interacting Parallel Computations with Work Stealing

Stefan K. Muller, Umut A. Acar

Latency-Hiding Work Stealing: Scheduling Interacting Parallel Computations with Work Stealing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling

Timothy Carpenter, Fabrice Rastello, P. Sadayappan, Anastasios Sidiropoulos

Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Power of Migration in Online Machine Minimization

Lin Chen, Nicole Megow, Kevin Schewior

The Power of Migration in Online Machine Minimization

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets

Amihood Amir, Oren Kapah, Tsvi Kopelowitz, Moni Naor, Ely Porat

The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables

William Kuszmaul

Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables

Details
Discussion Comments: 0
Verification: Author has not verified information

Universal Shape Formation for Programmable Matter

Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann

Universal Shape Formation for Programmable Matter

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Cost of Unknown Diameter in Dynamic Networks

Haifeng Yu, Yuda Zhao, Irvan Jahja

The Cost of Unknown Diameter in Dynamic Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs

Robert Utterback, Kunal Agrawal, Jeremy T. Fineman, I-Ting Angelina Lee

Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast and Robust Memory Reclamation for Concurrent Data Structures

Oana Balmau, Rachid Guerraoui, Maurice Herlihy, Igor Zablotchi

Fast and Robust Memory Reclamation for Concurrent Data Structures

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: MIC++: Accelerating Maximal Information Coefficient Calculation with GPUs and FPGAs

Chao Wang, Xi Li, Aili Wang, Xuehai Zhou

Brief Announcement: MIC++: Accelerating Maximal Information Coefficient Calculation with GPUs and FPGAs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation)

Tim Roughgarden, Sergei Vassilvitskii, Joshua R. Wang

Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation)

Details
Discussion Comments: 0
Verification: Authors have not verified information

Parallelism in Randomized Incremental Algorithms

Guy E. Blelloch, Yan Gu, Julian Shun, Yihan Sun

Parallelism in Randomized Incremental Algorithms

Details
Discussion Comments: 0
Verification: Authors have not verified information

Cache-Adaptive Analysis

Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, Samuel McCauley

Cache-Adaptive Analysis

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast Distributed Algorithms for Connectivity and MST in Large Graphs

Gopal Pandurangan, Peter Robinson, Michele Scquizzato

Fast Distributed Algorithms for Connectivity and MST in Large Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications

Qiang-Sheng Hua, Haoqiang Fan, Lixiang Qian, Ming Ai, Yangyang Li, Xuanhua Shi, Hai Jin

Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Energy Optimization of Memory Intensive Parallel Workloads

Chhaya Trehan, Hans Vandierendonck, Georgios Karakonstantis, Dimitrios S. Nikolopoulos

Brief Announcement: Energy Optimization of Memory Intensive Parallel Workloads

Details
Discussion Comments: 0
Verification: Authors have not verified information

Extending TM Primitives using Low Level Semantics

Mohamed M. Saad, Roberto Palmieri, Ahmed Hassan, Binoy Ravindran

Extending TM Primitives using Low Level Semantics

Details
Discussion Comments: 0
Verification: Authors have not verified information

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures

Mohsen Ghaffari, Merav Parter

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures

Details
Discussion Comments: 0
Verification: Authors have not verified information

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Tudor David, Rachid Guerraoui

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Details
Discussion Comments: 0
Verification: Authors have not verified information

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks

Dmitriy Katz, Baruch Schieber, Hadas Shachnai

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Parallel Algorithms for Summing Floating-Point Numbers

Michael T. Goodrich, Ahmed Eldawy

Parallel Algorithms for Summing Floating-Point Numbers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

Maximilian Drees, Robert Gmyr, Christian Scheideler

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

Details
Discussion Comments: 0
Verification: Authors have not verified information

Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford

Stephan Friedrichs, Christoph Lenzen

Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford

Details
Discussion Comments: 0
Verification: Authors have not verified information

Parallel Algorithms for Asymmetric Read-Write Costs

Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, Julian Shun

Parallel Algorithms for Asymmetric Read-Write Costs

Details
Discussion Comments: 0
Verification: Authors have not verified information

RUBIC: Online Parallelism Tuning for Co-located Transactional Memory Applications

Amin Mohtasham, João Pedro Barreto

RUBIC: Online Parallelism Tuning for Co-located Transactional Memory Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

Robust and Probabilistic Failure-Aware Placement

Madhukar R. Korupolu, Rajmohan Rajaraman

Robust and Probabilistic Failure-Aware Placement

Details
Discussion Comments: 0
Verification: Authors have not verified information

Investigating the Performance of Hardware Transactions on a Multi-Socket Machine

Trevor Brown, Alex Kogan, Yossi Lev, Victor Luchangco

Investigating the Performance of Hardware Transactions on a Multi-Socket Machine

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Computational Thinking, Inferential Thinking and Data Science

Michael I. Jordan

On Computational Thinking, Inferential Thinking and Data Science

Details
Discussion Comments: 0
Verification: Author has not verified information

Parallel Approaches to the String Matching Problem on the GPU

Saman Ashkiani, Nina Amenta, John D. Owens

Parallel Approaches to the String Matching Problem on the GPU

Details
Discussion Comments: 0
Verification: Authors have not verified information

Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?

Avery Miller, Andrzej Pelc

Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?

Details
Discussion Comments: 0
Verification: Authors have not verified information

Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time

Runtian Ren, Xueyan Tang

Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Brief Announcement: Benchmarking Concurrent Priority Queues

Jakob Gruber, Jesper Larsson Träff, Martin Wimmer

Brief Announcement: Benchmarking Concurrent Priority Queues

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lock-free Transactions without Rollbacks for Linked Data Structures

Deli Zhang, Damian Dechev

Lock-free Transactions without Rollbacks for Linked Data Structures

Details
Discussion Comments: 0
Verification: Authors have not verified information