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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
A Practical Solution to the Cactus Stack Problem Chaoran Yang, John M. Mellor-Crummey	A Practical Solution to the Cactus Stack Problem Details	https://github.com/chaoran/fibril chaorany@me.com	Author Comments: Discussion Comments: 0 Sharing: Research produced artifacts Verification: Authors have verified information More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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	https://github.com/yotamhc/rene	Discussion Comments: 0 Verification: Authors have not verified information More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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	https://github.com/wustl-pctg/cracer	Author Comments: Discussion Comments: 0 Sharing: Research produced artifacts Verification: Authors have verified information More...
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	https://github.com/zablotchi/qsense	Author Comments: Discussion Comments: 0 Sharing: Research produced artifacts Verification: Authors have verified information More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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	http://github.com/LPD-EPFL/ASCYLIB	Discussion Comments: 0 Verification: Authors have not verified information More...
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 More...
Parallel Algorithms for Summing Floating-Point Numbers Michael T. Goodrich, Ahmed Eldawy	Parallel Algorithms for Summing Floating-Point Numbers Details	https://github.com/aseldawy/sumn	Discussion Comments: 0 Verification: Authors have not verified information More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
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 More...
Brief Announcement: Benchmarking Concurrent Priority Queues Jakob Gruber, Jesper Larsson Träff, Martin Wimmer	Brief Announcement: Benchmarking Concurrent Priority Queues Details	https://github.com/klsmpq/klsm	Discussion Comments: 0 Verification: Authors have not verified information More...
Lock-free Transactions without Rollbacks for Linked Data Structures Deli Zhang, Damian Dechev	Lock-free Transactions without Rollbacks for Linked Data Structures Details	http://cse.eecs.ucf.edu/gitlab/deli/transactional-linked-data-structure	Discussion Comments: 0 Verification: Authors have not verified information More...

ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016