Search

An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future decisions of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future decisions, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, providing evidence that there are no local impossibility proofs for these tasks. • Studies impossibility proofs for sub-consensus tasks in wait-free shared-memory. • Locally-solvable valency tasks capture the FLP strategy for proving impossibility results. • Presents locally-solvable valency tasks for set consensus, weak symmetry breaking and renaming. • This explains why there are no FLP-style proofs for the impossibility of solving these tasks. [ABSTRACT FROM AUTHOR]

Data-intensive computing frameworks typically split job workload into fixed-size chunks, allowing them to be processed as parallel tasks on distributed machines. Ideally, when the machines are homogeneous and have identical speed, chunks of equal size would finish processing at the same time. However, such determinism in processing time cannot be guaranteed in practice. Diverging processing times can result from various sources such as system dynamics, machine heterogeneity, and variable network conditions. Such variation, together with dynamics and uncertainty during task processing, can lead to significant performance degradation at job level, due to long tails in job completion time resulted from residual chunk workload and stragglers. In this paper, we propose Forseti , a novel processing scheme that is able to reshape data chunk size on the fly with respect to heterogeneous machines and a dynamic execution environment. Forseti mitigates residual workload and stragglers to achieve significant improvement in performance. We note that Forseti is a fully online scheme and does not require any a priori knowledge of the machine configuration nor job statistics. Instead, it infers such information and adjusts data chunk sizes at runtime, making the solution robust even in environments with high volatility. In its implementation, Forseti also exploits a virtual machine reuse feature to avoid task start-up and initialization cost associated with launching new tasks. We prototype Forseti on a real-world cluster and evaluate its performance using several realistic benchmarks. The results show that Forseti outperforms a number of baselines, including default Hadoop by up to 68% and SkewTune by up to 50% in terms of average job completion time. • Forseti enables efficient data processing by reshaping data chunk sizes on the fly. • Forseti mitigates residual workload and stragglers to improve performance. • Forseti does not require any a priori knowledge. • Forseti infers tasks statistics and adjusts data chunk sizes at runtime. • Forseti exploits a virtual machine reuse feature to avoid task start-up time. [ABSTRACT FROM AUTHOR]

• We analyze the first independent security analysis of PHEMAP, a PUF based protocol. • We present the first third party security analysis of Salted PHEMAP. • We propose two basic/salted PUF based mutual authentication protocols. • We analyze the security of the proposed schemes through formal and informal methods. Recently, using Physical Unclonable Functions (PUF) to design lightweight authentication protocols for constrained environments such as the Internet of Things (IoT) has received much attention. In this direction, Barbareschi et al. recently proposed PHEMAP in Journal of Parallel and Distributed Computing , a PUF based mutual authentication protocol. Also, they extended it to the later designed Salted PHEMAP, for low-cost cloud-edge (CE) IoT devices. This paper presents the first third-party security analysis of PHEMAP and Salted PHEMAP to the best of our knowledge. Despite the designer's claim, we show that these protocols are vulnerable to impersonation, de-synchronization, and traceability attacks. The success probability of the proposed attacks is '1', while the complexity is negligible. In addition, we introduce two enhanced lightweight authentication protocols based on PUF chains (called PBAP and Salted PBAP), using the same design principles as PHEMAP and Salted PHEMAP. With the performance evaluation and the security analysis, it is justified that the two proposed schemes are practically well suited for use in resource-constrained IoT environments. [ABSTRACT FROM AUTHOR]

Processing high-throughput data-streams has become a major challenge in areas such as real-time event monitoring, complex dataflow processing, and big data analytics. While there has been tremendous progress in distributed stream processing systems in the past few years, the high-throughput and low-latency (a.k.a. high sustainable-throughput) requirement of modern applications is pushing the limits of traditional data processing infrastructures. This paper introduces a new distributed stream processing engine (DSPE), called Asynchronous Iterative Routing (or simply "AIR"), which implements a light-weight, dynamic sharding protocol. AIR expedites direct and asynchronous communication among all the worker nodes via a channel-like communication protocol on top of the Message Passing Interface (MPI), thereby completely avoiding the need for a dedicated driver node. The system adopts a new progress-tracking protocol, called hew-meld , which has been experimentally observed to show a low processing latency on our asynchronous master-less architecture when compared to the conventional low-watermark technique. The current version of AIR is also equipped with two fault tolerance and recovery strategies namely checkpointing & rollback and replication. With its unique design, AIR scales out particularly well to multi-core HPC architectures; specifically, we deployed it on clusters with up to 16 nodes and 448 cores (thus reaching a peak of 435.3 million events and 55.14 GB of data processed per second), which we found to significantly outperform existing DSPEs. • A new open source distributed stream processing engine (DSPE), called Asynchronous Iterative Routing (or simply "AIR"), which implements a light-weight, dynamic sharding protocol. • With its unique design, AIR scales out particularly well to multi-core HPC architectures. • Specifically, we deployed it on clusters with up to 16 nodes and 448 cores (thus reaching a peak of 435.3 million events and 55.14 GB of data processed per second), which we found to significantly outperform existing DSPEs. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2. • Voronoi cell computation is an enabler for scaling to large graphs and seed sets. • Message prioritization accelerates convergence of distance computation. • Combining vertex- and edge- centric processing can bring forth superior performance. • 2-approx. MST can preserve the theoretical bound of a 2-approx. Steiner tree algo. [ABSTRACT FROM AUTHOR]