Hadoop suffers from the issue of stragglers in which some tasks with unusual long execution time delay the whole job. Hadoop relieves the straggler problem by launching backup tasks, that are cloned from original task...
详细信息
ISBN:
(纸本)9781509043149
Hadoop suffers from the issue of stragglers in which some tasks with unusual long execution time delay the whole job. Hadoop relieves the straggler problem by launching backup tasks, that are cloned from original tasks and executed on server nodes different from those executing original tasks. A speculative algorithm is responsible for classifying straggler tasks and launching backup tasks. Although launching backup tasks can solve the problem, it requires additional resources to run. Existing algorithms wrongly classify and start many wasteful backup tasks, which reduces resource utilization. This paper proposes an algorithm called Accuracy Improvement for Backup Task (AIBT) in Hadoop speculative algorithm. In the AIBT algorithm, a task is divided into phases, and the execution time of the task is estimated from progress rates of the phases. Moreover, AIBT uses execution time information both from other finished tasks and its own to improve the accuracy of the estimated values by changing the weight dynamically. We implement the AIBT algorithm in Hadoop and evaluate its performance for four job types: Wordcount, KMean clustering, PageRank, and Inverted Index. Numerical results show that AIBT significantly reduces the number of unnecessary and wrong backup tasks compared with the existing algorithms.
Randomized Byzantine Consensus can be an interesting building block in the implementation of asynchronous distributed systems. Despite its exponential worst-case complexity, which would make it less appealing in pract...
详细信息
ISBN:
(纸本)9780769547848;9781467323970
Randomized Byzantine Consensus can be an interesting building block in the implementation of asynchronous distributed systems. Despite its exponential worst-case complexity, which would make it less appealing in practice, a few experimental works have argued quite the opposite. To bridge the gap between theory and practice, we analyze a well-known state-of-the-art algorithm in normal system conditions, in which crash failures may occur but no malicious attacks, proving that it is fast on average. We then leverage our analysis to improve its best-case complexity from three to two phases, by reducing the communication operations through speculative executions. Our findings are confirmed through an experimental validation.
In an adversarial environment, various kinds of attacks become possible if malicious nodes could claim fake locations that are different from their physical locations. In this paper, we propose a secure localization m...
详细信息
In an adversarial environment, various kinds of attacks become possible if malicious nodes could claim fake locations that are different from their physical locations. In this paper, we propose a secure localization mechanism that detects existence of these nodes, termed as phantom nodes, without relying on any trusted entities, ail approach significantly different from the existing ones. The proposed mechanism enjoys a set of nice features. First, it does not have my central point of attack. All nodes play the role of verifier, by generating local map, i.e. a view constructed based on ranging information from its neighbors. Second, this distributed and localized construction results in strong robustness against adversaries: even when the number of phantom nodes is greater than that of honest nodes, we can filter out most of the phantom nodes. Our analytical results as well as simulations under realistic noisy settings demonstrate that the proposed mechanism is effective in the presence of a large number of phantom nodes. (C) 2007 Elsevier B.V. All rights reserved.
Subresultant chains over rings of multivariate polynomials are calculated using a speculative approach based on the Bezout matrix. Our experimental results yield significant speedup factors for the proposed approach a...
详细信息
ISBN:
(数字)9783031147883
ISBN:
(纸本)9783031147883;9783031147876
Subresultant chains over rings of multivariate polynomials are calculated using a speculative approach based on the Bezout matrix. Our experimental results yield significant speedup factors for the proposed approach against comparable methods. The determinant computations are based on fraction-free Gaussian elimination using various pivoting strategies.
暂无评论