IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems - January 2010 (Vol. 21, No. 1)

PrePrint: Representation of a Stochastic Traffic Bound

This paper presents a theoretical representation of a stochastic traffic bound (σ’,ρ’) that consists of two items, the burstiness bound σ’ and the bound of long-term average rate ρ’. The novelty of the suggested representation is that the burstiness bound and the bound of long-term average rate are separately connected to the fractal dimension D that is the measure of the local self-similarity together with the small-scale factor r and the Hurst parameter H that is the measure of the long-range dependence (LRD) together with the large-scale factor a of traffic. More precisely, we obtain σ’=r^(2D-5)σ and ρ’=a^(-H) ρ, where σ is the conventional bound of burstiness, and ρ the conventional bound of long-term average rate, respectively. Thus, the present bound (σ’, ρ’) takes the conventional bound, saying (σ,ρ), as a special case when r = 1 and a = 1. Hence, the proposed representation provides us with a flexible way to tighten a traffic bound. Since we study the stochastically bounded modeling of traffic by taking into account the parameters in stochastic modeling, namely, D, H, r, and a, as well as the parameters in the deterministic modeling of traffic, i.e., σ and ρ, a new outlook regarding the stochastically bounded modeling of traffic is revealed. In addition, we open a problem to estimate r and a with respect to the possible applications of the proposed bound to the practice.

Presented By:

NEC

Ads by Pheedo

PrePrint: Self-Disciplinary Worms and Countermeasures: Modeling and Analysis

In this paper, we address issues related to the modeling, analysis, and countermeasures of worm attacks on the Internet. Most previous work assumed that a worm always propagates itself at the highest possible speed. Some newly developed worms (e.g., "Atak" worm) contradict this assumption by deliberately reducing the propagation speed in order to avoid detection. As such, we study a new class of worms, referred to as self-disciplinary worms. These worms adapt their propagation patterns in order to reduce the probability of detection, and to eventually infect more computers. We demonstrate that existing worm detection schemes based on traffic volume and variance cannot effectively defend against these self-disciplinary worms. To develop proper countermeasures, we introduce a game-theoretic formulation to model the interaction between the worm propagator and the defender. We show that an effective integration of multiple countermeasure schemes (e.g., worm detection and forensics analysis) is critical for defending against self-disciplinary worms. We propose different integrated schemes for fighting different self-disciplinary worms, and evaluate their performance via real-world traffic data.

PrePrint: A Near-Optimal Algorithm Attacking the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks

In an unstructured peer-to-peer (P2P) network (e.g., Gnutella), participating peers choose their neighbors randomly such that the resultant P2P network mismatches its underlying physical network, resulting in the lengthy communication between the peers and redundant network traffics generated in the underlying network. Previous solutions to the topology-mismatch problem in the literature either have no performance guarantees or are far from the optimum. In this paper, we propose a novel topology-matching algorithm based on the Metropolis-Hastings method. Our proposal is guided by our insight analytical model and is close to the optimal design. Specifically, we show that our proposal constructs an unstructured P2P network in which a broadcast message, originated by any node $v$, reaches any other node $u$ by taking approximately the only physical end-to-end delay between $v$ and $u$. In addition, our design guarantees the exponential broadcast scope. We verify our solution through extensive simulations, and show that our proposal considerably outperforms state-of-the-art solutions.

PrePrint: An ISP-Friendly File Distribution Protocol: Analysis, Design and Implementation

In the past few years, P2P file distribution applications (e.g., BitTorrent) are becoming so popular that they are the dominating source of Internet traffic. This creates significant problems to Internet Service Providers (ISPs), not only because of the added complexity in traffic engineering, but the increase of traffic, in particular on the cross-ISP links, implies congestion and a higher operating cost. In this paper, we consider an ISP-friendly file distribution protocol which uses the "{\em exploiting-the-locality principle}" (ELP) to reduce the cross-ISP traffic. To show its benefit, we derive an upper and lower bound of cross-ISP traffic for the protocols which rely on ELP, and show that the cross-ISP traffic can be reduced significantly when the number of peers within an ISP increases. To carry out realistic study, we design and implement our ISP-friendly protocol (which is compatible with the current BitTorrent protocol) and carry out large scale experiments on PlanetLab to measure the reduction of the cross ISP-traffic and the file downloading time. More important, we also show how the proposed ISP-friendly protocol can handle the "{\em black-hole}" security attack. This paper sheds light on the merits and design direction of ISP-friendly content distribution protocols.

PrePrint: Dealing with Transient Faults in the Interconnection Network of CMPs at the Cache Coherence Level

The importance of transient faults is predicted to grow due to current technology trends of increased scale of integration. One of the components that will be significantly affected by transient faults is the interconnection network of CMPs. To deal efficiently with these faults and differently from other authors, we propose to use fault-tolerant cache coherence protocols that ensure the correct execution of programs when not all messages are correctly delivered. We describe the extensions made to a directory-based cache coherence protocol to provide fault tolerance and provide a modified set of token counting rules which are useful to design fault-tolerant token-based cache coherence protocols. We compare the directory-based fault-tolerant protocol with a token-based fault-tolerant one. We also show how to adjust the fault tolerance parameters to achieve the desired level of fault tolerance and measure the overhead achieved to be able to support very high fault rates. Simulation results using a set of scientific, multimedia and commercial applications show that the fault tolerance measures have virtually no impact on execution time with respect to a non fault-tolerant protocol. Additionally, our protocols can support very high rates of transient faults (including bursts) at the cost of slightly increased network traffic.

PrePrint: Detecting Application Denial-of-Service Attacks: A Group Testing Based Approach

Application DoS attack, which aims at disrupting application service rather than depleting the network resource, has emerged as a larger threat to network services, compared to the classic DoS attack. Owing to its high similarity to legitimate traffic and much lower launching overhead than classic DDoS attack, this new assault type cannot be efficiently detected or prevented by existing detection solutions. To identify application DoS attack, we propose a novel group testing(GT) based approach deployed on back-end servers, which not only offers a theoretical method to obtain short detection delay and low false positive/negative rate, but also provides an underlying framework against general network attacks. More specifically, we first extend classic GT model with size constraints for practice purposes, then re-distribute the client service requests to multiple virtual servers embedded within each back-end server machine, according to specific testing matrices. Base on this framework, we propose a 2-mode detection mechanism using some dynamic thresholds to efficiently identify the attackers. The focus of this work lies in the detection algorithms proposed and the corresponding theoretical complexity analysis. We also provide preliminary simulation results regarding the efficiency and practicability of this new scheme. Further discussions over implementation issues and performance enhancements are also appended to show its great potentials.

PrePrint: Correlation-Based Traffic Analysis Attacks on Anonymity Networks

In this paper, we address issues related to flow correlation attacks and the corresponding countermeasures in low-latency anonymity networks. Mixes have been used in many anonymous communication systems and are supposed to provide countermeasures to defeat traffic analysis attacks. In this paper, we focus on a particular class of traffic analysis attacks, flow correlation attacks, by which an adversary attempts to analyze the network traffic and correlate the traffic of a flow over an input link with that over an output link. Two classes of correlation methods are considered, namely time-domain methods and frequency-domain methods. Based on our threat model and known strategies in existing mix networks, we perform extensive experiments to analyze the performance of mixes. We find that a mix with any known batching strategy may fail against flow correlation attacks allowing the adversary to reconstruct the path used by a flow. We also investigate methods that can effectively counter flow-correlation and other timing attacks. The empirical results provided in this paper give an indication to designers of Mix networks about appropriate configurations and alternative mechanisms to be used to counter flow correlation attacks.

PrePrint: Snoogle: A Search Engine for Pervasive Environments

Embedding small devices into everyday objects like toasters and coffee mugs creates a wireless network of objects. These embedded devices can contain a description of the under-lying objects, or other user defined information. In this paper, we present Snoogle, a search engine for such a network. A user can query Snoogle to find a particular mobile object, or a list of objects that fit the description. Snoogle uses information retrieval techniques to index information and process user queries, and Bloom filters to reduce communication overhead. Security and privacy protections are also engineered into Snoogle to protect sensitive information. We have implemented a prototype of Snoogle using off-the-shelf sensor motes, and conducted extensive experiments to evaluate the system performance.

PrePrint: A Hypergraph Approach to Linear Network Coding in Multicast Networks

Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. A typical scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose an approach to transforming the linear coding problem into a graph theory problem. By utilizing hypergraphs, we model the linear codes by constructing a pseudo-dual graph of the multicast network. Then a valid linear code is equivalent to a cover in the pseudo-dual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, we propose several preprocessing algorithms to further reduce the computation time required by the iterative refinements by reducing the graph size before transformation. An important contribution of this work is that the proposed approach can be readily extended to solve many minimal network coding problems. By assigning different weights to edges, minimal network coding problems are reduced to the shortest path problems in the pseudo-dual graph. Our simulation results show that the proposed algorithms can reduce the computation time by about 40-50% in a midium size multicast network, and the throughput of the system with network coding is 25% higher than that with the traditional approach of multiple multicast trees.

PrePrint: Resource Bundles: Using Aggregation for Statistical Wide-Area Resource Discovery and Allocation

Resource discovery is an important process for finding suitable nodes that satisfy application requirements in large loosely-coupled distributed systems. Besides inter-node heterogeneity, many of these systems also show a high degree of intra-node dynamism, so that selecting nodes based only on their recently observed resource capacities can lead to poor deployment decisions resulting in application failures or migration overheads. However, most existing resource discovery mechanisms rely mainly on recent observations to achieve scalability in large systems. In this paper, we propose the notion of a resource bundle - a representative resource usage distribution for a group of nodes with similar resource usage patterns - that employs two complementary techniques to overcome the limitations of existing techniques: resource usage histograms to provide statistical guarantees for resource capacities, and clustering-based resource aggregation to achieve scalability. Using trace-driven simulations and data analysis of a month-long PlanetLab trace, we show that resource bundles are able to provide high accuracy for statistical resource discovery, while achieving high scalability. We also show that resource bundles are ideally suited for identifying group-level characteristics (e.g. hot spots, total group capacity). To automatically parameterize the bundling algorithm, we present an adaptive algorithm that can detect online fluctuations in resource heterogeneity.

PrePrint: Impact of Feature Reduction on the Efficiency of Wireless Intrusion Detection Systems

Intrusion Detection Systems (IDS) are a major line of defense for protecting network resources from illegal penetrations. A common approach in intrusion detection models, specifically in anomaly detection models, is to use classifiers as detectors. Selecting the best set of features is very central to ensure the performance, speed of learning, accuracy, reliability of these detectors and to remove noise from the set of features used to construct the classifiers. In this paper, we propose a novel hybrid model that efficiently selects the optimal set of features in order to detect 802.11 specific intrusions. Our model of feature selection uses the information gain ratio measure as a mean to compute the relevance of each feature and the k-means classifier to select the optimal set of MAC layer features that can improve the accuracy of intrusion detection systems while reducing the learning time of their learning algorithm. Experimental results with three types of neural networks architectures show clearly that the optimization of the wireless feature set has a significant impact on the efficiency and accuracy of the intrusion detection system.

PrePrint: Adaptive Workload Prediction of Grid Performance in Confidence Windows

Predicting grid performance is a complex task, because heterogeneous resource nodes are involved in a distributed environment. Long-execution workload on a grid is even harder to predict due to heavy load fluctuations. In this paper, we use Kalman filter to minimize the prediction errors. We apply Savitzky-Golay filter to train a sequence of confidence windows. The purpose is to smooth the prediction process from being disturbed by load fluctuations. We present a new adaptive hybrid method (AHModel) for load prediction guided by trained confidence windows. We test the effectiveness of this new prediction scheme with real-life workload traces from two Grid platforms: the AuverGrid and Grid5000 in France. Both theoretical analysis and experimental results are presented in this paper. As the lookahead span increases from 10 to 50 steps (5 minutes per step), the AHModel predicts the grid workload with a mean-square error (MSE) of (0.04% ~ 0.73%), compared with a much greater MSE of (2.54% ~ 30.2%) in using the static point-value autoregression (AR) prediction method. The significant gain in prediction accuracy makes the new model very attractive to predict Grid performance. The model was proven especially effective to predict large workload that demands very long execution time, such as exceeding 4 hours on the Grid5000 over 5,000 processors. With minor changes of some key system parameters, the AHModel can apply to other computational grids as well. At the end, we discuss extended research issues and tool development for Grid performance prediction.

PrePrint: Optimal Resource Placement in Structured Peer-to-Peer Networks

Utilizing the skewed popularity distribution in P2P systems, common in Gnutella and KazaA like P2P applications, we propose an optimal resource (replica or link) placement strategy, which can optimally tradeoff the performance gain and paid cost. The proposed resource placement strategy, with better results than existing works, can be generally applied in randomized P2P systems (Symphony) and deterministic P2P systems (e.g. Chord, Pastry, Tapestry, etc). We apply the proposed resource placement strategy respectively to two novel applications: PCache (a P2P based caching scheme) and PRing (a P2P ring structure). The simulation results as well as a real deployment on Planetlab demonstrate the effectiveness of the proposed resource placement strategy in reducing the average search cost of the whole system.

PrePrint: SocioNet: A Social-Based Multimedia Access System for Unstructured P2P Networks

Increasingly, peer-to-peer (P2P) network users expect to be able to search objects by semantic attributes based on their preferences for multimedia content. Partial match search (i.e., search through the use of multimedia content semantic information) has become an essential service in P2P systems. In this paper, we propose SocioNet, a social-based overlay that clusters peers based on their preference relationships as a small world network. In SocioNet, peers mimic how people form a social network and how they query, by preference, their friends or acquaintances. Hence, SocioNet benefits from two desirable features of a social network: interest-based clustering and small-world properties (i.e., high cluster coefficient among all peers yet short path lengths between any two peers). To realize an interest-based small-world SocioNet, we also investigate the following practical design issues: 1) similarity estimation: we define a quantifiable similarity measure that enables clustering of similar peers in SocioNet, 2) distributed small-world overlay adaptation: peers maintain a small-world overlay under network dynamics, and 3) query strategy under the small-world overlay: we analyze appropriate settings for the Time-to-Live (TTL) value, for TTL-limited flooding, that provides a satisfactory success ratio and avoids redundant message overhead. We use simulations and a real database called AudioScrobbler, which tracks users' listening habits, to evaluate the performance of SocioNet. The results show that SocioNet assists peers in locating content at peers with similar interests through short path lengths, and hence, achieves a higher success ratio (than non-small-world interest-based overlays and non-interest-based small-world overlays) while reducing message overhead significantly.

PrePrint: The Synchronization Power of Coalesced Memory Accesses

Multicore architectures have established themselves as the new generation of computer architectures. As part of the one core to many cores evolution, memory access mechanisms have advanced rapidly. Several new memory access mechanisms have been implemented in many modern commodity multicore architectures. By specifying how processing cores access shared memory, memory access mechanisms directly influence the synchronization capabilities of multicore architectures. Therefore, it is crucial to investigate the synchronization power of these new memory access mechanisms. This paper investigates the synchronization power of coalesced memory accesses, a family of memory access mechanisms introduced in recent large multicore architectures such as the Compute Unified Device Architecture (CUDA). We first define three memory access models to capture the fundamental features of the new memory access mechanisms. Subsequently, we prove the exact synchronization power of these models in terms of their consensus numbers. These tight results show that the coalesced memory access mechanisms can facilitate strong synchronization between the threads of multicore architectures, without the need of synchronization primitives other than reads and writes. In the case of the contemporary CUDA processors, our results imply that the coalesced memory access mechanisms have consensus numbers up to sixty four.

PrePrint: Optimal Swarming for Massive Content Distribution

A distinct trend has emerged that the Internet is used to transport data on a more and more massive scale. Capacity shortage in the backbone networks has become a genuine possibility, which will be more serious with fiber-based access. The problem addressed in this paper is how to conduct massive content distribution efficiently in the future network environment where the capacity limitation can equally be at the core or the edge. We propose a novel technique as a main content transport mechanism to achieve efficient network resource utilization. The technique uses multiple trees for distributing different file pieces, which at the heart is a version of swarming. In this paper, we formulate an optimization problem for determining an optimal set of distribution trees as well as the rate of distribution on each tree under bandwidth limitation at arbitrary places in the network. The optimal solution can be found by a distributed algorithm. The results of the paper not only provide stand-alone solutions to the massive content distribution problem, but should also help the understanding of existing distribution techniques such as BitTorrent or FastReplica.

PrePrint: The Topology of Gaussian and Eisentein-Jacobi Interconnection Networks

Earlier authors have used quotient rings of Gaussian and Eisenstein-Jacobi integers to construct interconnection networks with good topological properties. In this article we present a unified study of these two types of networks. Our results include decomposing the edges into disjoint Hamiltonian cycles, a simplification of the calculation of the Eisenstein-Jacobi distance, a distribution of the distances between Eisenstein-Jacobi nodes, and shortest path routing algorithms. In particular, the known Gaussian routing algorithm is simplified.

PrePrint: Stabilizing Distributed R-trees for Peer-to-Peer Content Routing

Publish/subscribe systems provide useful platforms for delivering data (events) from publishers to subscribers in a decoupled fashion. Developing efficient publish/subscribe schemes in dynamic distributed systems is still an open problem for complex subscriptions (spanning multi-dimensional intervals). We propose a distributed R-tree (DR-tree) structure that uses R-tree-based spatial filters to construct a peer-to-peer overlay optimized for scalable and efficient selective dissemination of information. We adapt well-known variants of R-trees to organize publishers and subscribers in balanced peer-to-peer networks that support content-based filtering in publish/subscribe systems. DR-tree overlays guarantee subscription and publication times logarithmic in the size of the network while keeping space requirements low (comparable to distributed hash tables). The maintenance of the overlay is local and the structure is balanced with height logarithmic in the number of nodes. DR-tree overlays disseminate messages with no false negatives and very few false positives in the embedded publish/subscribe system. In addition, we propose self-stabilizing algorithms that guarantee consistency despite failures and changes in the peer population.

PrePrint: On the Benefits of Cooperative Proxy Caching for Peer-to-Peer Traffic

Peer-to-peer (P2P) systems currently generate a major fraction of the total Internet traffic. This paper analyzes the potential of cooperative proxy caching for P2P traffic as a means to ease the burden imposed by P2P traffic on ISPs. In particular, we propose two models for cooperative caching of P2P traffic. The first model enables cooperation among caches that belong to different autonomous systems (ASes), while the second considers cooperation among caches deployed within the same AS. We analyze the potential gain of cooperative caching in these two models. To perform this analysis, we conduct an eight-month measurement study on a popular P2P system to collect traffic traces for multiple caches. Then, we perform extensive trace-based simulations to analyze different angles of cooperative caching schemes. Our results demonstrate that: (i) significant improvement in byte hit rate can be achieved using cooperative caching, (ii) simple object replacement policies are sufficient to achieve that gain, and (iii) the overhead imposed by cooperative caching is negligible. In addition, we develop a simple analytic model to assess the gain from cooperative caching in different settings. The model accounts for number of caches, salient P2P traffic features, and network characteristics. Our model confirms that substantial gains from cooperative caching are attainable under wide ranges of traffic and network characteristics.

PrePrint: Delay Bounded and Energy Efficient Composite Event Monitoring in Heterogeneous Wireless Sensor Networks

Wireless sensor networks can be used for event warning applications. To date, in most of the proposed schemes, the raw or aggregated sensed data is periodically sent to a data consuming center. However, with those schemes, the occurrence of an emergency event such as a fire is hardly reported timely which is a strict requirement for event warning applications. In wireless sensor networks, it is also highly desired to conserve energy so that network lifetime can be maximized. Furthermore, to ensure the quality of surveillance, some applications require that if an event occurs, it needs to be detected by at least k sensors where k is a user-defined parameter. In this work, we examine the Timely Energy-efficient k-Watching Event Monitoring problem (TEKWEM) and propose a scheme, which involves an event detection model and a warning delivery model, for monitoring composite events and delivering warnings to users. Theoretical analysis and simulation results are shown to validate the proposed scheme.

PrePrint: Isoefficiency Maps for Divisible Computations

In this paper we propose a new technique of presenting performance relationships in parallel processing. Performance of parallel processing is a hard matter with many counterintuitive phenomena. It is relatively easy to obtain some numerical indicators of performance using various performance models. However, it is far more difficult to comprehend the nature of the analyzed problem. To facilitate understanding performance relationships we propose a new visualization technique based on the concept of isoefficiency. In this paper isoefficiency is represented as a relation on points in the space of system parameters for which efficiency of parallel processing is equal. We visualize this relation on 2-dimensional maps analogously to isobars, and isotherms on weather maps. This concept is applied to depict performance relationships in two standard performance laws: Amdahl's speedup law, and Gustafson's speedup law. Then we use isoefficiency maps to analyze performance relationships in divisible load processing. Divisible load model conforms with data-parallel computations in an environment with communication delays. The results we obtain give interesting insights into relationships existing in parallel processing.

PrePrint: An Efficient and Adaptive Decentralized File Replication Algorithm in P2P File Sharing Systems

In peer-to-peer file sharing systems, file replication technology is widely used to reduce hot spots and improve file query efficiency. Most current file replication methods replicate files in all nodes or two endpoints on a client-server query path. However, these methods either have low effectiveness or come at a cost of high overhead. These replication algorithms either cannot offer high effectiveness or come at a high cost of overhead. This paper presents an Efficient and Adaptive Decentralized file replication algorithm (EAD) that achieves high query efficiency and high replica utilization at a significantly low cost. EAD enhances the utilization of file replicas by selecting query traffic hubs and frequent requesters as replica nodes, and dynamically adapting to non-uniform and time-varying file popularity and node interest. EAD creates and deletes replicas in a decentralized self-adaptive manner while guarantees high replica utilization. Theoretical analysis shows the high performance of EAD. Simulation results demonstrate the efficiency and effectiveness of EAD in comparison with other approaches in both static and dynamic environments. It dramatically reduces the overhead of file replication, and yields significant improvements on the efficiency and effectiveness of file replication in terms of query efficiency, replica hit rate and overloaded nodes reduction.

PrePrint: Stabilization of Flood Sequencing Protocols in Sensor Networks

Flood is a communication primitive that can be used by the base station of a sensor network to send a copy of a message to every sensor in the network. When a sensor receives a flood message, the sensor needs to check whether it has received this message for the first time and so this message is fresh, or it has received the same message earlier and so the message is redundant. In this paper, we discuss a family of four flood sequencing protocols that use sequence numbers to distinguish between fresh and redundant flood messages. These four protocols are: a sequencing free protocol, a linear sequencing protocol, a circular sequencing protocol, and a differentiated sequencing protocol. We analyze the self-stabilization properties of these four flood sequencing protocols. We also compare the performance of these flood sequencing protocols, using simulation, over various settings of sensor networks. We conclude that the differentiated sequencing protocol has better stabilization property and provides better performance than those of the other three protocols.

PrePrint: The Signal Synchronous Multi-Clock Approach to the Design of Distributed Embedded Systems

This paper presents the design of distributed embedded systems using the synchronous multi-clock model of the Signal language. It proposes a methodology that ensures a correct-by-construction functional implementation of these systems from high-level models. It shows the capability of the synchronous approach to apply formal techniques and tools that guarantee the reliability of the designed systems. Such a capability is necessary and highly worthy when dealing with safety-critical systems. The proposed methodology is demonstrated through a case study consisting of a simple avionic application, which aims to pragmatically help the reader to understand the manipulated formal concepts, and to apply them easily in order to solve system correctness issues encountered in practice.

PrePrint: Cross-Domain Data Sharing in Distributed Electronic-Health-Record Systems

Cross-organization or cross-domain cooperation takes place from time to time in EHR (Electronic Health Record) system for necessary and high-quality patient treatment. Cautious design of delegation mechanism must be in place as a building block of cross-domain cooperation, since the cooperation inevitably involves exchanging and sharing relevant patient data which are considered highly private and confidential. The delegation mechanism grants permission to and restricts access rights of a cooperating partner. Patients are unwilling to accept the EHR system unless their health data are guaranteed proper use and disclosure, which cannot be easily achieved without cross-domain authentication and fine-grained access control. In addition, revocation of the delegated rights should be possible at any time during the cooperation. In this paper, we propose a secure EHR system, based on cryptographic constructions, to enable secure sharing of sensitive patient data during cooperation and preserve patient data privacy. Our EHR system further incorporates advanced mechanisms for fine-grained access control, and on-demand revocation, as enhancements to the basic access control offered by the delegation mechanism, and the basic revocation mechanism, respectively. The proposed EHR system is demonstrated to fulfill objectives specific to the cross-domain delegation scenario of interest.

PrePrint: Minimum-Latency Gossiping in Radio Wireless Networks

We studied the minimum-latency gossiping (all-to-all broadcast) problem in multi-hop radio networks defined as follows. Each node in the network is preloaded with a message and the objective is to distribute each node's message to the entire network with minimum latency. We studied this problem in the unit-size message model and the unit disk graph model. The unit-size model means different messages cannot be combined as one message, and the unit disk graph model means a link exists between two nodes if and only if their Euclidean distance is less than 1. The minimum-latency gossiping problem is known to be NP-hard in these two models. In this work we designed a gossiping scheme that significantly improved all current gossiping algorithms in terms of the approximation ratio. Our work has approximation ratio 27, a great improvement of the current state-of-the-art algorithm (which has ratio 1947). We also discussed the single point of failure problem and its impact on our approximation ratio. We designed an amended gossiping algorithm with ratio 27 in case of a non-source node failure. We also designed an amended gossiping algorithm with ratio 29 in case of source failure.

PrePrint: A Global Contribution Approach to Maintain Fairness in P2P Networks

For many P2P systems, implementing right incentives and policies to promote efficient and fair resource sharing is the key to improve the overall system performance. In this paper, we propose a points-based incentive mechanism named Global Contribution (GC) approach that efficiently and naturally maintains fairness in a P2P network. In this approach, a proposed GC algorithm first calculates a global score for each peer that accurately reflects its bandwidth contribution to the entire network. Then, these scores are used in a proposed data transfer policy to determine whether one peer can download data from other peers. Thus, the GC approach achieves: (1) efficiently preventing free riding, (2) naturally balancing the upload and download amounts in each peer, (3) reducing rejection rates in transactions between cooperative peers. Moreover, the GC algorithm requires only private transaction history as an input and can be fully decentralized. Also, its time complexity is approximately $O(N^2)$ in a centralized system and $O(N)$ per peer in a decentralized system.

PrePrint: On the Benefit of Processor Co-Allocation in Multicluster Grid Systems

In multicluster grid systems, parallel applications may benefit from processor co-allocation, that is, the simultaneous allocation of processors in multiple clusters. Although co-allocation allows the allocation of more processors than available in a single cluster, it may severely increase the execution time of applications due to the relatively slow wide-area communication. The aim of this paper is to investigate the benefit of co-allocation in multicluster grid systems, despite this drawback. To this end, we have conducted experiments in a real multicluster grid environment, as well as in a simulated environment, and we evaluate the performance of co-allocation for various applications that range from computation-intensive to communication-intensive and for various system load settings. In addition, we compare the performance of scheduling policies that are specifically designed for co-allocation. We demonstrate that considering latency in the resource selection phase improves the performance of co-allocation, especially for communication-intensive parallel applications.

PrePrint: Self-Consistent MPI Performance Guidelines

Message passing using the Message Passing Interface (MPI) is the most widely adopted framework for programming parallel applications for distributed-memory and clustered parallel systems. The MPI standard does not state any specific performance guarantees, but users expect MPI implementations to deliver good and consistent performance. For performance portability reasons, users also naturally desire communication optimizations performed on one parallel platform with one MPI implementation to be preserved when switching to another MPI implementation on another platform. We address the problem of ensuring performance consistency and portability by formulating performance guidelines and conditions that are desirable for good MPI implementations to fulfill. We formulate these guidelines by relating the performance of various aspects of the semantically strongly interrelated MPI standard to each other. Such guidelines may enable implementers to provide higher quality MPI implementations, minimize performance surprises, and eliminate the need for users to make special, non-portable optimizations by hand. We introduce and semi-formalize the concept of self-consistent performance guidelines for MPI, and provide a (non-exhaustive) set of such guidelines in a form that could be automatically verified by benchmarks and experiment-management tools. We present experimental results that show cases where guidelines are not satisfied in common MPI implementations, thereby indicating room for improvement in today's MPI implementations.

PrePrint: Streamline: An Optimal Distribution Algorithm for Peer-to-Peer Real-time Streaming

In this paper we propose and evaluate an overlay distribution algorithm for P2P, chunk-based, streaming systems over forest-based topologies. In such systems, the stream is divided in chunks and peers are logically organized in a forest of trees, where each tree includes all peers. The source periodically distributes different chunks to each tree for their delivery. Our key idea consists in employing serial transmission: for each tree and thus for each chunk, the source node sends the chunk to its children in series; the same holds for each peer node of the tree, excluding the leaves. Besides this basic idea, the contributions of this paper are: 1) we demonstrate the feasibility of serial transmission over a forest of trees, which is not a trivial problem, unlike the case of parallel transmission; 2) we derive an analytical model to evaluate the system performance; 3) we derive a theoretical bound for the number of nodes reachable in a given time interval or equivalently for the time required to reach a given number of nodes; 4) we prove the optimality of our approach in terms of its capability to reach such bound; 5) we develop a general simulation package for P2P streaming systems and we use it to compare our solution to literature results. Finally, we briefly describe also a practical workable implementation of our algorithm.

PrePrint: Update Scheduling for Improving Consistency in Distributed Virtual Environments

The fundamental goal of distributed virtual environments (DVEs) is to create a common and consistent presentation of the virtual world among a set of computers inter-connected by a network. This paper investigates update scheduling algorithms to make efficient use of network capacity and improve consistency in DVEs. Our approach is to schedule state updates according to their potential impacts on consistency. In DVEs, the perceptions of participants are affected by both the spatial magnitude and temporal duration of inconsistency in the virtual world. Using the metric of time-space inconsistency, we analytically derive the optimal update schedules for minimizing the impact of inconsistency. Based on the analysis, we propose a number of scheduling algorithms that integrate spatial and temporal factors. These algorithms also take into consideration the effect of network delays. The algorithms can be used on top of many existing mechanisms such as dead reckoning. Experimental results show that our proposed algorithms significantly outperform the intuitive algorithms that are based on spatial or temporal factors only.

PrePrint: Energy-Efficient Protocol for Deterministic and Probabilistic Coverage in Sensor Networks

Various sensor types, e.g., temperature, humidity, and acoustic, sense physical phenomena in different ways, and thus are expected to have different sensing models. Even for the same sensor type, the sensing model may need to be changed in different environments. Designing and testing a different coverage protocol for each sensing model is indeed a costly task. To address this challenging task, we propose a new probabilistic coverage protocol (denoted by PCP) that could employ different sensing models. We show that PCP works with the common disk sensing model as well as probabilistic sensing models, with minimal changes. We analyze the complexity of PCP and prove its correctness. In addition, we conduct an extensive simulation study of large-scale sensor networks to rigorously evaluate PCP and compare it against other deterministic and probabilistic protocols in the literature. Our simulation demonstrates that PCP is robust, and it can function correctly in presence of random node failures, inaccuracies in node locations, and imperfect time synchronization of nodes. Our comparisons with other protocols indicate that PCP outperforms them in several aspects, including number of activated sensors, total energy consumed, and network lifetime.

PrePrint: Coupling-Based Internal Clock Synchronization for Large Scale Dynamic Distributed Systems

This paper studies the problem of realizing a common software clock among a large set of nodes without an external time reference, any centralized control and where nodes can join and leave the distributed system at their will. The paper proposes an internal clock synchronization algorithm which combines the gossip-based paradigm with a nature-inspired approach, coming from the coupled oscillators phenomenon, to cope with scale and churn. The algorithm works on the top of an overlay network and uses a uniform peer sampling service to fullfill each node's local view. Therefore, differently from clock synchronization protocols for small scale and static distributed systems, here each node synchronizes regularly with only the neighbors in its local view and not with the whole system. Theoretical and empirical evaluations of the convergence speed and of the synchronization error of the synchronization algorithm have been carried out, showing how these properties depend on the coupling factor and on the local view size. Moreover the impact of churn and of a sudden variation of the number of nodes has been analyzed to show the stability of the algorithm. In all these contexts, the algorithm shows nice performance and very good self-organizing properties.

PrePrint: Inverting Systems of Embedded Sensors for Position Verification in Location-Aware Applications

Wireless sensor networks are typically deployed to monitor phenomena that vary over the spatial region the sensor network covers. The sensor readings may also be dual-used for additional purposes. In this paper we propose to use the inherent spatial variability in physical phenomena, such as temperature or ambient acoustic energy, to support localization and position verification. We first present the problem of localization using general spatial information fields, and then propose a theory for exploiting this spatial variability for localization. Our Spatial Correlation Weighting Mechanism (SCWM) uses spatial correlation across different phenomena to isolate an appropriate subset of environmental parameters for better location accuracy. We then develop an array of algorithms employing environmental parameters using a two-level approach: first, we develop the strategies on how the subset of parameters should be chosen, and second we derive mapping functions for position estimation. Our algorithms support our theoretical model for performing localization utilizing environmental properties. Finally, we provide an experimental evaluation of our approach by using a collection of physical phenomena measured across one hundred locations inside a building. Our results provide strong evidence of the viability of using general sensor readings for location-aware applications.

PrePrint: Connectivity-Based Skeleton Extraction in Wireless Sensor Networks

Many sensor network applications are tightly coupled with the geometric environment where the sensor nodes are deployed. The topological skeleton extraction for the topology has shown great impact on the performance of such services as location, routing, and path planning in wireless sensor networks. Nonetheless, current studies focus on using skeleton extraction for various applications of in wireless sensor networks. How to achieve a better skeleton extraction has not been thoroughly investigated. There are studies on skeleton extraction from the computer vision community; their centralized algorithms for continuous space, however, are not immediately applicable for the discrete and distributed wireless sensor networks. In this paper we present CASE: a novel Connectivity-bAsed Skeleton Extraction algorithm to compute skeleton graph that is robust to noise, and accurate in preservation of the original topology. In addition, CASE is distributed as no centralized operation is required, and is scalable as both its time complexity and its message complexity are linearly proportional to the network size. The skeleton graph is extracted by partitioning the boundary of the sensor network to identify the skeleton points, then generating the skeleton arcs, connecting these arcs, and finally refining the coarse skeleton graph. We believe that CASE has broad applications and we present a skeleton-assisted segmentation algorithm as an example. Our evaluation shows that CASE is able to extract a well-connected skeleton graph in the presence of significant noise and shape variations, and outperforms the state-of-the-art algorithms.

PrePrint: Efficient Algorithms for Global Snapshots in Large Distributed Systems

Existing algorithms for global snapshots in distributed systems are not scalable when the underlying topology is complete. There are primarily two classes of existing algorithms for computing a global snapshot. Algorithms in the first class use control messages of size O(1) but require O(N) space and O(N) messages per processor in a network with N processors. Algorithms in the second class use control messages (such as rotating tokens with vector counter method) of size O(N), use multiple control messages per channel, or require recording of message history. As a result, algorithms in both of these classes are not efficient in large systems when the logical topology of the communication layer such as MPI is complete. In this paper, we propose three scalable algorithms for global snapshots: a grid-based, a tree-based and a centralized algorithm. The grid-based algorithm uses O(N) space but only O(sqrt(N)) messages per processor each of size O(sqrt(N)). The tree-based and centralized algorithms use only O(1) size messages. The tree-based algorithm requires O(1) space and O(logN log (W/N)) messages per processor where W is the total number of messages in transit. The centralized algorithm requires O(1) space and O(log (W/N)) messages per processor. We also have a matching lower bound for this problem. We also present hybrid of centralized and tree-based algorithms that allow trade-off between the decentralization and the message complexity. Our algorithms have applications in checkpointing, detecting stable predicates and implementing synchronizers.

PrePrint: Real-Time Modeling of Wheel-Rail Contact Laws with System-on-Chip

This paper presents the development and implementation of a multiprocessor system-on-chip solution for fast and real time simulations of complex and nonlinear wheel-rail contact mechanics. There are two main significances in this paper. Firstly, the wheel-rail contact laws (including Hertz and Fastsim algorithms), which are widely used in the study of railway vehicle dynamics, are restructured for improved suitability that can take advantage of the rapid developing multiprocessor technology. Secondly, the complex algorithms for the contact laws are successfully implemented on a medium-sized FPGA (Field-Programmable-Gate-Array) device using six NiosII processors, where the executions of the Hertz and Fastsim parts are pipelined to achieve further enhancement in doing multiple contacts and the operation scheduling is optimized. In the Fastsim part the floating point units with buffering mechanism are efficiently shared by five processors connected in a token ring topology. The FPGA design shows good flexibility in utilizing logic element and on-chip memory resource on the device and scalability for a significant speed-up on a larger device in future work.

PrePrint: Realistic Workload Modeling and Its Performance Impacts in Large-Scale eScience Grids

Grid computing proves to be a successful paradigm for large-scale distributed data processing, and global eScience Grids have been in production for years (e.g. LCG and OSG). The majority of applications running on these production environments can be characterized as massive CPU-intensive batch jobs (or "bag-of-tasks"), sometimes considered as the "killer" application for the Grid. A deep understanding of its main workload characteristics is not only necessary for realistic performance evaluation of the existing system, but also crucial to generate new insights into better resource allocation schemes. This paper presents a comprehensive statistical analysis of the workloads on production eScience Grid environments. We focus on second-order statistics and the scaling behavior of main job characteristics, namely job arrivals and job run times. A range of autocorrelation structures is identified and analyzed, including pseudo-periodicity, short-range dependence (SRD), and long-range dependence (LRD). We further develop mathematical models that are able to capture these salient properties in the workloads. Workload models, in turn, enable us to quantitatively evaluate the performance impacts of autocorrelations in Grid scheduling. The results indicate that autocorrelations in workloads result in system performance degradation, sometimes the difference can be as large as up to several orders of magnitude. Nevertheless, better performance can be achieved at the Grid level under bursty local background workloads. Such effects of workloads on systems are extensively analyzed and explained.

PrePrint: Energy-Efficient Beaconless Geographic Routing in Wireless Sensor Networks

Geographic routing is an attractive localized routing scheme for wireless sensor networks (WSNs) due to its desirable scalability and efficiency. Maintaining neighborhood information for packet forwarding can achieve a high efficiency in geographic routing, but may not be appropriate for WSNs in highly dynamic scenarios where network topology changes frequently due to nodes mobility and availability. We propose a novel online routing scheme, called Energy-Efficient Beaconless Geographic Routing (EBGR), which can provide loop-free, fully stateless, energy-efficient sensor-to-sink routing at a low communication overhead without the help of prior neighborhood knowledge. In EBGR, each node first calculates its ideal next-hop relay position on the straight line towards the sink based on the energy optimal forwarding distance, and each forwarder selects the neighbor closest to its ideal next-hop relay position as the next-hop relay using the RTS/CTS (Request-To-Send/Clear-To-Send) handshaking mechanism. We establish the lower and upper bounds on hop count and the upper bound on energy consumption under EBGR for sensor-to-sink routing, assuming no packet loss and no failures in greedy forwarding. Moreover, we demonstrate that the expected total energy consumption along a route towards the sink under EBG approaches to the lower bound with the increase of node deployment density. We also extend EBGR to lossy sensor networks to provide energy-efficient routing in the presence of unreliable communication links. Simulation results show that our scheme significantly outperforms existing protocols in wireless sensor networks with highly dynamic network topologies.

PrePrint: Automatic Prefetch and Modulo Scheduling Transformations for the Cell BE Architecture

Ease of programming is one of the main requirements for the broad acceptance of multi-core systems without hardware support for transparent data transfer between local and global memories. Software cache is a robust approach to provide the user with a transparent view of the memory architecture; but this software approach can suffer from poor performance. In this paper, we propose a hierarchical, hybrid software-cache architecture that targets enabling prefetch techniques. Memory accesses are classified at compile time into two classes: high-locality and irregular. Our approach then steers the memory references toward one of two specific cache structures optimized for their respective access pattern. The specific cache structures are optimized to enable high-level compiler optimizations to aggressively unroll loops, reorder cache references, and/or transform surrounding loops so as to practically eliminate the software cache overhead in the innermost loop. The cache design enables automatic prefetch and modulo scheduling transformations. Performance evaluation indicates that optimized software cache structures combined with the proposed prefetch techniques translate into speed-up between 10% and 20%. As a result of the proposed technique, we can achieve similar performance on the Cell BE processor as on a modern server-class multi-core such as the IBM PowerPC 970MP processor for a set of parallel NAS applications.

PrePrint: Null Data Frame: A Double-Edged Sword in IEEE 802.11 WLANs

Null data frames are a special but important type of frames in IEEE 802.11 WLANs. They are widely used in 802.11 WLANs for control purposes such as power management, channel scanning and association keeping alive. The wide applications of null data frames come from their salient features such as lightweight frame format and implementation flexibility. However, such features can be taken advantage of by malicious attackers to launch a variety of attacks on 802.11 WLANs. In this paper, we identify potential security vulnerabilities in current null data frame applications in 802.11 WLANs. We then study two types of attacks taking advantage of these vulnerabilities in detail, that are, functionality based Denial-of-Service attack and implementation based fingerprinting attack. We also evaluate their effectiveness based on extensive experiments. Furthermore, we design and implement novel defense mechanisms against the attacks, and evaluate their effectiveness based on extensive experiments. Although our proposed defenses help alleviate the vulnerabilities, completely eliminating the vulnerabilities brought by null data frames remains an open issue. Finally, we point out that our work has broader impact in that similar vulnerabilities exist in many other networks due to the adoption of simple and lightweight messages for control purpose.

PrePrint: A Synchronous Scheduling Service for Distributed Real-Time Java

Current trends in real-time systems point out Java as a new alternative to develop both centralized and distributed real-time systems. Many efforts have been devoted to develop the Real-Time Specification for Java (RTSJ), and there is substantial on-going activity to produce a straightforward and valuable Distributed Real Time Specification for Java (DRTSJ). The current paper provides a contribution to this latter activity defining, from different angles, a global synchronous scheduling service aligned with principles of some popular real-time architectures. This service orchestrates the system in such a way that it provides endto- end guarantees in the distributed transactions, guaranteeing their timely execution across the network and nodes. The service is described from a double point-of-view: the system one, characterizing a portable model; and the programmer one, defining a distributed object-oriented implementation of the model based on RTRMI. Eventually, it also presents results of an implementation carried out to judge the goodness of the service, offering some interesting clues on the predictability and performance that we may expect from a distributed real-time Java technology.

PrePrint: An Efficient Super-Peer Overlay-Construction and Broadcasting Scheme Based on Perfect Difference Graph

Two-layer hierarchy unstructured peer-to-peer (P2P) systems, comprising an upper layer of super-peers and an underlying layer of ordinary peers, are commonly used to improve the performance of large-scale P2P systems. However, the optimal super-peer network design involves several requirements including super-peer degree, network diameter, scalability, load balancing, and flooding performance. A perfect difference graph has desirable properties to satisfy the above design rationale of super-peers overlay network. This paper proposes a two-layer hierarchical unstructured P2P system in which a perfect difference graph (PDG) is used to dynamically construct and maintain the super-peer overlay topology. In addition, the broadcasting performance of the P2P system is enhanced through the use of a PDG-based forwarding algorithm which ensures that each super-peer receives just one lookup query flooding message. The theoretical results show that the proposed system improves existing super-peer hierarchical unstructured P2P systems in terms of a smaller network diameter, fewer lookup flooding messages, and a reduced average delay and the experimental results show that the proposed two-layer hierarchy P2P system performs very well in the dynamic network environment.

PrePrint: Toward Systematical Data Scheduling for Layered Streaming in Peer-to-Peer Networks: Can We Go Farther?

Layered streaming in P2P networks has become a hot topic recently. However, the "layered" feature makes the data scheduling quite different from that for non-layered streaming, and it hasn't been systematically studied yet. In this paper, firstly, according to the unique characteristics caused by layered coding, we present four objectives that should be addressed by scheduling: throughput, layer delivery ratio, useless packets ratio and subscription jitter prevention; then, a 3-stage scheduling approach LayerP2P is designed to request data, where the min-cost flow model, probability decision mechanism and multi-window remedy mechanism are used in Free Stage, Decision Stage and Remedy Stage, respectively, to collaboratively achieve the above objectives. With the basic version of LayerP2P and corresponding experiment results achieved in our previous work, in this paper, more effort are put on its mechanism details, and analysis to its unique features; besides, to further guarantee the performance under sharp bandwidth variation, we propose the enhanced approach by improving the Decision Stage strategy. Extensive experiments by simulation and real network implementation indicate it outperforms other schemes. LayerP2P has also been deployed in PDEPS Project in China, which is expected to be the first practical layered streaming system for education in p2p networks.

PrePrint: Exploring In-Situ Sensing Irregularity in Wireless Sensor Networks

The circular sensing model has been widely used to estimate performance of sensing applications in existing analyses and simulations. While this model provides valuable high-level guidelines, the quantitative results obtained may not reflect the true performance of these applications, due to the sensing irregularity introduced by existence of obstacles in real deployment areas and insufficient hardware calibration. In this project, we design and implement two Sensing Area Modeling (SAM) techniques useful in the real world. They complement each other in the design space. Physical Sensing Area Modeling (P-SAM) provides accurate physical sensing area for individual nodes using controlled or monitored events, while Virtual Sensing Area Modeling (V-SAM) provides continuous sensing similarity between nodes using natural events in an environment. With these two models, we pioneer an investigation of the impact of sensing irregularity on application performance, such as coverage scheduling. We evaluate SAM extensively in real-world settings, using testbeds consisting of 14 XSM motes. To study the performance at scale, we also provide an extensive 1,400-node simulation. Evaluation results reveal several serious issues concerning circular models, and demonstrate significant improvements in several applications when SAM is used instead.

PrePrint: A Cross-Layer Approach-Based Gnutella for Collaborative Virtual Environments over Mobile Ad-Hoc Networks

Collaborative Virtual Environments (CVEs) such as military training programs, emergency preparedness simulations, and online games place strict requirements on network performance when participating users share the 3D virtual environment through their mobile devices in an ad-hoc network. However, most support systems for existing CVEs are confined to a desktop setting, thus preventing collaboration while users are mobile. In this work, we propose and evaluate a Gnutella peer-to-peer network over mobile ad-hoc networks (MANETs) to support Mobile Collaborative Virtual Environment (MCVE) applications. Both architectures share some common features such as decentralization, self-reorganization, and self-healing. However, peer-to-peer networks and MANETs operate on different network layers and thus cause poor performance. To address this problem, we explore a novel cross-layer approach to improve the overall performance of CVEs over MANETs. The network layer should be aware of the user's physical position in the virtual environment (VE) in order to minimize network traffic and cope with a moderate workload between nodes. The protocol is based on a collaborative context-aware discovery process in which mobile nodes are located using both their state and interest in the Virtual Environment (VE). In this paper, we present a cross-layer approach model for collaborative virtual environment over MANET. We describe its implementation and evaluate its performance using NS2 simulator.

PrePrint: Quality of Trilateration: Confidence-Based Iterative Localization

The proliferation of wireless and mobile devices has fostered the demand for context aware applications. Location is one of the most significant contexts. Multilateration, as a basic building block of localization, however, has not yet overcome the challenges of (1) poor ranging meas-urement; (2) dynamic and noisy environments; (3) fluctuations in wireless communications. Hence, they often suffer poor accuracy and can hardly be employed in practical applications. In this study, we propose Quality of Trilateration (QoT) that quantifies the geometric relationship of objects and the ranging noise. Based on QoT, we design a confidence based iterative localization scheme, in which nodes dynamically select trilaterations with the highest quality for localization. To validate this design, a wireless sensor network prototype is deployed and results show that QoT well represents trilateration accuracy, and the proposed scheme significantly improve localization performances.

PrePrint: Gossip-Based Self-Management of a Recursive Area Hierarchy for Large Wireless SensorNets

A recursive multi-hop area hierarchy has a number of applications in wireless sensor networks, the most common being scalable point-to-point routing. In this paper, we consider the problem of maintaining a recursive multi-hop area hierarchy in large sensor networks. We present a gossip-based protocol, dubbed PL-GOSSIP, in which nodes, by using local-only operations and by periodically gossiping with their neighbors, collaboratively maintain such a hierarchy. Since the hierarchy is a complex distributed structure, PL-GOSSIP introduces special mechanisms for internode coordination and consistency enforcement. Yet, these mechanisms are seamlessly integrated within the basic gossiping framework. Through simulations and experiments with an actual embedded protocol implementations, we demonstrate that PL-GOSSIP maintains the hierarchy in a manner that addresses all the peculiarities of sensor networks. More specifically, it offers excellent opportunities for aggressive energy saving and facilitates provisioning energy harvesting infrastructure. In addition, it bootstraps and recovers the hierarchy after failures relatively fast while also being robust to message loss. Finally, it can seamlessly operate on real sensor node hardware in realistic deployment scenarios and can outperform existing state-of-the-art hierarchy maintenance protocols.

PrePrint: Evaluation and Optimization of the Robustness of DAG Schedules in Heterogeneous Environments

A schedule is said to be robust if it is able to absorb some degree of uncertainty in tasks duration while maintaining a stable solution. This intuitive notion of robustness has led to a lot of different metrics and almost no heuristics. In this paper, we perform an experimental study of these different metrics and show how they are correlated to each other. Additionally, we proposed different strategies for minimizing the makespan while maximizing the robustness: from an evolutionary metaheuristic (best solutions but longer computation time) to more simple heuristics making approximations (bad quality solutions but fast computation time). We compare these different approaches experimentally and show that we are able to find different approximations of the Pareto front for this bicriteria problem.