Offloading of tasks to the cloud is one of the approaches to improve the performance of distributed applications. When monetary constraints are present, selection of the tasks to be offloaded becomes important in order to ensure efficient use of the available cloud resources. This becomes a challenge for large scale distributed applications as the decisions on offloading have to be made locally at the nodes without an exact global view of the system. In our earlier work, we modeled this challenge as a new class of formal problems termed cloudy knapsack problem and derived some theoretical bounds on the solution space for worst case task sequences. In many real world applications, the task sequences have inherent patterns which can be exploited to improve offloading. In this work, we propose a cloud offloading algorithm that exploits these patterns through offline and online learning. Experimental evaluation using realistic datasets for a cloud-assisted peer-to-peer search case study reveals that the proposed solution performs close to a hypothetical omniscient offloading algorithm having a complete view of the system. The proposed cloud-assisted peer-to-peer search engine provides a cost-effective approach to address scalability bottleneck in peer-to-peer search engines.

Spark is an in-memory big data analytics framework which has replaced Hadoop as the de facto standard for processing big data in cloud platforms. These frameworks run on cloud platforms where heterogeneity is a common scenario. Heterogeneity gets introduced due to the failure, addition or upgradation of nodes in the cloud platforms. It can arise from various factors such as variation in the number of CPU cores, amount of memory, disk read/write latencies across the nodes, etc. These factors have a significant impact on the performance of Spark jobs. Spark supports execution of a job on equal-sized executors which can result in under allocation of resources in a heterogeneous cluster. Insufficient resources can severely degrade the performance of CPU and memory intensive applications like machine learning, graph processing, etc. Existing techniques use equal-sized executors which can degrade the performance of jobs in heterogeneous environments. In this paper, we propose Sparker, an efficient resource-aware optimization strategy for Spark in heterogeneous clusters. It overcomes the limitation of heterogeneity in terms of CPU and memory resources by modifying the size of the executor. The executors are re-sized based on the available resources of the node. We have modified Spark source code to incorporate executor re-sizing strategy. Experimental evaluation on SparkBench benchmark shows that our approach achieves a reduction of up to 46% in execution time.

With continuously growing data, clusters also need to grow periodically to accommodate the increased demand of data processing. This is usually done by addition of newer hardware, whose configuration might differ from the existing nodes. As a result, clusters are becoming heterogeneous in nature. For many real world machine learning and data mining applications, data is represented in the form of graphs. Most of the existing distributed graph processing frameworks such as Pregel and Graphlab assume that the computational nodes are homogeneous. These frameworks split the graph into approximately equal subgraphs, which is appropriate for homogeneous clusters. In heterogeneous clusters, these frameworks perform poorly in most of the scenarios. To the best of our knowledge, GraphIVE is the only heterogeneity-aware graph processing framework. It learns the relative capabilities of the nodes based on runtime metrics of previous jobs and partitions the graph proportionally. However, it may not perform well if a new job differs drastically in terms of resource requirements when compared to previous jobs executed on the cluster. To overcome this limitation, we propose GraphSteal, a dynamic graph re-partitioning policy for vertex-cut based graph processing frameworks on heterogeneous clusters. GraphSteal dynamically re-partitions the graph based on the runtime characteristics of the job. To avoid computational skew in the cluster, it migrates edges from slow nodes to fast nodes. To demonstrate our approach, we modify the source code of Graphlab to incorporate dynamic graph re-partitioning strategy. Experimental results show that GraphSteal significantly improves the performance over Graphlab.

Heterogeneity could occur due to various reasons in a Hadoop cluster. This work primarily focuses on heterogeneity occurring due to varying read/write latency of disks. In case of similar disk latencies among the datanodes, balancing the blocks uniformly is a suitable choice. However, with time, the disk latencies can increase due to mechanical problems and bad sectors. Further, the disks which crash and become non-functional are replaced with newer disks which could be of newer generation and can have greater RPM. This leads to heterogeneity in terms of disk in the cluster which is otherwise homogeneous, and balancing uniformly according to disk utilization may not give optimal job runtime. To address this issue we propose a disk latency aware balancer, which balances the cluster taking both disk latency and disk space utilization into consideration. This strategy for balancing makes sure that a low latency disk gets higher number of blocks in comparison to high latency disk. Furthermore, we introduce a custom block placement strategy considering disk latency and other factors. Our preliminary results show an improvement of upto 20% in job runtime.

Graphlab, which is a framework for large graph processing currently does not support multiple job scheduling simultaneously. However, for efficient use of the cluster resources, it may be required to share the cluster among multiple jobs. The challenges in multi-job scheduling in the case of graph processing are different from other frameworks such as Hadoop. In Hadoop, it is possible to schedule multiple jobs by fairly allocating resources to the jobs. We show in this paper that such an approach does not provide optimal results in the case of graph processing. We propose Octopus, a fair multi-job scheduler for Graphlab. The scheduler uses two different algorithms viz., First Fit with round robin Filling (FFF) and First In First Out with round robin Filling (FIFOF) to schedule large jobs of a user. We compare the performance of both the algorithms on a 20-node cluster. Preliminary results show that non-preemptive time sharing approach among users exhibits significant gain in turnaround time when compared to spatial resource sharing.

Cloud resources like Amazon EC2 and Google Compute Engine have become an integral part of our life with their pay-per-use pricing models. On the other hand, attempts have also been made to create virtual clouds on the fly using available devices in the locality like smartphones and tablets. Such devices being equipped with powerful processors, this is a novel method of utilizing their normally unused computational capabilities. We attempt to design and develop a pricing model for such resources created for opportunistic computing. Since the values of the resources in these virtual clouds cannot be calculated, the pay-per-resource model has to give way to a pay-per-effort model. We model the scenario as a principal-agent problem with moral hazards and propose an incentive-driven Quality of Service (QoS) to ensure that the agents act appropriately. In view of the short contractual duration, we consider only deterministic contracts which are easy to understand and implement. We show that the mobile devices can be modeled as economic actors in a contractual arrangement and discuss how the optimal decisions are identified.

Cloud-assisted approaches for both peer-to-peer systems and mobile apps require optimized use of elastic cloud resources. Due to budget constraints, a subset of the tasks has to be selected for offloading considering context parameters like device battery level and task variability. This leads to the challenging problem of context-sensitive task scheduling on elastic resources with a limited global view, which is not addressed by existing works. We identify a new class of formal problems called cloudy knapsack problems to effectively model the same. Abstracting out the problem formally can spur future independent works related to different variants of the problem and corresponding bounds and optimal algorithms. We illustrate the global view related issues through simulations, identify some theoretical bounds for a variant of cloudy knapsack problems and discuss several open problems.

SUMMARY It is difficult to express the parallelism present in complex computations by using existing higher level abstractions such as MapReduce and Dryad. These computations include applications from wide variety of domains, like Artificial Intelligence, Decision Tree Algorithms, Association Rule Mining, Recommender Systems, Graph Algorithms, Clustering Algorithms, Compute Intensive Scientific Workflows, Optimization Algorithms, and so forth. Their execution graphs introduce new challenges in terms of programmer expressibility and runtime performance such as iterative and recursive computations, shared communication model, and so forth. We propose an extension to MapReduce, called Generate‐Map‐Reduce (GMR), targeted towards modeling these applications. GMR introduces a new Generate abstraction into the MapReduce framework that captures recursive computations. The runtime also supports iterative jobs and a distributed communication model by using shared data structures. We illustrate recursive computations with GMR by modeling complex applications such as simulated annealing, A* search, and adaptive quadrature computation that require recursive spawning of new tasks to handle variable degree of parallelism. GMR runtime supports caching of common data across iterations in memory and local disks. We illustrate how this caching helps in achieving significant speedup for iterative computations by modeling k‐means clustering. Copyright © 2013 John Wiley & Sons, Ltd.

Today, batch processing frameworks like Hadoop MapReduce are difficult to scale to multiple clouds due to latencies involved in inter-cloud data transfer and synchronization overheads during shuffle-phase. This inhibits the MapReduce framework from guaranteeing performance at variable load surges without over-provisioning in the internal cloud (IC). We propose BStream, a cloud bursting framework for MapReduce that couples stream-processing in the external cloud (EC) with Hadoop in the internal cloud (IC). Stream processing in EC enables pipelined uploading, processing and downloading of data to minimize network latencies. We use this framework to meet job deadlines. BStream uses an analytical model to minimize the usage of EC. We propose different checkpointing strategies that overlap output transfer with input transfer/processing and simultaneously reduce the computation involved in merging the results from EC and IC. Checkpointing further reduces job completion time. We experimentally compare BStream with other related works and illustrate performance benefits due to stream processing and checkpointing strategies in EC. Lastly, we characterize the operational regime of BStream.

Skew mitigation has been a major concern in distributed programming frameworks like MapReduce. It is becoming more prominent with the increasing complexity in user requirements and computation involved. We present Chisel, a self-regulating skew detection and mitigation policy for MapReduce applications. The novelty of the approach is that it involves no scanning or sampling of input data to detect skew and hence incurs low overhead, provides better resource utilization and maintains output order and file structure. It is also transparent to the users and can be used as a plugin whenever required. We use Hadoop to implement our skew handling policies. Chisel implements two skew handling policies for mitigating skew. It does late skew detection for map operators i.e at the last wave of map execution, where skewed maps are selected on the basis of remaining time to complete. More maps are created dynamically over remaining data per block. An early skew detection i.e before starting shuffle phase, is done for reduce operator. This prevents the expensive shuffle and sort phases from delaying skew detection and job completion time. Multiple reducers are created per skewed partition, each shuffling data from a subset of total maps and starts processing it when their portion of maps are over. They need not wait for the completion of all the maps. Therefore, the barrier between map and reduce phase no longer remains a constraint for effective resource utilization. Chisel additionally implements an online job profiler to determine the start point of reduce tasks and also modifies the capacity scheduler to distribute reduce tasks evenly in the cluster. Chisel significantly decreases the overall execution time of jobs and increases resource utilization. Improvement depends directly upon the availability of resources in the cluster and skewness in the job.

Optimizing ordered throughput not only improves the system efficiency but also makes cloud bursting transparent to the user. This is critical from the perspective of user fairness in customer-facing systems, correctness in stream processing systems, and so on. In this paper, we consider optimizing ordered throughput for near real-time, data-intensive, independent computations using cloud bursting. Intercloud computation of data-intensive applications is a challenge due to large data transfer requirements, low intercloud bandwidth, and best-effort traffic on the Internet. The system model we consider is comprised of two processing stages. The first stage uses cloud bursting opportunistically for parallel processing, while the second stage (sequential) expects the output of the first stage to be in the same order as the arrival sequence. We propose three scheduling heuristics as part of an autonomic cloud bursting approach that adapt to changing workload characteristics, variation in bandwidth, and available resources to optimize ordered throughput. We also characterize the operational regimes for cloud bursting as stabilization mode versus acceleration mode, depending on the workload characteristics like the size of data to be transferred for a given compute load. The operational regime characterization helps in deciding how many instances can be optimally utilized in the external cloud.

Co-operative peer-to-peer systems have lot of relevance due to their desirable properties like lack of centralized control and transparency. But in certain applications, the stability of peer-to-peer systems is affected when concentrated load spikes occur. In this work, we explore the case for cloud-assisted peer-to-peer systems to handle spikes using peer-to-peer search as a case study. We identify the issues involved in realizing cloud-assisted peer-to-peer systems and propose, implement and evaluate Cloud-Assisted Peer-to-Peer Search (CAPS) architecture which fits in with the co-operative nature of peer-to-peer systems. The experimental results show that CAPS provides stability to peer-to-peer search service during query spikes without affecting user experience adversely.

Service Registries form a core component of Services Computing. They have been successful in enabling loose coupling among services by storing, managing and exposing interface descriptions of available services in a standard description language. However, existing service registries fall short of fulfilling the promise of enabling automatic service discovery and invocation and usually are tied to a particular web service technology. We present RegSOP that uses a novel approach of utilizing behavioral descriptions of available services as the basis for registering and discovering services. Behavioral descriptions can be classified and made available to the programmer at development time without committing to any particular service instance or underlying web service technology. Further, RegSOP computes different relationships among service behavior and automatically builds an ontology of service behavior. RegSOP, therefore, reduces the discovery process at runtime to a quick lookup of service classname. We present the design and implementation of RegSOP and report our evaluation of its capabilities.

Advances in cloud computing have led to advances in infrastructure, platforms and user applications. But the operating system space hasn't really kept pace with these advancements. In this paper we propose a model for cloud OS with Kernel As A Service (KAAS) offering. We describe the notion of KAAS and use it as a building block for developing Cloud OS. The KAAS model serves as the basic enabler for cross kernel switching, this offers an attractive set of possibilities like load balancing across kernels, fault resilience against kernel failures etc. The design, implementation and performance study of the this Cloud Operating System (SICLOPS) is presented in the paper.

Abstract Various mechanisms for hardening the Linux kernel (for example, enforcing system call policies, device driver failure recovery, protection against exploitation of bugs in code) are proposed in the literature. The main problem with these mechanisms is that, they require changes in the kernel code leading to the possibility of introducing new bugs and hence increasing the testing time. We propose a message filter model as an extension to object‐oriented wrappers for the Linux kernel, to dynamically provide various filtering capabilities to the kernel. This model works as a comprehensive framework for specifying system call policies, handling device driver faults, protecting the kernel against exploits of bugs in code etc, without modifying the existing kernel code. This considerably reduces the possibility of creating new bugs in the kernel code. We have integrated policies for system call interception and device driver failure handling, into the Linux kernel (2.6.9), using message filter model. Our experiments show that the overhead due to our filter objects is very low, making it a useful mechanism for providing filtering capabilities to the Linux kernel. Copyright © 2010 John Wiley & Sons, Ltd.

Identifying the set of cognitive processes (CPs) a student can go through during computer programming is an interesting research problem. It can provide a better understanding of the human aspects in computer programming process and can also contribute to the computer programming education in general. The study identified the presence of a set of 42 CPs in computer programming (C language). The study used Verbal Protocol Analysis (VPA) in identifying these CPs. It is a qualitative study on the Verbal Protocols (VPs) of 19 students. Some of the CPs have been inferred by referring to the literature and some have been additionally identified by this study. The additional CPs found are confusion, hypothesis, interrogation, iteration, monitoring, recollection, recurrence, and translation. It is observed that programming involves the interplay of lower and higher CPs and needs various cognitive skills, which increase the processing load on the brain and make the programming process difficult and complex to learn and practice. The same set of CPs was found in both the effective and ineffective subjects. The research results can provide deeper knowledge to teachers on cognitive aspects of programming and the cognitive behavior of students during the programming process.

Sybil attack is one of the most challenging problems that plague current decentralized Peer-to-Peer systems. In Sybil attack, a single malicious user creates multiple peer identities known as sybils. These sybils are employed to target honest peers and hence subvert the system. In this paper, we propose a novel solution that enables all honest peers to protect themselves from sybils with high probability in large structured P2P systems. In our proposed sybil defense system, we associate every peer with another non-sybil peer known as SyMon. A given peer's SyMon is chosen dynamically such that the chances of both of them being sybils are very low. The chosen SyMon is entrusted with the responsibility of moderating the transactions involving the given peer and hence makes it almost impossible for sybils to compromise the system. We show the effectiveness of our proposed system in defending against Sybil attack both analytically and experimentally.

Data objects have to be replicated in large-scale distributed systems for reasons of fault tolerance, availability, and performance. Furthermore, computations may have to be scheduled on these objects, when these objects are part of a grid computation. Although replication mechanism for unstructured peer-to-peer (P2P) systems can place replicas on capable nodes, they may not be able to provide deterministic guarantees on searching. Replication mechanisms in structured P2P systems provide deterministic guarantees on searching but do not address node capability in replica placement. We propose Virat, a node-capability-aware P2P middleware for managing replicas in large-scale distributed systems. Virat uses a unique two-layered architecture that builds a structured overlay over an unstructured P2P layer, combining the advantages of both structured and unstructured P2P systems. Detailed performance comparison is made with a replication mechanism realized over OpenDHT, a state-of-the-art structured P2P system. We show that the 99th percentile response time for Virat does not exceed 600 ms, whereas for OpenDHT, it goes beyond 2000 ms in our test bed, created specifically for the aforementioned comparison.

This paper has provided a first step towards solid theoretical foundations of large scale distributed systems. It has focused on applying complex systems theories SOC and HOT to data management solutions in P2P grids. It argues that replica management solution over OpenDHT, the state of the art DHT deployment, is based on SOC and consequently achieves robustness even in the presence of churn but not optimal performance.

Services Computing is emerging as a new discipline. The acceptance of web services technology stems from the fact that services enable easy integration and interoperation of enterprise level distributed systems. However, currently software developers are forced to translate business level service requirements and encode them into programs using low level abstractions such as objects. We propose to introduce language constructs for Service Oriented Programming that would enable raising programming abstractions from objects to services.

Abstract Linux is an open‐source operating system, which has increased in its popularity and size since its birth. Various studies have been conducted in literature on the evolution of the Linux kernel, which have shown that there are considerable maintenance problems arising out of the coupling issues in the Linux kernel and this may hamper the evolution of the kernel in future. We propose an object‐oriented (OO) wrapper‐based approach to Linux kernel to provide OO abstractions to external modules. As the major growth of the size of the Linux kernel is in device drivers, our approach provides substantial benefits in terms of developing the device drivers in C++, although the kernel is in C. Providing reusability and extensibility features to device drivers improves the maintainability of the kernel. The OO wrappers provide several benefits to module developers in terms of understandability, development ease, support for OO modules, etc. The design and implementation of C++ wrappers for Linux kernel and the performance of a device driver re‐engineered in C++ are presented in this paper. Copyright © 2008 John Wiley & Sons, Ltd.

Traditional software development involves reusing and building upon off-the-shelf software libraries. This paradigm provides compile time availability of both, component interfaces as well as corresponding implementations. It enables developers to write programs that build on existing functionality without worrying much about the runtime. Service oriented computing presents a different environment that involves actively running components in the form of services. Here, a search step becomes necessary to first discover the component(s) that satisfy the specified requirements. Moreover, services may come up or go down dynamically leading to expiry of searched results which makes dependent programs highly brittle. In this paper, we propose a paradigm shift from objects to services as first class entities. We present service matching techniques defined across design time and runtime. Using these techniques we define language level operations involving services as operands leading to a novel approach for services based software development.

It is widely accepted that strong coupling such as common coupling should be used with caution among modules. Linux kernel is analyzed in terms of these common coupling instances and the results show the presence of excessive common coupling among modules. It is mentioned that unless the kernel is restructured with a bare minimum of common coupling, it would be exceedingly difficult to maintain kernel in the near future. We attribute this problem to the lack of data abstractions in the kernel. To support our argument, we have analyzed the cohesion in the Linux kernel both at the module level (file level) and function level. Although the cohesion at the function level is high, low cohesion prevails at the module level indicating the lack of focus on data abstractions at the module level. We believe that this is an inherent drawback in procedural paradigm where functionality is considered first rather than data. Hence, we suggest to migrate the kernel to object-oriented paradigm to minimize coupling among modules and increase cohesion within the modules. As performance is one of the prime concerns for an OS kernel, object oriented features can be introduced in the kernel in an incremental fashion using the technique of object-oriented wrappers.

The abundant computing resources available on the Internet has made grid computing over the Internet a viable solution, to scientific problems. The dynamic nature of the Internet necessitates dynamic reconfigurability of applications to handle failures and varying loads. Most of the existing grid solutions handle reconfigurability to a limited extent. These systems lack appropriate support to handle the failure of key-components, like coordinators, essential for the computational model. We propose a two layered peer-to-peer middleware, Vishwa, to handle reconfiguration of the application in the face of failure and system load. The two-layers, task management layer and reconfiguration layer, are used in conjunction by the applications to adapt and mask node failures. We show that our system is able to handle the failures of the key-components of a computation model. This is demonstrated in the case studies of two computational models, namely bag of tasks and connected problems, with an appropriate example for each

The current state-of-the-art generational garbage collector pauses all the program threads when it performs young and old generation garbage collection. As the number of program threads increases, the delay due to garbage collection also increases, thus restricting the scalability of the collector. In order to improve the scalability and reduce the pause time, an on-the-fly generational garbage collector called Yama is proposed for multiprocessor systems. This uses the on-the-fly deferred reference counting in the young generation and the DLG (Doligez Leroy Gonthier) on-the-fly mark and sweep garbage collector in the old generation. We have proposed and experimented with two novel variations of the on-the-fly deferred reference counting called Chitragupt1 and Chitragupt2 in the young generation. Yama does not pause all the application threads simultaneously. An adaptive tenuring policy based on object reference count and survival rate is also proposed. Yama has been implemented in the IBM Jikes RVM (research virtual machine). The above claims are supported with experimental results for standard benchmark programs. The results show that Yama has an extremely low pause time in both the young and the old generation. The pause time reduction results in better response times for the user programs.

Refactoring in object-orientation has gained increased attention due to its ability to improve design quality. Refactoring using design patterns (DPs) leads to production of high quality software systems. Although numerous tools related to refactoring exist, only a few of them apply design patterns in refactoring. Even these do not clearly specify where refactoring can be applied and when to apply appropriate design patterns.In this paper, we propose a tool, JIAD (Java based Intent-Aspects Detector) which addresses the refactoring issues such as, the scope for applying DPs in the code and the appropriate selection of DPs. The tool automates the identification of Intent-Aspects (IAs) which helps in applying suitable design patterns while refactoring the Java code. By automating the process of identifying IAs, the whole process of refactoring using DPs can be automated which enables rapid development of software systems. Also, the tool minimizes the number of possible errors while inferring the suitable DPs to apply refactoring. Our approach primarily focuses on Java code refactoring using declarative programming and AspectJ compiler. Finally, the tool is validated using two applications namely, JLex and Java2Prolog written in Java.

Concurrency control (CC) algorithms targeted at Web systems need to be different from those of traditional transactional processing systems. In Web systems, transactions could be generated in a burst mode, leading to scalability problems at the server. Transactions may also suffer from network delays due to the unpredictable response time over the Web. This paper proposes a CC mechanism for Web-based three tier systems. In this mechanism, initial validation of the transactions is performed at the application server. The transactions that pass the initial validation are sent to the database server (DB server) for final validation. The serializability criterion is achieved by associating a data-counter with each data-item. This reduces the load on the DB server. Also, in the proposed model, the middle tier contains multiple number of application servers. Apart of the database is dynamically replicated in these servers. The modifications made on the data-items are known immediately to clients and the data-items at the DB server are locked only during the final validation phase and write phase. Consequently, the model is also suitable for transactions that suffer from unpredictable delays between read and write operations. The model is scalable as it can support large number of application servers in the middle tier. Performance studies have been carried out to depict the efficiency of the proposed model over the existing models. The proposed model is simple to implement and it performs extremely well compared to existing models when the transactions are generated in a burst mode.

This paper explores the transparent programmability of communicating parallel tasks in a Network of, Workstations (NOW). Programs which are tied up with specific machines will not be resilient to the changing conditions of a NOW. The Distributed Pipes (DP) model enables location independent intertask communication among processes' across machines. This approach enables migration of communicating parallel tasks according to runtime conditions. A transparent programming model for a parallel solution to Iterative Grid Computations using DP is also proposed. Programs written using the model are resilient to the heterogeneity of nodes and changing conditions in the NOW. They are also devoid of any network related code. The design of runtime support and function library support are presented. An engineering problem, namely, the Steady State Equilibrium Problem, is studied over the model. The performance analysis shows the speedup due to parallel execution and scaled down memory requirements. We present a case where the effect of communication overhead can be nullified to achieve a linear to super-linear speedup. The analysis discusses performance resilience of Iterative Grid Computations and characterizes synchronization delay among subtasks and the effect of network overhead and load fluctuations on performance. The performance saturation characteristics of such applications are also studied.

Patterns are a means for capturing experience in solving general problems. They give general solutions to common and recurring problems. They exist at various phases of the software development life-cycle (SDLC), namely the analysis phase, the design phase, the coding phase and the testing phase. Patterns in each phase are identified independently. It is possible for the patterns of one phase to be related to patterns in other phases. This paper proposes pattern mapping to inter-relate the patterns of various phases in SDLC to address this issue. It is advantageous to capture the related patterns of different phases as a single unit for software development. Reusable integrated components (ICs) of patterns are proposed to capture the related patterns. A software IC is a group of inter-related patterns, that gives solutions for a recurring problem at various phases of SDLC. A representation mechanism for ICs is presented using the URA (Unified Representation of an Artifact) model, which captures the software development process. Also, this paper proposes a software development process that is based on reusable ICs of patterns. The representation of a software project developed using ICs is also discussed.

A number of high-level parallel programming platforms for networks of workstations (NOWs) have been developed in recent times. Most of these platforms target the exploitation of data parallelism in applications. They do not allow expressibility of applications as a collection of tasks along with their precedence relationships. As a result, the control or task parallelism in an application cannot be expressed or exploited. The current work aims at integrating the notion of task parallelism and precedence relationships among constituting tasks to such high-level data parallel platforms for NOWs. Our model of integration provides for arbitrary nesting of data and task parallel modules. Also, the precedence relationships are clearly reflected from the program structure. The model relieves the programmer from the need to design applications for non-determinism in the order of completion of constituting tasks. The design of the runtime support as well as system-level book keeping is discussed. The model is general enough to be applied to a wide range of data parallel platforms. A specific case of integrating the model into anonymous remote computing (ARC), a data parallel programming platform, is presented. The performance related aspects are also discussed. Copyright © 2000 John Wiley & Sons, Ltd.

Large projects generally involve a number of phases and evolve over a period of time. Several revisions of the individual artifacts consisting of the project take place during the various phases. These revisions and refinements are normally captured as different versions using configuration/version management tools. But the semantics of these refinements with respect to the project are not captured by existing mechanisms. In addition to the above, a change in the semantics of a project artifact may require suitable changes in other related artifacts. Existing mechanisms for configuration management do not provide mechanisms for change propagation based on the change semantics. In this paper, we propose a generic model for semantics-based version management in projects, which can be built over existing tools. The model also provides support for capturing how changes propagate in a project. We then elucidate the generality of the model by applying it to a project involving a CAD framework and a software development project.

Parallel computing on interconnected workstations is becoming a viable and attractive proposition due to the rapid growth in speeds of interconnection networks and processors. In the case of workstation clusters, there is always a considerable amount of unused computing capacity available in the network. However, heterogeneity in architectures and operating systems, load variations on machines, variations in machine availability, and failure susceptibility of networks and workstations complicate the situation for the programmer. In this context, new programming paradigms that reduce the burden involved in programming for distribution, load adaptability, heterogeneity and fault tolerance gain importance. This paper identifies the issues involved in parallel computing on a network of workstations. The anonymous remote computing (ARC) paradigm is proposed to address the issues specific to parallel programming on workstation systems. ARC differs from the conventional communicating process model by treating a program as one single entity consisting of several loosely coupled remote instruction blocks instead of treating it as a collection of processes. The ARC approach results in distribution transparency and heterogeneity transparency. At the same time, it provides fault tolerance and load adaptability to parallel programs on workstations. ARC is developed in a two-tiered architecture consisting of high level language constructs and low level ARC primitives. The paper describes an implementation of the ARC kernel supporting ARC primitives.

In the conventional object model, encapsulated objects interact by messages that result in method invocations on the destination object. A message is delivered directly at the destination object. As a result of the direct deliveries, the message control code performing intermediate message manipulations cannot be abstracted out separately from the message processing code in the destination object without sacrificing the transparency of the intermediate message control. We propose the filtered delivery model of message passing for object-oriented languages to provide the separation of message control from message processing in a transparent manner. An interclass relationship, called a filter relationship, is introduced. As a consequence, a filter object can intercept and manipulate messages sent to another object called its client via filter member functions. A filter member function in a filter object can intercept a particular member function invocation on its client object. The filtered delivery model supports both upward and downward filtering mechanisms, facilitating interception of an upward message and its return message value. Filter objects can be plugged or unplugged at runtime. Binding of filter member functions to corresponding member functions in the client is selective and dynamic. The filtered delivery model is developed for the C++ object-oriented language; its applications are described and implementation is discussed. © 1997 John Wiley & Sons, Ltd.

Object databases have been recognized as providing rich data modeling capabilities for the next-generation applications, especially CAD/CAM, software engineering, and multimedia. The core object model consisting of objects, messages and inheritance, however, is not adequate to tackle all the requirements of these applications. Since collaborative activity is one of the key features of next-generation applications, it is essential that the basic object model be extended to support collaborative activity. We propose an object model for collaborative designing based on objects and constraint meta-objects. Each design object has an associated constraint space consisting of one or more constraint meta-objects. The object/constraint meta-object separation achieves a clear distinction between design object and its associated design environment and provides a framework for supporting collaboration among members of a design team. Collaboration is modeled as dependencies among multiple constraint spaces on different nodes, and collaborative activity as design transactions satisfying local constraints and propagating constraints among interrelated constraint spaces. We propose language extensions to C++ for capturing the object/constraint meta-object paradigm. The extensions are implemented using filters, a special mechanism for capturing messages sent to an object. Our model has been applied to the case of a mechanical CAD problem.

Job shop scheduling belongs to the class of NP-hard problems. There are a number of algorithms in literature for finding near optimal solution for the job shop scheduling problem. Many of these algorithms exploit the problem specific information and hence are less general. However, the simulated annealing algorithm for job shop scheduling is general and produces better results in comparison with other similar algorithms. But one of the major drawbacks of the algorithm is that the execution time is high. This makes the algorithm inapplicable to large scale problems. One possible approach to reduce the execution time of the algorithm is to develop distributed algorithms for simulated annealing. In the paper, the authors discuss approaches to developing distributed algorithms for simulated annealing for solving the job shop scheduling problem. Three different algorithms have been developed. These are the temperature modifier, the locking edges and the modified locking edges algorithms. These algorithms have been implemented on the distributed task sharing system (DTSS) running on a network of 18 Sun workstations. The observed performance showed that each of these algorithms performs well depending on the problem size.>