The past eight years have seen the emergence ofvehicular cloudsas a topic of research in its own right. Vehicular clouds were inspired by the insight that present-day vehicles feature an impressive array of on-board compute, storage and sensing capabilities. These on-board capabilities are a vast untapped resource that, at the moment, is wasted. One of the defining ways in which vehicular clouds differ from conventional clouds is resource volatility. As vehicles enter and leave the cloud, new compute resources become available while others depart, creating a volatile environment where the tasks of enhancing reliability and availability become very challenging. It is intuitively clear that the longer and more predictable the vehicle residency times in the cloud are, the easier it is to ensure reliability and system availability. In this work we look at vehicular clouds withshort and unpredictablevehicular residency times. We propose to enhance the reliability and availability of these types of vehicular clouds through a family of redundancy-based job assignment strategies that attempt to mitigate the effect of resource volatility. We offer a theoretical prediction of the Mean Time To Failure (MTTF) of these strategies. We also show how to fine-tune the granularity of the redundancy in order to meet QoS requirements specified in terms of a minimum MTTF for a given user job. Extensive simulations, using vehicle residency data derived from shopping mall statistics, have confirmed the accuracy of our analytical predictions.

Cloud Computing, a catchy metaphor for utility computing, implemented through the provisioning of various types of hosted services over the Internet, has seen phenomenal growth and quasi-universal adoption in the past two decades. The underlying business model of cloud computing is the familiar “pay-as-you-go” model of metered services, where a user pays for whatever he/she uses and no more, and where additional demand for service can be met in real time. This powerful idea was suggested, at least in part, by the pervasive low-cost high-speed Internet, a good handle on virtualization, and advances in parallel and distributed computing. Three aspects are novel in conventional cloud computing: First, it gives users the illusion of infinite computing resources available to them on demand. Second, it eliminates the up-front financial commitment by cloud users, allowing them to increase hardware/software resources as needed. Third, it gives users the ability to pay for resources on a short-term basis and release them when they are no longer needed.

Information leakage is the inadvertent disclosure of sensitive information through correlation of records from several databases/collections of a cloud data warehouse. Malicious insiders pose a serious threat to cloud data security and this justifies the focus on information leakage due to rogue employees or to outsiders using the credentials of legitimate employees. The discussion in this paper is restricted to NoSQL databases with a flexible schema. Data encryption can reduce information leakage, but it is impractical to encrypt large databases and/or all fields of database documents. Encryption limits the operations that can be carried on the data in a database. It is thus, critical to distinguish sensitive documents in a data warehouse and concentrate on efforts to protect them. The capacity of a leakage channel introduced in this work quantifies the intuitively obvious means to trigger alarms when an insider attacker uses excessive computer resources to correlate information in multiple databases. The Sensitivity Analysis based on Data Sampling (SADS) introduced in this paper balances the trade-offs between higher efficiency in identifying the risks posed by information leakage and the accuracy of the results obtained by sampling very large collections of documents. The paper reports on experiments assessing the effectiveness of SADS and the use of selective disinformation to limit information leakage. Cloud services identifying sensitive records and reducing the risk of information leakage are also discussed.

The increasing heterogeneity of cloud resources, and the increasing diversity of services being deployed in cloud environments are leading to significant increases in the complexities of cloud resource management.This paper presents an architecture to manage heterogeneous resources and to improve service delivery in cloud environments.A loosely-coupled, hierarchical, selfadapting management model, deployed across multiple layers, is used for heterogeneous resource management.Moreover, a service-specific coalition formation mechanism is employed to identify appropriate resources to support the process parallelism associated with high performance services.Finally, a proofof-concept of the proposed hierarchical cloud architecture, as realized in CloudLightning project, is presented.

In this paper, we introduce an energy-aware operation model used for load balancing and application scaling on a cloud. The basic philosophy of our approach is defining an energy-optimal operation regime and attempting to maximize the number of servers operating in this regime. Idle and lightly-loaded servers are switched to one of the sleep states to save energy. The load balancing and scaling algorithms also exploit some of the most desirable features of server consolidation mechanisms discussed in the literature.

Emerging Big Data applications increasingly require resources beyond those available from a single server and may be expressed as a complex workflow of many components and dependency relationships-each component potentially requiring its own specific, and perhaps specialized, resources for its execution. Efficiently supporting this type of Big Data application is a challenging resource management problem for existing cloud environments. In response, we propose a two-stage protocol for solving this resource management problem. We exploit spatial locality in the first stage by dynamically forming rack-level coalitions of servers to execute a workflow component. These coalitions only exist for the duration of the execution of their assigned component and are subsequently disbanded, allowing their resources to take part in future coalitions. The second stage creates a package of these coalitions, designed to support all the components in the complete workflow. To minimize the communication and housekeeping overhead needed to form this package of coalitions, the technique of combinatorial auctions is adapted from market-based resource allocation. This technique has a considerably lower overhead for resource aggregation than the traditional hierarchically organized models. We analyze two strategies for coalition formation: the first, history-based uses information from past auctions to pre-form coalitions in anticipation of predicted demand; the second one is a just-in-time-that builds coalitions only when support for specific workflow components is requested.

Bid-centric service descriptions have the potential to offer a new cloud service provisioning model that promotes portability, diversity of choice and differentiation between providers. A bid matching model based on requirements and capabilities is presented that provides the basis for such an approach. In order to facilitate the bidding process, tenders should be specified as abstractly as possible so that the solution space is not needlessly restricted. To this end, we describe how partial TOSCA service descriptions allow for a range of diverse solutions to be proposed by multiple providers in response to tenders. Rather than adopting a lowest common denominator approach, true portability should allow for the relative strengths and differentiating features of cloud service providers to be applied to bids. With this in mind, we describe how service descriptions can be augmented with additional information that allows the bid matching algorithm to make use of heterogeneous processing resources, such as GPUs and MICs.

We propose to look at the evolution of ideas related to parallel systems, algorithms, and applications during the past three decades and then glimpse at the future. The journey starts with massively parallel systems of the early nineties, transitions gently to computing for the masses on the clouds of the first decade of the new millennium, and continues with what we could expect from quantum computers and quantum parallelism in the next few decades. In the late 1980s several technology companies were tasked to build massively parallel systems for classified and unclassified work. Supercomputers built with high-performance processors and low-latency interconnection networks provided the computing cycles for a relatively small population of sophisticated users from National Laboratories and universities. For example, the Touchstone Delta and then the Paragon had a hypercube interconnection network connecting together hundreds or thousands i860s, RISC processors launched with great fanfare by Intel, but mostly forgotten today. Virtually all un-classified applications running on such systems required the development of parallel libraries and parallel algorithms for different areas of scientific computing. Well discuss in some depth an application in the area of structural biology we developed for the Touchstone Delta, the 3D structure determination of viruses with unknown symmetry at high resolution. The tide turned, and in the second half of the first decade of the new millennium utility computing captured the attention of the masses. Large farms of servers built with off-the-shelf components, the so-called clouds, appeared in different time zones on earth, rather than the sky, to support enterprize computing. Anybody with a credit card and a problem involving big data now had access to vast amounts of computing cycles and storage space. The number of Cloud Service Providers (CSPs), the spectrum of services offered by the CSPs, and the number of cloud users have increased dramatically during the last few years. For example, in 2007 the EC2 (Elastic Cloud Computing) was the first service provided by AWS (Amazon Web Services), five years later, in 2012, AWS was used by businesses in 200 countries. Amazons S3 (Simple Storage Service) has surpassed two trillion objects and routinely runs more than 1.1 million peak requests per second. Well-known methods to partition the data and process the data concurrently were rediscovered and given new names, the Elastic MapReduce service has launched 5.5 million clusters since the start of the service in May 2010. In our presentation well concentrate on the IaaS (Infrastructure as a Service) cloud delivery model, discuss several classes of applications running successfully on a cloud, and present the results of some cloud benchmarks. While the computer science and computer engineering communities were busy developing operating systems, file systems, compilers, and algorithms for parallel systems a physicist, albeit a very famous one, Richard Feynman, showed in 1982 that computers obeying the laws of classical physics will never be able to carry out some difficult tasks, for example, to exactly simulate a quantum system. He predicted that a system where information is encoded as properties of quantum particles and processed using reversible state transformations will be capable of delivering extraordinary computing power. A number of alternatives for building a quantum computer including quantum dots based on spin or charge, trapped ions in a cavity, liquid NMR (Nuclear Magnetic Resonance), quantum Hall effect, and other physical processes are now investigated in many labs around the world. The race to build a quantum computer is on. To understand why, we overview the physical phenomena exploited by quantum parallelism and then discuss Shors factoring algorithm which achieves an exponential speed-up compared with a classical one. In 2009 it took almost two years and hundreds of computers to factor a 768 bit number, it is estimated that it would take 1,000 times longer to factor a 1,024 bit number. A quantum computer would most likely be able to factor a 2,048 bit number in days. But, so far only quantum computers with few qubits were built thus, information encrypted with a few hundred bit keys is safe!!

In the service-oriented architecture introduced in D.C. Marinescu and J.P. Morrison (2007), the reputation affects the prices producers could ask for their resources, the prices consumers of resources are willing to pay, and the commission charged for every contract. In this paper we introduce the GRB algorithm to quantify the reputations of the participants. The system is self-organizing and this affects the space requirements and the communication complexity of the algorithm.

Recently we proposed algorithms for concurrent execution on multiple clusters [11]. In this case, data partitioning is done at two levels; first, the data is distributed to a collection of heterogeneous parallel systems with different resources and startup time, then, on each system the data is evenly partitioned to the available nodes. In this paper, we report on a simulation study of the algorithms.

The automation of the data processing pipeline for virus structure determination at high resolution is a very challenging problem. The interaction between the data collection process and the theoretical modeling and computer simulation is very complex; routine tasks are mixed with decision making processes and unforeseen conditions. This paper dissects some of the most difficult problems posed by the dynamic coordination of complex computational tasks in a large scale distributed data acquisition and analysis system. A flexible coordination model should be capable of accommodating user actions, handling system related activities such as resource discovery and resource allocation, permitting dynamic process description modification, allowing different level of abstraction, providing some level of fault tolerance and backtracking capability. The condensed graphs model of computing developed at University College Cork (UCC) which combines availability-, demand-, and control-driven computation seems to be the most promising for certain classes of problems and complements our previous efforts in developing an intelligent environment for large scale-distributed data acquisition and analysis workflow applications.

Quantum and biological information processing could revolutionize computing and communication in the third millennium. In the 2007 Boole Lecture, we discussed the necessity to explore alternative paradigms for computing and communication and presented some striking features of quantum information processing and provided some insights into quantum parallelism as well as quantum communication and teleportation.

In this paper, we report on a series of experiments involving the speedups obtainable with time-parallel simulation of wireless ad hoc networks. A mobile ad hoc network scenario involving the AODV and DSDV routing protocols was simulated. The results and the performance of the serial NS-2 simulator were compared to the time-parallel simulation method for wireless ad hoc networks, previously introduced by the authors. The results of the time-parallel simulation are approximations, and we find that there is a trade off between the precision of the simulation and the achievable speedup. However, it is possible to find compromises where a precision of the range of 95-98%, sufficient for most applications, can be obtained up to 10 times faster than the time needed by a serial simulation

In this paper we discuss the role of a broker in a market-oriented resource allocation model for large-scale heterogeneous systems. The simplified model is based upon a three party system, provider-broker-consumer. The allocation of resources is determined by their price, their utility to the consumer, and by the satisfaction of the consumer. The role of the broker is to add societal objectives to resource allocation algorithms and to mediate between greedy consumers and selfish providers. A simulation experiment was conducted to study the transient and the steady-state behavior of several performance measures, including the average consumer satisfaction, the average utility, and the hourly revenue.

The execution of a complex task in any environment requires planning. Planning is the process of constructing an activity graph given by the current state of the system, a goal state, and a set of activities. If we wish to execute a complex computing task in a heterogeneous computing environment with autonomous resource providers, we should be able to adapt to changes in the environment. A possible solution is to construct a family of activity graphs beforehand and investigate the means of switching from one member of the family to another when the execution of one activity graph fails. In this paper, we study the conditions when plan switching is feasible. Then we introduce an approach for plan switching and report the simulation results of this approach

Asymmetric links are common in wireless networks for a variety of physical, logical, operational, and legal considerations. An asymmetric link supports uni-directional communication between a pair of mobile stations and requires a set of relay stations for the transmission of packets in the other direction. We introduce a MAC layer protocol for wireless networks with Asymmetric links (AMAC). The MAC layer protocol requires fewer nodes to maintain silence during a transmission exchange than the protocols proposed in [1, 2]. We present a set of concepts and metrics characterizing the ability of a medium access control protocol to silence nodes which could cause collisions.

We introduce a scalable algorithm for time-parallel simulations of wireless ad hoc networks and report on our results. Our approach decomposes the simulation into overlapping temporal components; the individual components are computed using an unmodified sequential network simulator such as NS-2. Our algorithm is iterative and the accuracy of the results increases with the number of iterations. We find that the approach allows the simulation of ad hoc networks with a number of nodes larger than those feasible with sequential network simulators on single CPUs. The algorithm is scalable, we can simulate larger time intervals by increasing the number of virtual processors carrying out the simulation. We identify the parameters that can be investigated with the algorithm and report on the accuracy of our results and on the achieved simulation speedup

The global Internet is rich in commodity resources but scarce in specialized resources. We argue that a grid framework can achieve better performance if it separates management of commodity tasks from the management of the tasks requiring specialized resources. Assuming a relative homogeneity of the commodity resource providers, the determining factor of grid performance becomes the latency of entering into execution. This effectively transforms the resource allocation problem into a routing problem. We present an approach in which commodity tasks are distributed to the commodity service providers by request forwarding on the n-cycle overlay network. We provide algorithms for task allocation and for the maintenance of the overlay network. By ensuring that the algorithms use only narrow local information, the approach is easily scalable to millions of nodes. For task allocation algorithms in a commercial setting, fairness is of paramount importance. We investigate the properties of the proposed algorithms from the fairness point of view and show how adding several hops of random pre-walk to the algorithm can improve its fairness. Extensive simulations prove that the approach provides efficient task allocation on networks loaded up to 95% of their capacity.

A computational grid is a complex system. The state space of a complex system is very large and it is infeasible to create a rigid infrastructure implementing optimal policies and strategies which take into account the current state of the system. An alternative to a rigid infrastructure is to base the system's reactions on logical inference, planning, and learning, the quintessential elements of an intelligent system. An intelligent grid is one where societal services exhibit intelligent behavior. A coordination service acting as a proxy on behalf of end users reacts to unforeseen events, plans how to carry out complex tasks, and learns from the history of the system. Various policies implemented by the societal services of an intelligent grid, such as brokerage and matchmaking, are based upon rules and facts gathered with the aid of a monitoring service. The question we address is how to construct intelligent computational grids which are truly scalable and could respond to the needs of a diverse user community. We present a prototype of a system used for a virtual laboratory in computational biology.

Summary form only given. We discuss the semantics of process and case description necessary for the workflow management on a grid used for scientific applications and outline the structure of basic ontologies supporting the coordinated execution of complex tasks. We survey the core services provided by our environment and discuss in some detail the planning service.

We introduce ad hoc grids as a hierarchy of mobile devices with different computing and communication capabilities. An ad hoc grid allows a group of individuals to accomplish a mission, often in a hostile environment; examples of applications of ad hoc grids are disaster management, wild-fire prevention, and peacekeeping operations. We are concerned with the interplay between computing and communication in the power-constrained environment of an ad hoc grid.

The network traffic control strategies and algorithms are part of the feedback loop that allows such a complex system to operate at an optimal or near-optimal functioning point. Effective performance criteria are an important element for providing the feedback regarding the current state of the system; thus, they represent a key aspect of the design of network traffic control strategies and algorithms. We introduce three synthetic factors of merit regarding the quality of service, the quantity of service and the ratio of the two. The figures of merit may take into account multiple QoS attributes. Each of these figures of merit can be calculated either for individual flows, the flows with a common characteristic, e.g., belonging to the same class, or crossing the same router, or for all the flows in a network. We also define a coefficient of fairness among the flows with a common characteristic, as the ratio of the variance to the expected value of a factor of merit.

Software agents are expected to play an increasingly important role in computational, service, and data grids built around the Internet. We discuss attributes of mobile agents and propose criteria that may be used for qualitative and quantitative evaluation of mobile agent systems.

System stability is an important criterion in selecting an appropriate control or scheduling policy for re-entrant line systems. Traditionally, stability analysis was based on the concept of time boundedness and was studied using Foster's criterion, which is a special case of stochastic Lyapunov functions. We emphasized the concept of buffer boundedness as an alternative criterion for characterizing the stability of scheduling policies and analyzed the stability of re-entrant line systems using this concept. A Petri net based framework was introduced to represent the dynamic behavior of re-entrant line systems. The Petri net method has been shown to be intuitive, simple and efficient.

Abstract The 3D electron‐density determination of viruses, from experimental data provided by electron microscopy, is a data‐intensive computation that requires the use of clusters of PCs or parallel computers. In this paper we report on three parallel algorithms used for 3D reconstruction of asymmetric objects from their 2D projections. We discuss their computational, communication, I/O, and space requirements and present some performance data. The algorithms are general and can be used for 3D reconstruction of asymmetric objects for applications other than structural biology. Copyright © 2001 John Wiley & Sons, Ltd.

The simulation and modeling of complex physical systems often involves many components because (i) the physical system itself has components of differing natures, (ii) parallel computing strategies require many (somewhat independent) components, and (iii) existing simulation software applies only to simpler geometrical shapes and physical situations. We discuss how agent based networks are applied to such multi-component applications. The network agents are used to (a) control the execution of existing solvers on sub-components, (b) mediate between sub-components, and (c) coordinate the execution of the ensemble. This paper focuses on partial differential equation (PDE) models as an instance of the approach and describes the implementation of networks using the PELLPACK problem solving environment for PDEs and the Bond system for agent based computing. Copyright © 2000 John Wiley & Sons, Ltd.

In this paper we present a security framework for Bond, a message-oriented distributed object middleware for network computing. Bond Security Framework, BSF, allows developers to exercise performance-security tradeoffs and use the security model best suited for a specific application and for a given environment. BSF consists of an extensible core and a set of well-defined security interfaces. Any Bond object can become a secure object when extended with a dynamic property called bondSecurityContext.

We present a suite of tools for monitoring and analysis of paging and I/O activity of parallel programs. Then we discuss results of the measurements for several parallel programs. The tools we have developed allow the user to select the statements to be measured, and then to define the format of the trace record generated by each traceable event. The tools, written in Tcl/Tk are portable and easy to use. We report measurements of paging and I/O activity for a suite of programs used in structural biology, and on programs in the NAS Benchmark suite.

Describes an environment for visualization and processing of low-dose, low-contrast electron micrographs of biological specimens. We focus on image selection, the first step in the process of reconstruction of the 3D structure of a specimen from its projections. Noise from a variety of sources makes automatic detection of particle positions a difficult task. New image acquisition devices and modern electron microscopy methods require the processing and rendering of very large images (50-100 million pixels). We describe techniques for processing large images, algorithms for detecting particle positions on compressed images using the crosspoint method, and methods for position refinement. EMMA, an interactive visualization environment for experimenting with particle identification methods is presented.

Abstract The paper discusses data management techniques for mapping a large data space onto the memory hierarchy of a distributed memory MIMD system. Experimental results for structural biology computations using the Molecular Replacement Method are presented.

Abstract The paper discusses algorithms and programs for electron density averaging using a distributed memory MIMD system. Electron density averaging is a computationally intensive step needed for phase refinement and extension in the computation of the 3‐D structure of macromolecules like proteins and viruses. The determination of a single structure may require thousands of hours of CPU time for traditional supercomputers. The approach discussed in this paper leads to a reduction by one to two orders of magnitude of the computing time. The program runs on an Intel iPSC/860 and on the Touchstone Delta system and uses a user controlled shared virtual memory and a dynamic load‐balancing mechanism.

Petri net models for the Horn clause form of propositional logic and of first-order predicate logic are studied. A net model for logical inconsistency check is proposed. Algorithms for computing T-invariants of Petri net models of logical inference systems are investigated. The algorithms are based on the idea of resolution and exploit the presence of one-literal, pure-literal, and splitting clauses to lead to faster computation. Algorithms for computing T-invariants of high-level Petri net (HLPN) models of predicate logic are presented.>

The VERT (verification of real-time programs) project is surveyed. The goal of the project is to assist the development of correct real-time programs. VERT is based on modeling concurrent programs with colored Petri nets. The investigations of the net model of the program reveal static and dynamic properties of the original program. In particular critical path analysis of the nets is used to determine if the program meets the timing constraints. Several aspects of the VERT project are addressed: translation of concurrent programs into colored Petri net models, algorithms for analysis, and visualization of net models.>

The problem of using the idle cycles of a number of high-performance workstations, interconnected by a high-speed network, for solving computationally intensive tasks is discussed. The classes of distributed applications examined require some form of synchronization among the sub-tasks, hence the need for coscheduling to guarantee that sub-tasks start at the same time and execute at the same pace on a group of workstations. A model of the system that allows the definition of an objective function to be maximized is presented. Then a quadratic time and linear space algorithm is derived for computing the optimal coscheduling.>

Abstract Synchronization is a major cause of wasted computing cycles and of diminished performance in parallel computing. This paper investigates the effects of synchronization upon the performance of iterative methods on distributed memory MIMD machines. A quantitative analysis of the effects of the communication latency and of the load imbalance due to the non‐deterministic execution times for iterative methods is presented. This analysis explains the rather poor performance observed often in actual implementations of such methods and suggests better ways to achieve convergence without frequent synchronization.

The design of a debugging and performance analysis system that includes a specification language for process-level events and hardware for nonintrusive identification of these events during the execution of parallel and distributed application for a nonshared memory system is presented. The design is based on a formal event/action model and a layered architecture model that have been previously presented. Background, related work, and specification, and identification of events are discussed.>

A multiple access protocol with real-time delivery constraints is introduced, and its properties are investigated. The modified shortest time to extinction (MSTE) algorithm implements a pseudo shortest time to extinction scheduling policy. The salient features of the algorithm are: it allows transmission of messages belonging to several classes of criticality, it takes into account the actual priority of a message in a given class and it rejects packets with deadlines shorter than a minimum acceptance deadline defined for a particular class.>

Several aspects of the multidimensional problem of providing monitoring support for the debugging and performance analysis of distributed and parallel systems and parallel applications are presented. The key elements of the solution to the problem are a formal event-action model at the process level and a layered architectural model. The application of the event-action model to the development of the abstract layered architectural model is shown, as well as a proposed implementation sketch of a nonintrusive monitor for the PASM parallel processing system.>

Request-response communication is studied in the framework of the functional communication model. A scheme that uses the channel access algorithm for distributed scheduling is investigated. A timed token protocol is used to control the two access modes, the scheduled access, with communication initiated by a server, and the nonscheduled access when a client sends a request to a functional group without prior consent from any of the servers in the group. In case of scheduled communication, the server guarantees the acceptance of the request.>

A class of stochastic Petri nets called stochastic high-level Petri nets (SHLPNs) is proposed. SHLPNs are high-level Petri nets augmented with exponentially distributed firing times. SHLPNs generally lead to models with a smaller state space. A computer marking concept is introduced that allows a considerable reduction of the number of states and induces a correct grouping of states in the Markov-domain SHLPN models of multiprocessor systems. The main advantage of modeling homogeneous systems using SHLPNs is that the resulting models are simpler and more intuitive and have a smaller number of states, as shown by examples.>

Abstract This paper surveys inter‐process communication in MVS/XA (multiple virtual system/extended architecture) and explores the use of cross‐memory services for this purpose. The lack of high‐level interfaces to system services is a major handicap in MVS/XA. Tools to provide high‐level services, in particular, tools for inter‐process communication, can be implemented in a simple, elegant and efficient way. The implementation and use of a communication subsystem, the extended communication facility (ECF), are also described. The ideas and mechanisms presented are useful for many scientific and engineering applications running under MVS/XA. Examples include distributed systems, applications using concurrent programming, a quasi‐batch environment, communication subsystems, and mail subsystems.