Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFaster Data-access in Large-scale Systems: Network-scale Latency Analysis under General Service-time Distributions
366
0
0.0
(
0
)
Added by
Avishek Ghosh
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In cloud storage systems with a large number of servers, files are typically not stored in single servers. Instead, they are split, replicated (to ensure reliability in case of server malfunction) and stored in different servers. We analyze the mean latency of such a split-and-replicate cloud storage system under general sub-exponential service time. We present a novel scheduling scheme that utilizes the load-balancing policy of the textit{power of $d$ $(geq 2)$} choices. An alternative to split-and-replicate is to use erasure-codes, and recently, it has been observed that they can reduce latency in data access (see cite{longbo_delay} for details). We argue that under high redundancy (integer redundancy factor strictly greater than or equal to 2) regime, the mean latency of a coded system is upper bounded by that of a split-and-replicate system (with same replication factor) and the gap between these two is small. We validate this claim numerically under different service distributions such as exponential, shift plus exponential and the heavy-tailed Weibull distribution and compare the mean latency to that of an unsplit-replicated system. We observe that the coded system outperforms the unsplit-replication system by at least $20%$. Furthermore, we consider the mean latency for an erasure coded system with low redundancy (fractional redundancy factor between 1 and 2), a scenario which is more pragmatic, given the storage constraints (cite{rashmi_thesis}). However under this regime, we restrict ourselves to the special case of exponential service time distribution and use the randomized load balancing policy namely textit{batch-sampling}. We obtain an upper bound on mean delay that depends on the order statistics of the queue lengths, which, we further smooth out via a discrete to continuous approximation.
rate research
Read More
Wireless blockchain network is proposed to enable a decentralized and safe wireless networks for various blockchain applications. To achieve blockchain consensus in wireless network, one of the important steps is to broadcast new block using wireless channel. Under wireless network protocols, the block transmitting will be affected significantly. In this work, we focus on the consensus process in blockchain-based wireless local area network (B-WLAN) by investigating the impact of the media access control (MAC) protocol, CSMA/CA. With the randomness of the backoff counter in CSMA/CA, it is possible for latter blocks to catch up or outpace the earlier one, which complicates blockchain forking problem. In view of this, we propose mining strategies to pause mining for reducing the forking probability, and a discard strategy to remove the forking blocks that already exist in CSMA/CA backoff procedure. Based on the proposed strategies, we design Block Access Control (BAC) approaches to effectively schedule block mining and transmitting for improving the performance of B-WLAN. Then, Markov chain models are presented to conduct performance analysis in B-WLAN. The results show that BAC approaches can help the network to achieve a high transaction throughput while improving block utilization and saving computational power. Meanwhile, the trade-off between transaction throughput and block utilization is demonstrated, which can act as a guidance for practical deployment of blockchain.
There is a growing interest in analysing the freshness of data in networked systems. Age of Information (AoI) has emerged as a popular metric to quantify this freshness at a given destination. There has been a significant research effort in optimizing this metric in communication and networking systems under different settings. In contrast to previous works, we are interested in a fundamental question, what is the minimum achievable AoI in any single-server-single-source queuing system for a given service-time distribution? To address this question, we study a problem of optimizing AoI under service preemptions. Our main result is on the characterization of the minimum achievable average peak AoI (PAoI). We obtain this result by showing that a fixed-threshold policy is optimal in the set of all randomized-threshold causal policies. We use the characterization to provide necessary and sufficient conditions for the service-time distributions under which preemptions are beneficial.
Graphs are widespread data structures used to model a wide variety of problems. The sheer amount of data to be processed has prompted the creation of a myriad of systems that help us cope with massive scale graphs. The pressure to deliver fast responses to queries on the graph is higher than ever before, as it is demanded by many applications (e.g. online recommendations, auctions, terrorism protection, etc.). In addition, graphs change continuously (so do the real world entities that typically represent). Systems must be ready for both: near real-time and dynamic massive graphs. We survey systems taking their scalability, real-time potential and capability to support dynamic changes to the graph as driving guidelines. The main techniques and limitations are distilled and categorised. The algorithms run on top of graph systems are not ready for prime time dynamism either. Therefore,a short overview on dynamic graph algorithms has also been included.
In cloud computing systems, assigning a task to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers, and reduce latency. But adding redundancy may result in higher cost of computing resources, as well as an increase in queueing delay due to higher traffic load. This work helps understand when and how redundancy gives a cost-efficient reduction in latency. For a general task service time distribution, we compare different redundancy strategies in terms of the number of redundant tasks, and time when they are issued and canceled. We get the insight that the log-concavity of the task service time creates a dichotomy of when adding redundancy helps. If the service time distribution is log-convex (i.e. log of the tail probability is convex) then adding maximum redundancy reduces both latency and cost. And if it is log-concave (i.e. log of the tail probability is concave), then less redundancy, and early cancellation of redundant tasks is more effective. Using these insights, we design a general redundancy strategy that achieves a good latency-cost trade-off for an arbitrary service time distribution. This work also generalizes and extends some results in the analysis of fork-join queues.
The large-scale data stream problem refers to high-speed information flow which cannot be processed in scalable manner under a traditional computing platform. This problem also imposes expensive labelling cost making the deployment of fully supervised algorithms unfeasible. On the other hand, the problem of semi-supervised large-scale data streams is little explored in the literature because most works are designed in the traditional single-node computing environments while also being fully supervised approaches. This paper offers Weakly Supervised Scalable Teacher Forcing Network (WeScatterNet) to cope with the scarcity of labelled samples and the large-scale data streams simultaneously. WeScatterNet is crafted under distributed computing platform of Apache Spark with a data-free model fusion strategy for model compression after parallel computing stage. It features an open network structure to address the global and local drift problems while integrating a data augmentation, annotation and auto-correction ($DA^3$) method for handling partially labelled data streams. The performance of WeScatterNet is numerically evaluated in the six large-scale data stream problems with only $25%$ label proportions. It shows highly competitive performance even if compared with fully supervised learners with $100%$ label proportions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
