Parallel Computing (TOPC)


Search Issue
enter search term and/or author name


ACM Transactions on Parallel Computing (TOPC) - Special Issue for SPAA 2013, Volume 2 Issue 3, October 2015

Section: Special Issue for SPAA 2013

Introduction to the Special Issue on SPAA 2013
Michael Dinitz, Torsten Hoefler
Article No.: 14e
DOI: 10.1145/2809923

Fast Greedy Algorithms in MapReduce and Streaming
Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, Andrea Vattani
Article No.: 14
DOI: 10.1145/2809814

Greedy algorithms are practitioners’ best friends—they are intuitive, are simple to implement, and often lead to very good solutions. However, implementing greedy algorithms in a distributed setting is challenging since the greedy...

Work-Efficient Matrix Inversion in Polylogarithmic Time
Peter Sanders, Jochen Speck, Raoul Steffen
Article No.: 15
DOI: 10.1145/2809812

We present an algorithm for inversion of symmetric positive definite matrices that combines the practical requirement of an optimal number of arithmetic operations and the theoretical goal of a polylogarithmic critical path length. The algorithm...

SybilCast: Broadcast on the Open Airwaves
Seth Gilbert, Chaodong Zheng
Article No.: 16
DOI: 10.1145/2809810

Consider a scenario where many wireless users are attempting to download data from a single base station. While most of the users are honest, some users may be malicious and attempt to obtain more than their fair share of the bandwidth. One...

On-the-Fly Pipeline Parallelism
I-Ting Angelina Lee, Charles E. Leiserson, Tao B. Schardl, Zhunping Zhang, Jim Sukha
Article No.: 17
DOI: 10.1145/2809808

Pipeline parallelism organizes a parallel program as a linear sequence of stages. Each stage processes elements of a data stream, passing each processed data element to the next stage, and then taking on a new element before the subsequent stages...

IRIS: A Robust Information System Against Insider DoS Attacks
Martina Eikel, Christian Scheideler
Article No.: 18
DOI: 10.1145/2809806

In this work, we present the first scalable distributed information system, that is, a system with low storage overhead, that is provably robust against denial-of-service (DoS) attacks by a current insider. We allow a current insider to have...

Profitable Scheduling on Multiple Speed-Scalable Processors
Peter Kling, Peter Pietrzyk
Article No.: 19
DOI: 10.1145/2809872

We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors and provide a tight analysis of the algorithm’s competitiveness. Our results generalize and improve upon work by Chan et al. [2010], which...

Coalescing-Branching Random Walks on Graphs
Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Scott Roche
Article No.: 20
DOI: 10.1145/2817830

We study a distributed randomized information propagation mechanism in networks we call the coalescing-branching random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied “standard” random walk,...