Search

The matroidal connectivity and conditional matroidal connectivity are novel indicators to measure the real faulty tolerability. In this paper, for the $n$ n -dimensional alternating group graph $AG_{n}$ A G n , the structure properties and (conditional) matroidal connectivity are studied based on the dimensional partition of $E(AG_{n})$ E (A G n) . We prove that for $S\subseteq E(AG_{n})$ S ⊆ E (A G n) under some limitation on the number of faulty edges in each dimensional edge set, if $|S|\leq (n-1)!-1$ | S | ≤ (n - 1) ! - 1 , then $AG_{n}-S$ A G n - S is connected. We study the value of matroidal connectivity and conditional matroidal connectivity of $AG_{n}$ A G n . Furthermore, simulations have been carried out to compare the matroidal connectivity with other types of conditional connectivity in $AG_{n}$ A G n . The simulation result shows that the matroidal connectivity significantly improves these known fault-tolerant capability of alternating group graphs. [ABSTRACT FROM AUTHOR]

We study the embedding of Hamiltonian cycle in the Crossed Cube, which is a prominent variant of the classical hypercube, obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and the algorithm proposed in this paper can find their way when system designers evaluate a candidate network's competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network. [ABSTRACT FROM AUTHOR]

Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest subcomputation (with the least number of consistent cuts) that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are actually equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b. The time complexity of the (derived) slicing algorithm is O(n∣E∣T), where n is the number of processes, E is the set of events, and O(T) is the time complexity of the detection algorithm. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the genera/predicate detection problem in many cases. Slicing algorithms described in our earlier papers are all offline in nature. In this paper, we also present two online algorithms for computing the slice. The first algorithm can be used to compute the slice for a general predicate. Its amortized time complexity is O(n(c+n)T) per event, where c is the average concurrency in the computation and O(T) is the time complexity of the detection algorithm. The second algorithm can be used to compute the slice for a regular predicate. Its amortized time complexity is only O(n2) per event. [ABSTRACT FROM AUTHOR]

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice. [ABSTRACT FROM AUTHOR]

In this paper, we explore potential correlations of fatal system events for one of the most powerful supercomputers—IBM Blue Gene/Q Mira, which is deployed at Argonne National Laboratory, based on its 5-year reliability, availability, and serviceability (RAS) log. Our contribution is two-fold. (1) We design an efficient log analysis tool, namely LogAider, with a novel filtering method to effectively extract fatal events from masses of system messages that are heavily duplicated in the log. LogAider exhibits a very precise detection of temporal-correlation with a high similarity (up to 95 percent) to the ground-truth (i.e., compared to the failure records reported by the administrators). The total number of fatal events can be reduced to about 1,255 compared with originally 2.6 million duplicated fatal messages. (2) We analyze the 5-year RAS log of the MIRA system using LogAider, and summarize six important “takeaways” which can help system vendors and administrators better understand an extreme-scale system's fatal events. Specifically, we find that the distribution or proportion of the fatal system events follow a Pareto-like principle in general. The temporal correlation among fatal events is much stronger than that of warn messages and info messages, and the correlated events tend to constitute a few clusters. The mean time between fatal events (MTBFE) of the Mira system is about 1.3 days from the perspective of the system, and the MTTI is 2–4 days from the perspective of users. The most error-prone item value with respect to any key attribute appears likely in the log every 2–10 days. Weibull, Gamma, and Pearson6 are the three best-fit distributions for the fatal event intervals. The overall correlation of fatal events on the 5D torus network is not prominent, whereas the small-region locality correlation (e.g., the fatal events inside racks) is relatively strong. We believe our work will be interesting to large-scale HPC system administrators and vendors and to fault tolerance researchers, enabling them to better understand fatal events and mitigate such events accordingly. [ABSTRACT FROM AUTHOR]

Hidayetolu et al. (2019) proposed a novel memory-centric computation system, MemXCT. As a challenge at SC20, we reproduce the computational efficiency of MemXCT on our Azure cloud cluster. Our experiments evaluate the overall performance and the strong scalability with real datasets and verify part of the conclusions in the original article. [ABSTRACT FROM AUTHOR]

Modern replicated data stores aim to provide high availability, by immediately responding to client requests, often by implementing objects that expose concurrency. Such objects, for example, multi-valued registers (MVRs), do not have sequential specifications. This paper explores a recent model for replicated data stores that can be used to precisely specify causal consistency for such objects, and liveness properties like eventual consistency, without revealing details of the underlying implementation. The model is used to prove the following results: 1) An eventually consistent data store implementing MVRs cannot satisfy a consistency model strictly stronger than observable causal consistency ( \mathcal OCC ). \mathcal OCC is a model somewhat stronger than causal consistency, which captures executions in which client observations can use causality to infer concurrency of operations. This result holds under certain assumptions about the data store. 2) Under the same assumptions, an eventually consistent and causally consistent replicated data store must send messages of size linear in the size of the system: If s objects, each \Omega (\mathrm{lg} k) -bit in size, are supported by n$ replicas, then there is an execution in which an \Omega (\min \lbrace n,s\rbrace \mathrm{lg} k) -bit message is sent. [ABSTRACT FROM AUTHOR]

Active restoration (AR) is a novel lightpath restoration scheme proposed recently to guarantee a certain degree of survivability in wavelength-division multiplexing (WDM) optical networks with a reasonable trade-off between capacity requirement and restoration time. In this paper, we conduct a comprehensive performance analysis for AR-based optical networks. In particular, we propose a novel analytical framework for modeling the restoration probability of a connection (the probability that the connection can be successfully restored in case of a failure) when the possible correlation among its multiple backup routes is incorporated. Although theoretically, we need to consider all the possible correlations between as many as (...) pairs of backup routes to analyze the restoration probability in a network with N nodes, and this high computation complexity may obscure the practicality of an approach, considering-all the possible correlations among backup routes, our analysis in this paper indicates that by considering at most the possible correlations among any three successive backup routes of a connection, we can achieve a very good approximation to the simulated restoration probability of the connection, as verified by extensive simulation results upon two typical network topologies under various workloads. We find that the proposed framework can deeply investigate into the inherent relationship among restoration probability, wavelength channel utilization ratio, number of wavelengths per fiber, routes hop length, and wavelength conversion capability. As a result, the framework significantly contributes to the related areas by providing network designers with a quantitative tool to evaluate the restoration probability and, thus, the survivability of AR-based optical networks. [ABSTRACT FROM AUTHOR]

Most weak memory consistency models are incapable of supporting a solution to mutual exclusion using only read and write operations to shared variables. Processor Consistency-Goodman's version (PC-G) is an exception. Ahamad et al. showed that Peterson's mutual exclusion algorithm is correct for PC-G, but Lamport's bakery algorithm is not. This paper derives a lower bound on the number of and type of (single or multiwriter) variables that a mutual exclusion algorithm must use in order to be correct for PC-G. Specifically, any such solution for n processes must use at least one multiwriter variable and n single-writer variables. Peterson's algorithm for two processes uses one multiwriter and two single-writer variables, and therefore establishes that this bound is tight for two processes. This paper presents a new n-process algorithm for mutual exclusion that is correct for PC-G and achieves the bound for any n. While Peterson's algorithm is fair, this extension to arbitrary n is not fair. Six known algorithms that use the same number and type of variables are shown to fail to guarantee mutual exclusion when the memory consistency model is only PC-G, as opposed to the Sequential Consistency model for which they were designed. A corollary of our investigation is that, in contrast to Sequential Consistency, multiwriter variables cannot be implemented from single-writer variables in a PC-G system. [ABSTRACT FROM AUTHOR]

The bypass paths and multiported register files in microprocessors serve as an implicit interconnect to communicate operand values among pipeline stages and multiple ALUs. Previous superscalar designs implemented this interconnect using centralized structures that do not scale with increasing ILP demands. In search of scalability, recent microprocessor designs in industry and academia exhibit a trend toward distributed resources such as partitioned register files, banked caches, multiple independent compute pipelines, and even multiple program counters. Some of these partitioned microprocessor designs have begun to implement bypassing and operand transport using point-to-point interconnects. We call interconnects optimized for scalar data transport, whether centralized or distributed, scalar operand networks. Although these networks share many of the challenges of multiprocessor networks such as scalability and deadlock avoidance, they have many unique requirements, including ultra-low latency (a few cycles versus tens of cycles) and ultra-fast operation-operand matching. This paper discusses the unique properties of scalar operand networks (SONs), examines alternative ways of implementing them, and introduces the AsTrO taxonomy to distinguish between them. It discusses the design of two alternative networks in the context of the Raw microprocessor, and presents timing, area, and energy statistics for a real implementation. The paper also presents a 5-tuple performance model for SONs and analyzes their performance sensitivity to network properties for ILP workloads. [ABSTRACT FROM AUTHOR]

Given large-scale multi-dimensional data (e.g., (user, movie, time; rating) for movie recommendations), how can we extract latent concepts/relations of such data? Tensor factorization has been widely used to solve such problems with multi-dimensional data, which are modeled as tensors. However, most tensor factorization algorithms exhibit limited scalability and speed since they require huge memory and heavy computational costs while updating factor matrices. In this paper, we propose GTA, a general framework for Tucker factorization on heterogeneous platforms. GTA performs alternating least squares with a row-wise update rule in a fully parallel way, which significantly reduces memory requirements for updating factor matrices. Furthermore, GTA provides two algorithms: GTA-PART for partially observable tensors and GTA-FULL for fully observable tensors, both of which accelerate the update process using GPUs and CPUs. Experimental results show that GTA exhibits $5.6 \sim 44.6 \times$5.6∼44.6× speed-up for large-scale tensors compared to the state-of-the-art. In addition, GTA scales near linearly with the number of GPUs and computing nodes used for experiments. [ABSTRACT FROM AUTHOR]

Nowadays, high-bandwidth networks are more easily accessible than ever before. However, existing distributed graph-processing frameworks, such as GPS, fail to efficiently utilize the additional bandwidth capacity in these networks for higher performance, due to their inefficient computation and communication models, leading to very long waiting times experienced by users for the graph-computing results. The root cause lies in the fact that the computation and communication models of these frameworks generate, send and receive messages so slowly that only a small fraction of the available network bandwidth is utilized. In this paper, we propose a high-performance distributed graph-processing framework, called BlitzG, to address this problem. This framework fully exploits the available network bandwidth capacity for fast graph processing. Our approach aims at significant reduction in (i) the computation workload of each vertex for fast message generation by using a new slimmed-down vertex-centric computation model and (ii) the average message overhead for fast message delivery by designing a light-weight message-centric communication model. Evaluation on a 40Gbps Ethernet, driven by real-world graph datasets, shows that BlitzG outperforms GPS by up to 27x with an average of 20.7x. [ABSTRACT FROM AUTHOR]

Fat trees are considered suitable structures for data center interconnection networking. Such structures are rigid, and hard to scale up and scale out. A good data center network structure should have high scalability, efficient switch utilization, and high reliability. In this paper we present a class of data center network structures based on hypergraph theory and combinatorial block design theory. We show that our data center network structures are more flexible and scalable than fat trees. Using switches of the same size, our data center network structures can connect more nodes than fat trees, and it is possible to construct different structures with tradeoffs among inter-cluster communication capacity, reliability, the number of switches used, and the number of connected nodes. [ABSTRACT FROM AUTHOR]

Scalable high-performance routers and switches are required to provide a larger number of ports, higher throughput, and good reliability. Most of today's routers and switches are implemented using single crossbar as the switched fabric. The single crossbar complexity increases at O(N2) in terms of crosspoint number, which might become unacceptable for scalability as the port number (N) increases. A delta class self-routing multistage interconnection network (MIN) with the complexity of O(N × log2N) has been widely used in the asynchronous transfer mode switches. However, the reduction of the crosspoint number results in considerable internal blocking. A number of scalable methods have been proposed to solve this problem. One of them uses more stages with recirculation architecture to reroute the deflected packets, which greatly increase the latency. In this paper, we propose an interleaved multistage switching fabrics architecture and assess its throughput with an analytical model and simulations. We compare this novel scheme with some previous parallel architectures and show its benefits. From extensive simulations under different traffic patterns and fault models, our interleaved architecture achieves better performance than its counterpart of single panel fabric. Our interleaved scheme achieves speedups (over the single panel fabric) of 3.4 and 2.25 under uniform and hot-spot traffic patterns, respectively, at maximum load (p = 1). Moreover, the interleaved fabrics show great tolerance against internal hardware failures. [ABSTRACT FROM AUTHOR]

Abstract-The involvement of only the necessary users and service providers for service discovery in pervasive computing environments is challenging. Without prudence, users' and service providers' requests or service information, their identities, and their presence information may be sacrificed. We identify that the problem may be as difficult as a chicken-and-egg problem, in which both users and service providers want the other parties to expose sensitive information first. In this paper, we propose a progressive and probabilistic approach to solve the problem. Users and service providers expose partial information in turn and avoid unnecessary exposure if there is any mismatch. Although 1 or 2 bits of information are exchanged in each message, we prove that the process converges and that the false-positive overhead decreases quickly. Experiments and hypothesis tests show that security properties hold. We implemented the approach and the performance measurements show that the approach runs efficiently on PDAs. [ABSTRACT FROM AUTHOR]

Emerging network technologies have complex network interfaces that have renewed concerns about network reliability. In this paper, we present an effective low-overhead fault tolerance technique to recover from network interface failures. Failure detection is based on a software watchdog timer that detects network processor hangs and a self-testing scheme that detects interface failures other than processor hangs. The proposed self-testing scheme achieves failure detection by periodically directing the control flow to go through only active software modules in order to detect errors that affect instructions in the local memory of the network interface. Our failure recovery is achieved by restoring the state of the network interface using a small backup copy containing just the right amount of information required for complete recovery. The paper shows how this technique can be made to minimize the performance impact to the host system and be completely transparent to the user. [ABSTRACT FROM AUTHOR]

The most commonly used scheduling algorithm for parallel supercomputers is FCFS with backfilling, as originally introduced in the EASY scheduler. Backfilling means that short jobs are allowed to run ahead of their time provided they do not delay previously queued jobs (or at least the first queued job). To make such determinations possible, users are required to provide estimates of how long jobs will run, and jobs that violate these estimates are killed. Empirical studies have repeatedly shown that user estimates are inaccurate, and that system-generated predictions based on history may be significantly better. However, predictions have not been incorporated into production schedulers, partially due to a misconception (that we resolve) claiming inaccuracy actually improves performance, but mainly because underprediction is technically unacceptable: Users will not tolerate jobs being killed just because system predictions were too short. We solve this problem by divorcing kill-time from the runtime prediction and correcting predictions adaptively as needed if they are proved wrong. The end result is a surprisingly simple scheduler, which requires minimal deviations from current practices (e.g., using FCFS as the basis) and behaves exactly like EASY as far as users are concerned; nevertheless, it achieves significant improvements in performance, predictability, and accuracy. Notably, this is based on a very simple runtime predictor that just averages the runtimes of the last two jobs by the same user; counterintuitively, our results indicate that using recent data is more important than mining the history for similar jobs. All the techniques suggested in this paper can be used to enhance any backfilling algorithm and are not limited to EASY. [ABSTRACT FROM AUTHOR]

In this paper, we consider performance evaluation of a system which shares K servers (or resources) among N heterogeneous classes of workloads, where server allocation and deallocation for class i is dictated by a class specific threshold- based policy with hysteresis control. In particular, the server activation time for class i is noninstantaneous. There are many systems and applications whare a multiclass threshold-based queueing system can be of great use. One important utility of using threshold-based approaches is In situations where applications may incur server usage costs. In these cases, one needs to consider not only the performance aspects but also the resulting cost/performance ratio. The motivation for using hysteresis control is to reduce the unnecessary cost of server setup (or activation) and server removal (or deactivation) whenever there are momentary fluctuations in workload. Moreover, servers in such systems and applications are often needed by multiple classes of workloads and, hence, it is desirable to find good approaches to sharing server resources among the different classes of workloads, preferably without statically partitioning the server pool among these classes. An important and distinguishing characteristic of our work is that we consider the modeling and analysis of a multiclass system with noninstantaneous server activation. The main contributions of this work are 1) in developing an efficient approximation method for solving such models, 2) in verifying the convergence of our iterative method, and 3) in evaluating the resulting accuracy of the technique for computing performance measures of interest, which can subsequently be used in making system design choices. [ABSTRACT FROM AUTHOR]

This paper describes the design of a flexible load balancing framework and runtime software system for supporting the development of adaptive applications on distributed-memory parallel computers. The runtime system supports a global namespace, transparent object migration, automatic message forwarding and routing, and automatic load balancing. These features can be used at the discretion of the application developer in order to simplify program development and to eliminate complex bookkeeping associated with mobile data objects. An evaluation of this system in the context of a three-dimensional tetrahedral advancing front parallel mesh generator shows that overall runtime improvements of 15 percent compared to common stop-and-repartition load balancing methods, 30 percent compared to explicit intrusive load balancing methods, and 42 percent compared to no load balancing are possible on large processor configurations. At the same time, the overheads attributable to the runtime system are a fraction of 1 percent of the total runtime. The parallel advancing front method is a coarse-grained and highly adaptive application and therefore exercises all of the features of the runtime system. [ABSTRACT FROM AUTHOR]

Low latency stream processing on large clusters consisting of hundreds to thousands of servers is an increasingly important challenge. A crucial barrier to tackling this challenge is stragglers, i.e., tasks that are significantly straggling behind others in processing the stream data. However, prior straggler mitigation solutions have significant limitations. They balance streaming workloads among tasks but may incur imbalanced backlogs when the workloads exhibit variance, causing stragglers as well. Fortunately, we observe that carefully scheduling the outgoing tuples of different tasks can yield benefits for balancing backlogs, and thus avoids stragglers. To this end, we present Hone, a tuple scheduler that aims to minimize the maximum queue backlog of all tasks over time. Hone leverages an online Largest-Backlog-First (LBF) algorithm with a provable good competitive ratio to perform efficient tuple scheduling. We have implemented Hone based on Apache Storm and evaluated it extensively via both simulations and testbed experiments. Our results show that under the same workload balancing strategy–shuffle grouping, Hone outperforms the original Storm significantly, with the end-to-end tuple processing latency reduced by 78.7 percent on average. [ABSTRACT FROM AUTHOR]

The issue of potential privacy leakage during centralized AI’s model training has drawn intensive concern from the public. A Parallel and Distributed Computing (or PDC) scheme, termed Federated Learning (FL), has emerged as a new paradigm to cope with the privacy issue by allowing clients to perform model training locally, without the necessity to upload their personal sensitive data. In FL, the number of clients could be sufficiently large, but the bandwidth available for model distribution and re-upload is quite limited, making it sensible to only involve part of the volunteers to participate in the training process. The client selection policy is critical to an FL process in terms of training efficiency, the final model’s quality as well as fairness. In this article, we will model the fairness guaranteed client selection as a Lyapunov optimization problem and then a C2MAB-based method is proposed for estimation of the model exchange time between each client and the server, based on which we design a fairness guaranteed algorithm termed RBCS-F for problem-solving. The regret of RBCS-F is strictly bounded by a finite constant, justifying its theoretical feasibility. Barring the theoretical results, more empirical data can be derived from our real training experiments on public datasets. [ABSTRACT FROM AUTHOR]

Pervasive computing environments (PvCE) are embedded with interconnected smart devices which provide users with services desired. To meet requirements of users, smart devices with different kinds of functions may need to be associated together to provide the service described in the user requirement, which is called service composition. As the service composition environment may be dynamic and large scale, centralized service composition algorithm is usually inefficient due to message cost. On the other hand, a decentralized approach, which employs pre-determined coordinators to search and compose service, may have high cost as well. In this paper, we discuss a localized approach for service composition based on the Ubiquitous Interacting Object (UIO) model we have proposed earlier. UIO is an abstraction of physical devices in PvCE with ability to find and collaborate with other devices through exposing their capabilities as services. In our localized service composition algorithm (LASEC), UIOs collaborate with each other in a bottom-up, localized manner to compose required service without requiring global knowledge. To solve the problem of blind compositions in LASEC, we propose a novel mechanism called Alien-information-based Acknowledging (A-Ack), in which a UIO decides on collaborating with another UIO only after obtaining some additional information from the collaboration candidate. Specifically, this information refers to ability of a given UIO to compose another part of the service. Proposed LASEC is message-efficient and quality-guaranteed. Extensive simulations of LASEC as well as existing decentralized and pull-based centralized algorithms have been conducted. The results show the relatively low communication cost and composition time of LASEC. Moreover, we demonstrate feasibility of our approach with a prototype implementation. [ABSTRACT FROM AUTHOR]

In recent years, there are many new findings on independent spanning trees (ISTs for short) in hypercubes, crossed cubes, locally twisted cubes, and M\ddot\obius cubes, which all belong to a more general network category called bijective connection networks (BC networks). However, little progress has been made for ISTs in general BC networks. In this paper, we first propose the definitions of conditional BC networks and V-dimensional-permutation. We then give a linear parallel algorithm of ISTs rooted at an arbitrary vertex in conditional BC networks, which include hypercubes, crossed cubes, locally twisted cubes, and M \ddot\obius cubes, based on the ascending circular dimensional-permutation, where the ISTs are all isomorphic to the binomial-like tree. In addition, we show that there exists an efficient algorithm to construct a spanning tree rooted at an arbitrary vertex in any BC network X_n, and all V-dimensional-permutations can be used to construct spanning trees isomorphic to the n-level binomial tree and rooted at an arbitrary vertex in X_n. [ABSTRACT FROM PUBLISHER]

Conventional methods supporting Java binary security mainly rely on the security of the host Java Virtual Machine (JVM). However, malicious Java binaries keep exploiting the vulnerabilities of JVMs, escaping their sandbox restrictions and allowing attacks on end-user systems. Administrators must confront the difticulties and dilemmas brought on by security upgrades. On the other hand, binary rewriting techniques have been advanced to allow users to enforce security policies directly on the mobile code. They have the advantages of supporting a richer set of security policies and a self-constrained written code. However, the high administrative and performance overhead caused by security configuration and code rewriting have prevented rewriters from becoming a practical security tool. In this paper, we address these problems by integrating binary code rewriters with Web caching proxies and build the security system called PB-JARS, a Proxy-based JAva Rewriting System. PB-JARS works as a complimentary system to existing JVM security mechanisms by placing another line of defense between users and their end-user systems. It gives system administrators centralized security control and management for the mobile code and security policies. We evaluated PB-JARS using a real Java binary traffic model derived from analyzing real Web trace records. Our results show that adding binary rewriting to a Web caching system can be very efficient in improving end-host security at a low cost. [ABSTRACT FROM AUTHOR]

Many wireless sensor network (WSN) applications demand secure communications. The random key predistribution (RKP) protocol has been well accepted in achieving secure communications in WSNs. A host of key management protocols have been proposed based on the RKP protocol. However, due to the randomness in key distribution and strong constraint in key path construction, the RKP-based protocols can only be applied in highly dense networks, which are not always feasible in practice. In this paper, we propose a methodology called network decoupling to address this problem. With this methodology, a WSN is decoupled into a logical keysha ring network and a physical neighborhood network, which significantly releases the constraint in key path construction of the RKP protocol. We design two new key management protocols, that is, RKP-DE and RKP-DEA, as well as a set of link and path dependency elimination rules in decoupled sensor networks. Our analytical and simulation data demonstrate the performance enhancement of our solutions from the perspective of connectivity and resilience and its applicability in nonhighly dense sensor networks. [ABSTRACT FROM AUTHOR]

One of the most prominent and comprehensive ways of data collection in sensor networks is to periodically extract raw sensor readings. This way of data collection enables complex analysis of data, which may not be possible with in-network aggregation or query processing. However, this flexibility in data analysis comes at the cost of power consumption. In this paper, we develop ASAP, which is an adaptive sampling approach to energy-efficient periodic data collection in sensor networks. The main idea behind ASAP is to use a dynamically changing subset of the nodes as samplers such that the sensor readings of the sampler nodes are directly collected, whereas the values of the nonsampler nodes are predicted through the use of probabilistic models that are locally and periodically constructed. ASAP can be effectively used to increase the network lifetime while keeping the quality of the collected data high in scenarios where either the spatial density of the network deployment is superfluous, which is relative to the required spatial resolution for data analysis, or certain amount of data quality can be traded off in order to decrease the power consumption of the network. The ASAP approach consists of three main mechanisms: First, sensing-driven cluster construction is used to create clusters within the network such that nodes with close sensor readings are assigned to the same clusters. Second, correlation-based sampler selection and model derivation are used to determine the sampler nodes and to calculate the parameters of the probabilistic models that capture the spatial and temporal correlations among the sensor readings. Last, adaptive data collection and model-based prediction are used to minimize the number of messages used to extract data from the network. A unique feature of ASAP is the use of in-network schemes, as opposed to the protocols requiring centralized control, to select and dynamically refine the subset of the sensor nodes serving as samplers and to adjust the value prediction models used for nonsampler nodes. Such runtime adaptations create a data collection schedule, which is self-optimizing in response to the changes in the energy levels of the nodes and environmental dynamics. We present simulation-based experimental results and study the effectiveness of ASAP under different system settings. [ABSTRACT FROM AUTHOR]

In the InfoBeacons system, a peer-to-peer network of beacons cooperates to route queries to the best information sources. Many Internet sources are unwilling to provide more cooperation than simple searching to aid in the query routing. We adapt techniques from information retrieval to deal with this lack of cooperation. In particular, beacons determine how to route queries based on information cached from sources' responses to queries. In this paper, we examine alternative architectures for routing queries between beacons and to data sources. We also examine how to improve the routing by probing sources in an informed way to learn about their content. Results of experiments using a beacon network to search 2,500 information sources demonstrates the effectiveness of our system; for example, our techniques require contacting up to 71 percent fewer sources than existing peer-to-peer random walk techniques. [ABSTRACT FROM AUTHOR]

The exploitation of parallelism in a message passing platform implies a previous modeling phase of the parallel application as a task graph, which properly reflects its temporal behavior. In this paper, we analyze the classical task graph models of the literature and their drawbacks when modeling message passing programs with an arbitrary task structure. We define a new task graph model called Temporal Task Interaction Graph (TTIG) that integrates the classical models used in the literature. The TTIG allows us to explicitly capture the ability of concurrency of adjacent tasks for applications where adjacent tasks can communicate at any point inside them. A mapping strategy is developed from this model, which minimizes the expected execution time by properly exploiting task parallelism. The effectiveness of this approach has been proved in different experimentation scopes for a wide range of message passing applications. [ABSTRACT FROM AUTHOR]

Virtual channels (VCs) are a popular solution for the provision of quality of service (QoS). Current interconnect standards propose 16 or even more VCs for this purpose. However, most implementations do not offer so many VCs because it is too expensive in terms of silicon area. Therefore, a reduction of the number of VCs necessary to support QoS can be very helpful in the switch design and implementation. In this paper, we show that this number of VCs can be reduced if the system is considered as a whole rather than each element being taken separately. The scheduling decisions made at network interfaces can be easily reused at switches without significantly altering the global behavior. In this way, we obtain a noticeable reduction of silicon area, component count and, thus, power consumption, and we can provide similar performance to a more complex architecture. We also show that this is a scalable technique, suitable for the foreseen demands of traffic. [ABSTRACT FROM AUTHOR]

In this paper, we address several issues that are imperative to Grid environments such as handling resource heterogeneity and sharing, communication latency, job migration from one site to other, and load balancing. We address these issues by proposing two job migration algorithms, which are MELISA (Modified ELISA) and LBA (Load Balancing on Arrival). The algorithms differ in the way load balancing is carried out and is shown to be efficient in minimizing the response time on large and small-scale heterogeneous Grid environments, respectively. MELISA, which is applicable to large-scale systems (that is, interGrid [1]), is a modified version of ELISA [2] in which we consider the job migration cost, resource heterogeneity, and network heterogeneity when load balancing is considered. The LBA algorithm, which is applicable to small-scale systems (that is, intraGrid [1]), performs load balancing by estimating the expected finish time of a job on buddy processors on each job arrival. Both algorithms estimate system parameters such as the job arrival rate, CPU processing rate, and load on the processor and balance the load by migrating jobs to buddy processors by taking into account the job transfer cost, resource heterogeneity, and network heterogeneity. We quantify the performance of our algorithms using several influencing parameters such as the job size, data transfer rate, status exchange period, and migration limit, and we discuss the implications of the performance and choice of our approaches. [ABSTRACT FROM AUTHOR]

This paper presents a new distributed approach to detecting DDoS (distributed denial of services) flooding attacks at the traffic-flow level. The new defense system is suitable for efficient implementation over the core networks operated by Internet service providers (ISPs). At the early stage of a DDoS attack, some traffic fluctuations are detectable at Internet routers or at the gateways of edge networks. We develop a distributed change-point detection (DCD) architecture using change aggregation trees (CAT). The idea is to detect abrupt traffic changes across multiple network domains at the earliest time. Early detection of DDoS attacks minimizes the flooding damages to the victim systems serviced by the provider. The system is built over attack-transit routers, which work together cooperatively. Each ISP domain has a CAT server to aggregate the flooding alerts reported by the routers. CAT domain servers collaborate among themselves to make the final decision. To resolve policy conflicts at different ISP domains, a new secure infrastructure protocol (SIP) is developed to establish mutual trust or consensus. We simulated the DCD system up to 16 network domains on the Cyber Defense Technology Experimental Research (DETER) testbed, a 220-node PC cluster for Internet emulation experiments at the University of Southern California (USC) Information Science Institute. Experimental results show that four network domains are sufficient to yield a 98 percent detection accuracy with only 1 percent false-positive alarms. Based on a 2006 Internet report on autonomous system (AS) domain distribution, we prove that this DDoS defense system can scale well to cover 84 AS domains. This security coverage is wide enough to safeguard most ISP core networks from real-life DDoS flooding attacks. [ABSTRACT FROM AUTHOR]

Earlier work has developed the underpinnings of the IC-Scheduling Theory, a framework for scheduling computations having intertask dependencies—modeled via directed acyclic graphs (DAGs)—for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients' computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation's stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation ..., which allows one to "prioritize" the scheduling of a complex DAG's building blocks. The current paper extends the IC-Scheduling Theory in two ways: by expanding significantly the repertoire of DAGs that the Theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either "expansive," in the sense that they grow outward from their sources, or "reductive," in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to "read off" an optimal schedule for a DAG from a given optimal schedule for the DAG's dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks). [ABSTRACT FROM AUTHOR]

Modern Web-based application infrastructures are based on clustered multitiered architectures, where request distribution occurs in two sequential stages: over a cluster of Web servers and over a cluster of application servers. Much work has focused on strategies for distributing requests across a Web server cluster in order to improve the overall throughput across the cluster. The strategies applied at the application layer are the same as those at the Web server layer because it is assumed that they transfer directly. In this paper, we argue that the problem of distributing requests across an application server cluster is fundamentally different from the Web server request distribution problem due to core differences in request processing in Web and application servers. We devise an approach for distributing requests across a cluster of application servers such that the overall system throughput is enhanced, and load across the application servers is balanced. [ABSTRACT FROM AUTHOR]

Structured peer-to-peer overlay networks, like distributed hash tables (DHTs), map data items to the network based on a consistent hashing function. Such mapping for data distribution has an inherent load balance problem. Data redistribution algorithms based on randomized matching of heavily loaded nodes with light ones can deal with the dynamics of DHTs. However, they are unable to consider the proximity of the nodes simultaneously. There are other methods that rely on auxiliary networks to facilitate locality-aware load redistribution. Due to the cost of network construction and maintenance, the locality-aware algorithms can hardly work for DHTs with churn. This paper presents a locality-aware randomized load-balancing algorithm to deal with both the proximity and network churn at the same time. We introduce a factor of randomness in the probing of lightly loaded nodes in a range of proximity. We further improve the efficiency by allowing the probing of multiple candidates (d-way) at a time. Simulation results show the superiority of the locality-aware two-way randomized algorithm in comparison with other random or locality-aware algorithms. In DHTs with churn, it performs no worse than the best churn-resilient algorithm. It takes advantage of node capacity heterogeneity and achieves good load balance effectively even in a skewed distribution of items. [ABSTRACT FROM AUTHOR]

Proxy caching is a key technique to reduce transmission cost for on-demand multimedia streaming. The effectiveness of current caching schemes, however, is limited by the insufficient storage space and weak cooperations among proxies and their clients, particularly considering the high bandwidth demands from media objects. In this paper, we propose COPACC, a cooperative proxy- and-client caching system that addresses the above deficiencies. This innovative approach combines the advantages of both proxy caching and peer-to-peer client communications. It leverages the client-side caching to amplify the aggregated cache space and rely on dedicated proxies to effectively coordinate the communications. We propose a comprehensive suite of distributed protocols to facilitate the interactions among different network entities in COPACC. It also realizes a smart and cost-effective cache indexing, searching, and verifying scheme. Furthermore, we develop an efficient cache allocation algorithm for distributing video segments among the proxies and clients. The algorithm not only minimizes the aggregated transmission cost of the whole system, but also accommodates heterogeneous computation and storage constraints of proxies and clients. We have extensively evaluated the performance of COPACC under various network and end-system configurations. The results demonstrate that it achieves remarkably lower transmission cost as compared to pure proxy-based caching with limited storage space. On the other hand, it is much more robust than a pure peer-to-peer communication system in the presence of node failures. Meanwhile, its computation and control overheads are both kept in low levels. [ABSTRACT FROM AUTHOR]

Unstructured peer-to-peer (P2P) system is the prevalent model in today's P2P systems. In such systems, a response is sent along the same path that carried the incoming query message. To guarantee the anonymity of the requestor, no requestor information is included in the response message, and each node in the query's incoming path only knows its direct neighbors who sent the query request to it. This mechanism introduces response loss when any one node or connection in the path fails, which is a common occurrence in the P2P system due to its dynamic feature. In this paper, we address the response loss problem and show that peers' oscillation can cause up to a 35 percent response loss in an unstructured P2P system. We also present three techniques to alleviate this problem: the redundant response delivery (RRD) scheme as a proactive approach, the adaptive response delivery (ARD) scheme as a reactive approach, and the extended adaptive response delivery scheme to render ARD to function in an unstructured P2P system with limited or no flooding-based search mechanism. We have evaluated our techniques in a large-scale network simulation. With limited traffic overhead, all three techniques reduce response loss rate by more than 65 percent and are fully distributed. We have designed our techniques to be simple to develop and implement in existing P2P systems. [ABSTRACT FROM AUTHOR]

Expiration-based consistency management is widely used to keep replicated contents up-to-date in the Internet. The effectiveness of replication can be characterized by the communication costs of client accesses and consistency management. Both costs depend on the locations of the replicas. This paper investigates the problem of placing replicas in a network where replica consistency is managed by the expiration-based scheme. Our objective is to minimize the total cost of client accesses and consistency management. By analyzing the communication cost of recursive validations for cascaded replicas, we prove that in the optimal placement scheme, the nodes not assigned replicas induce a connected subgraph that includes the origin server. Our results are generic in that they apply to any request arrival patterns. Based on the analysis, an O(D)-time algorithm is proposed to compute the optimal placement of the replicas, where D is the sum of the number of descendants over all nodes in the routing tree. [ABSTRACT FROM AUTHOR]

All-optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has been proposed as a promising candidate to meet the ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. However, with current technology, the cost of optical communication, especially the cost of optical buffering and wavelength conversion, remains a major concern for such applications. In this paper, we study WDM optical interconnects that utilize low cost recirculating buffering and limited range wavelength conversion. We first consider the packet scheduling problem in this type of interconnect, and formalize the problem of maximizing throughput and minimizing packet delay as a matching problem in a bipartite graph. We give an optimal parallel algorithm for this problem that runs in O(Bk²) time, compared to O((N + B)³k³) time if directly applied to existing matching algorithms for general bipartite graphs, where N is the number of input/output fibers of the interconnect, B is the number of fiber delay lines, and k is the number of wavelengths. We also consider efficient switching fabric designs for this type of interconnect. We distinguish between the switching fabric connecting the input fibers to the output fibers and the switching fabric connecting the input fibers to the delay lines and show that by adopting the idea of concentration, the cost of the latter can be reduced significantly in terms of the number of crosspoints. [ABSTRACT FROM AUTHOR]

Software-based active replication is expensive in terms of performance overhead. Multithreading can help improve performance; however, thread scheduling is a source of nondeterminism in replica behavior. To achieve strong replica consistency in multithreaded environments, this paper proposes intercepting mutex lock/unlock operations performed by threads on accessing the shared data and contributes with two algorithmic solutions: 1) a Loose Synchronization Algorithm (LSA), which captures the natural concurrency in a leader replica and projects it on follower replicas through interreplica communication, and 2) a Preemptive Deterministic Scheduler (PDS) algorithm, which removes the need for interreplica communication through the notion of round and by suspending threads when it is unable (yet) to schedule them deterministically. Failure behavior and performance of LSA and PDS implementations are evaluated in a triplicated system and compared with existing solutions. A performance evaluation indicates that LSA and PDS outperform existing solutions, with PDS offering lower throughput than LSA. A fault-injection campaign shows that PDS is more robust to errors due to the absence of interreplica communication. Hence, LSA and PDS represent a trade-off between performance and dependability. Finally, LSA and PDS are demonstrated in replicating the Apache Web server, a substantial real-world application. [ABSTRACT FROM AUTHOR]

A number of structured peer-to-peer (P2P) lookup protocols have been proposed recently. A P2P lookup protocol routes a lookup request to its target node in a P2P distributed system. Existing protocols achieve balanced routing traffic among nodes by assuming that lookup requests are evenly targeted at every node. However, when lookup requests concentrate on a few nodes simultaneously, these nodes become hot spots. Due to uneven routing patterns in existing protocols, hot spots cause unbalanced routing traffic which leads to routing bottlenecks. In this paper, we present a novel structured P2P lookup protocol called SCALLOP that delivers balanced routing and avoids routing bottlenecks at occurrences of hot spots. Among existing protocols, SCALLOP is the first one to accomplish this goal at the fundamental nature of a routing protocol. SCALLOP achieves balanced routing by uniquely constructing a balanced lookup tree for each node. The balanced tree evenly distributes routing traffic among sibling nodes and, therefore, avoids or reduces routing bottlenecks. In addition, as a load-balanced protocol, SCALLOP delivers asymptotically optimal lookup performance at the tradeoff between routing path and routing table size. We conducted a set of simulations to demonstrate the effectiveness of SCALLOP. The results show that, compared with a most-referenced and representative structured P2P lookup protocol and a graph-based extension of this protocol, SCALLOP significantly reduces routing bottlenecks while all three protocols deliver comparable lookup performance. [ABSTRACT FROM AUTHOR]

Multimedia-on-Demand (MOD) applications have grown dramatically in popularity, especially in the domains of education, business, and entertainment. Current MOD servers waste precious resources in performing store-and-forward copying. This excessive overhead increases cost and severely limits the scalability of these servers. In this paper, we propose using the Network-Attached Disk (NAD) architecture to design highly scalable and cost-effective MOD servers. In order to ensure enhanced performance, we propose a scheme, called Distributed Interval Caching (DIC), which utilizes the on-disk buffers for caching intervals between successive streams. We also propose another scheme, called Multi-Objective Scheduling (MOS), which increases the degrees of resource sharing by scheduling the waiting requests for service intelligently. We then integrate the two schemes and study the overall performance benefits through extensive simulation. The results demonstrate that the integrated policy works very well in increasing the number of customers that can be serviced concurrently while decreasing their waiting times for service. The performance benefits vary with several architectural, system workload, and scheduling parameters. We conclude this study by developing an analytical model for ideal DIC in order to estimate the performance limits which may be achieved through various optimizations. [ABSTRACT FROM AUTHOR]

To successfully exploit all the possibilities of current computer/multicomputer architectures, optimization compiling techniques are a must. However, for codes based on pointers and dynamic data structures, these optimization techniques have to be necessarily carried out after identifying the characteristics and properties of the data structure used in the code. In this paper, we describe the framework and the analyzer we have implemented to capture complex data structures generated, traversed, and modified in codes based on pointers. Our method assigns a Reduced Set of Reference Shape Graph (RSRSG) to each statement to approximate the shape of the data structure after the execution of such a statement. With the properties and operations that define the behavior of our RSRSG, the method can accurately detect complex recursive data structures such as a doubly linked list of pointers to trees where the leaves point to additional lists. Several experiments are carried out with real codes to validate the capabilities of our analyzer. [ABSTRACT FROM AUTHOR]

Proposes an approach to broadcast in wormhole-routed, and three-dimensional torus networks. Extension of the graph theoretical concept of dominating nodes; Characteristics of Massively parallel computers; Further information on the proposed algorithm.

Presents information on reconfigurable meshes. Consideration of the Euclidean Minimum Spanning Tree (EMST) and the All Nearest Neighbors (ANN) problems; Applications of the EMST; Problem of constructing an EMST for a given set of points in a d-dimensional space.

Presents a paper which analyzed load sharing (LS) in Hexagonal Architecture for Real-Time Systems (HARTS). Examination of a system model and load sharing mechanism for HARTS; How the performance of LS can be evaluated; Features of distributed systems; Outline of the design for load sharing mechanisms for real-time applications.

Quantization has been proven to be a vital method for improving the inference efficiency of deep neural networks (DNNs). However, it is still challenging to strike a good balance between accuracy and efficiency while quantizing DNN weights or activation values from high-precision formats to their quantized counterparts. We propose a new method called elastic significant bit quantization (ESB) that controls the number of significant bits of quantized values to obtain better inference accuracy with fewer resources. We design a unified mathematical formula to constrain the quantized values of the ESB with a flexible number of significant bits. We also introduce a distribution difference aligner (DDA) to quantitatively align the distributions between the full-precision weight or activation values and quantized values. Consequently, ESB is suitable for various bell-shaped distributions of weights and activation of DNNs, thus maintaining a high inference accuracy. Benefitting from fewer significant bits of quantized values, ESB can reduce the multiplication complexity. We implement ESB as an accelerator and quantitatively evaluate its efficiency on FPGAs. Extensive experimental results illustrate that ESB quantization consistently outperforms state-of-the-art methods and achieves average accuracy improvements of 4.78%, 1.92%, and 3.56% over AlexNet, ResNet18, and MobileNetV2, respectively. Furthermore, ESB as an accelerator can achieve 10.95 GOPS peak performance of 1k LUTs without DSPs on the Xilinx ZCU102 FPGA platform. Compared with CPU, GPU, and state-of-the-art accelerators on FPGAs, the ESB accelerator can improve the energy efficiency by up to 65×, 11×, and 26×, respectively. [ABSTRACT FROM AUTHOR]

Merging sorted segments is a core topic of fundamental computer science that has many different applications, such as n-body simulation. In this research, we propose Lazy-Merge, a novel implementation of sequential in-place k-way merging algorithms, that can be utilized in their parallel counterparts. The implementation divides the k-way merging problem into t ordered and independent smaller k-way merging tasks (partitions), but each merging task includes a set of scattered ranges to be merged by an existing merging algorithm. The final merged list includes ranges with ordered elements, but the ranges themselves are not ordered. Lazy-Merge utilizes a novel usage of indexes to access the entire set of merged elements in order. Its merging time complexity is O(k log (n/k) + merge(n/p)), where k, n, and pare the number of segments, the list size and the number of processors (partitions), respectively. Here, merge(n/p) represents the time needed to merge n/p elements by the used in-place merging algorithm. The time complexity of accessing an element in the merged list is O(log k), that time can be constant if k processors are used. The results of the proposed work are compared with those of bitonic merge and the best time-space optimal algorithms on number of moves and execution time. In comparison with the existing algorithms, significant speedup and reasonable reduction factor for number of moves have been achieved. [ABSTRACT FROM AUTHOR]

Unexpected bursty traffic brought by certain sudden events, such as news in the spotlight on a social network or discounted items on sale, can cause severe load imbalance in backend services. Migrating hot data—the standard approach to achieve load balance—meets a challenge when handling such unexpected load imbalance, because migrating data will slow down the server that is already under heavy pressure. This article proposes PostMan, an alternative approach to rapidly mitigate load imbalance for services processing small requests. Motivated by the observation that processing large packets incurs far less CPU overhead than processing small ones, PostMan deploys a number of middleboxes called helpers to assemble small packets into large ones for the heavily-loaded server. This approach essentially offloads the overhead of packet processing from the heavily-loaded server to helpers. To minimize the overhead, PostMan activates helpers on demand, only when bursty traffic is detected. The heavily-loaded server determines when clients connect/disconnect to/from helpers based on the real-time load statistics. To tolerate helper failures, PostMan can migrate connections across helpers and can ensure packet ordering despite such migration. Driven by real-world workloads, our evaluation shows that, with the help of PostMan, a Memcached server can mitigate bursty traffic within hundreds of milliseconds, while migrating data takes tens of seconds and increases the latency during migration. [ABSTRACT FROM AUTHOR]