Transformer-based machine translation models currently dominate the field of model-based program translation. However, these models fail to provide interpretative support for the generated program translations. Moreover, researchers frequently invest substantial time and computational resources in retraining models, yet the improvement in translation accuracy is quite limited. To address these issues, we introduce a novel approach, $k\text{NN-ECD}$, which combines $k$-nearest-neighbor search with a key-value error correction datastore to overwrite the wrong translations of TransCoder-ST. This provides a decision-making basis for interpreting the corrected translations. Building upon this, we further propose $k\text{NN-ECS}_{m}$, a methodology that employs a distributed structure with $m$ sub-datastores connected in series, utilizing $m$ diverse experts for multi-round error correction. Additionally, we put forward a unified name rule, encouraging the datastore to focus more on code logic and structure rather than diverse rare identifiers. Our experimental results show that our approach improves the translation accuracy from 68.9\% to 89.9\% of TransCoder-ST (for translation from Java to Python). This error correction method augments program translation, overcoming the inherent limitations of Transformer-based code translation models, such as resource-intensive retraining requirements and uninterpretable outcomes.

Abstract Code generation has become an integral feature of modern IDEs, gathering significant attention. Notable approaches like GitHub Copilot and TabNine have been proposed to tackle this task. However, these tools may shift code writing tasks towards code reviewing, which involves modification from users. Despite the advantages of user feedback, their responses remain transient and lack persistence across interaction sessions. This is attributed to the inherent characteristics of generative AI models, which require explicit re-training for new data integration. Additionally, the non-deterministic and unpredictable nature of AI-powered models limits thorough examination of their unforeseen behaviors. We propose a methodology named One-shot Correction to mitigate these issues in natural language to code translation models with no additional re-training. We utilize decomposition techniques to break down code translation into sub-problems. The final code is constructed using code snippets of each query chunk, extracted from user feedback or selectively generated from a generative model. Our evaluation indicates comparable or improved performance compared to other models. Moreover, the methodology offers straightforward and interpretable approaches, which enable in-depth examination of unexpected results and facilitate insights for potential enhancements. We also illustrate that user feedback can substantially improve code translation models without re-training. Ultimately, we develop a preliminary GUI application to demonstrate the utility of our methodology in simplifying customization and assessment of suggested code for users.

Domain Specific Languages (DSLs) can be implemented as either internal DSL, i.e. essentially a library in a host general-purpose programming language (GPL), or as external DSL which is a stand-alone language unconstrained in its syntax. This choice implies an inherent trade-off between a limited syntactic and representational flexibility (internal DSLs), or an involved integration with GPLs and the need for a full stack of tools from a parser to a code generator (external DSLs).

Abstract Code completion has become an indispensable feature of modern Integrated Development Environments. In recent years, many approaches have been proposed to tackle this task. However, it is hard to compare between the models without explicitly re-evaluating them due to the differences of used benchmarks (e.g. datasets and evaluation metrics). Besides, almost all of these works report the accuracy of the code completion models as aggregated metrics averaged over all types of code tokens. Such evaluations make it difficult to assess the potential improvements for particularly relevant types of tokens (i.e. method or variable names), and blur the differences between the performance of the methods. In this paper, we propose a methodology called Code Token Type Taxonomy (CT3) to address the issue of using aggregated metrics. We identify multiple dimensions relevant for code prediction (e.g. syntax type, context, length), partition the tokens into meaningful types along each dimension, and compute individual accuracies by type. We illustrate the utility of this methodology by comparing the code completion accuracy of a Transformer-based model in two variants: with closed, and with open vocabulary. Our results show that the refined evaluation provides a more detailed view of the differences and indicates where further work is needed. We also survey the state-of-the-art of Machine Learning-based code completion models to illustrate that there is a demand for a set of standardized benchmarks for code completion approaches. Furthermore, we find that the open vocabulary model is significantly more accurate for relevant code token types such as usage of (defined) variables and literals.

Microbenchmarking frameworks, such as Java's Microbenchmark Harness (JMH), allow developers to write fine-grained performance test suites at the method or statement level. However, due to the complexities of the Java Virtual Machine, developers often struggle with writing expressive JMH benchmarks which accurately represent the performance of such methods or statements. In this paper, we empirically study bad practices of JMH benchmarks. We present a tool that leverages static analysis to identify 5 bad JMH practices. Our empirical study of 123 open source Java-based systems shows that each of these 5 bad practices are prevalent in open source software. Further, we conduct several experiments to quantify the impact of each bad practice in multiple case studies, and find that bad practices often significantly impact the benchmark results. To validate our experimental results, we constructed seven patches that fix the identified bad practices for six of the studied open source projects, of which six were merged into the main branch of the project. In this paper, we show that developers struggle with accurate Java microbenchmarking, and provide several recommendations to developers of microbenchmarking frameworks on how to improve future versions of their framework.

Unit tests in object-oriented programming languages must instantiate objects as an essential part of their set-up. Finding feasible method-call sequences for object creation and selecting a most desirable sequence can be a time-consuming challenge for developers in large C++ projects. This is caused by the intricacies of the C++ language, complexity of recursive object creation, and a large number of alternatives. We confirm the significance of the problem by analysis of 7 large C++ projects and a survey with 143 practitioners. We then design an approach for recommending method-call sequences for object creation that align with criteria gathered by the survey. Our approach exploits accurate and efficient compiler-based source code analysis to build an object dependency graph that is processed by a divide-and-conquer algorithm.An evaluation on a large industrial project shows that our tool finds solutions that require in 99% of 1104 cases identical or fewer objects compared to manually crafted solutions. Developer feedback and manual analysis confirm these results. Moreover, solutions found by our tool require up to 6 times fewer objects on average compared to approaches from prior work.

Merge conflicts can occur when multiple developers work concurrently on the same source code corpus. Diverging textual changes (in the same lines of code) are typically easy to resolve with help of common tools like Git. More challenging are higher-order merge conflicts. They arise as the result of unintended interactions between changes in different parts of the source code. Higher-order merge conflicts can be caused by a combination of changes, and so even thorough testing of the individual development branches might not be able to identify them. We suggest an approach based on static analysis and a prototypical tool to detect potential higher-order merge conflicts. Our method identifies potentially dangerous dependencies between changed code fragments in a call graph. An evaluation on SAP HANA, a very large industrial product in C++, shows that the approach is able to identify 62% of higher-order merge conflicts causing build failures over 22 months project development time. The same prototype finds no instance of higher-order merge conflicts causing test failures in SAP HANA during a two month development period. In summary, our method scales well and can identify higher-order merge conflicts which escape traditional testing.

Domain Specific Languages (DSLs) have proven useful in the domain of data science, as witnessed by the popularity of SQL. However, implementing and maintaining a DSL incurs a significant effort which limits their utility in context of fast-changing data science frameworks and libraries.

Code clone detection remains a crucial challenge in maintaining software projects. Many classic approaches rely on handcrafted aggregation schemes, while recent work uses supervised or unsupervised learning. In this work, we study several aspects of aggregation schemes for code clone detection based on supervised learning. To this aim, we implement an AST-based Recursive Neural Network. Firstly, our ablation study shows the influence of model choices and hyperparameters. We introduce error scaling as a way to effectively and efficiently address the class imbalance problem arising in code clone detection. Secondly, we study the influence of pretrained embeddings representing nodes in ASTs. We show that simply averaging all node vectors of a given AST yields strong baseline aggregation scheme. Further, learned AST aggregation schemes greatly benefit from pretrained node embeddings. Finally, we show the importance of carefully separating training and test data by clone clusters, to reliably measure generalization of models learned with supervision.

Selecting collection data structures for a given application is a crucial aspect of the software development. Inefficient usage of collections has been credited as a major cause of performance bloat in applications written in Java, C++ and C#. Furthermore, a single implementation might not be optimal throughout the entire program execution. This demands an adaptive solution that adjusts at runtime the collection implementations to varying workloads.

Measuring quality of test suites is one of the major challenges of software testing. Code coverage identifies tested and untested parts of code and is frequently used to approximate test suite quality. Multiple previous studies have investigated the relationship between coverage ratio and test suite quality, without a clear consent in the results. In this work we study whether covered code contains a smaller number of future bugs than uncovered code (assuming appropriate scaling). If this correlation holds and bug density is lower in covered code, coverage can be regarded as a meaningful metric to estimate the adequacy of testing. To this end we analyse 16000 internal bug reports and bug-fixes of SAP HANA, a large industrial software project. We found that the above-mentioned relationship indeed holds, and is statistically significant. Contrary to most previous works our study uses real bugs and real bug-fixes. Furthermore, our data is derived from a complex and large industrial project.

Configuration frameworks are routinely used in software systems to change application behavior without recompilation. Selecting a suitable configuration framework among the vast variety of existing choices is a crucial decision for developers, as it can impact project reliability and its maintenance profile. In this paper, we analyze almost 2,000 Java projects on GitHub to investigate the features and properties of 11 major Java configuration frameworks. We analyze the popularity of the frameworks and try to identify links between the maintenance effort involved with the usage of these frameworks and the frameworks' properties. More basic frameworks turn out to be the most popular, but in half of the cases are complemented by more complex frameworks. Furthermore, younger, more active frameworks with more detailed documentation, support for hierarchical configuration models and/or more data formats seem to require more maintenance by client developers.

Collection data structures have a major impact on the performance of applications, especially in languages such as Java, C#, or C++. This requires a developer to select an appropriate collection from a large set of possibilities, including different abstractions (e.g. list, map, set, queue), and multiple implementations. In Java, the default implementation of collections is provided by the standard Java Collection Framework (JCF). However, there exist a large variety of less known third-party collection libraries which can provide substantial performance benefits with minimal code changes.

Configuration options are widely used for customizing the behavior and initial settings of software applications, server processes, and operating systems. Their distinctive property is that each option is processed, defined, and described in different parts of a software project - namely in code, in configuration file, and in documentation. This creates a challenge for maintaining project consistency as it evolves. It also promotes inconsistencies leading to misconfiguration issues in production scenarios. We propose an approach for detection of inconsistencies between source code and documentation based on static analysis. Our approach automatically identifies source code locations where options are read, and for each such location retrieves the name of the option. Inconsistencies are then detected by comparing the results against the option names listed in documentation. We evaluated our approach on multiple components of Apache Hadoop, a complex framework with more than 800 options. Our tool ORPLocator was able to successfully locate at least one read point for 93% to 96% of documented options within four Hadoop components. A comparison with a previous state-of-the-art technique shows that our tool produces more accurate results. Moreover, our evaluation has uncovered 4 previously unknown, real-world inconsistencies between documented options and source code.

Identifying approximately identical strings is key for many data cleaning and data integration processes, including similarity join and record matching. The accuracy of such tasks crucially depends on appropriate choices of string similarity measures and thresholds for the particular dataset. Manual selection of similarity measures and thresholds is infeasible. Other approaches rely on the existence of adequate historic ground-truth or massive manual effort.

Software misconfigurations are responsible for a substantial part of today's system failures, causing about one-quarter of all customer-reported issues. Identifying their root causes can be costly in terms of time and human resources. We present an approach to automatically pinpoint such defects without error reproduction. It uses static analysis to infer the correlation degree between each configuration option and program sites affected by an exception. The only run-time information required by our approach is the stack trace of a failure. This is an essential advantage compared to existing approaches which require to reproduce errors or to provide testing oracles. We evaluate our approach on 29 errors from 4 configurable software programs, namely JChord, Randoop, Hadoop, and Hbase. Our approach can successfully diagnose 27 out of 29 errors. For 20 errors, the failure-inducing configuration option is ranked first.

Memory leaks are tedious to detect and require significant debugging effort to be reproduced and localized. In particular, many of such bugs escape classical testing processes used in software development. One of the reasons is that unit and integration tests run too short for leaks to manifest via memory bloat or degraded performance. Moreover, many of such defects are environment-sensitive and not triggered by a test suite. Consequently, leaks are frequently discovered in the production scenario, causing elevated costs. In this paper we propose an approach for automated diagnosis of memory leaks during the development phase. Our technique is based on regression testing and exploits existing test suites. The key idea is to compare object (de-)allocation statistics (collected during unit/integration test executions) between a previous and the current software version. By grouping these statistics according to object creation sites we can detect anomalies and pinpoint the potential root causes of memory leaks. Such diagnosis can be completed before a visible memory bloat occurs, and in time proportional to the execution of test suite. We evaluate our approach using real leaks found in 7 Java applications. Results show that our approach has sufficient detection accuracy and is effective in isolating the leaky allocation site: true defect locations rank relatively high in the lists of suspicious code locations if the tests trigger the leak pattern. Our prototypical system imposes an acceptable instrumentation and execution overhead for practical memory leak detection even in large software projects.

Software systems running continuously for a long time often confront software aging, which is the phenomenon of progressive degradation of execution environment caused by latent software faults. Removal of such faults in software development process is a crucial issue for system reliability. A known major obstacle is typically the large latency to discover the existence of software aging. We propose a systematic approach to detect software aging which has in a shorter test time and higher accuracy compared to traditional aging detection via stress testing and trend detection with high confidence. The approach is based on a comparative differential analysis where a software version under test is compared with against a previous robust version by observing in terms of behavioral (signal) changes during system tests of resource metrics. A key instrument adopted is a divergence chart, which expresses time-dependent differences between two signals, allowing us to detect changes in the system metrics' values which indicate the existence of software aging. In our experimental study, we focuses on memory-leak detection and the and evaluates divergence charts are computed using various multiple statistical techniques combined paired with different application-level memory related metrics (RSS and Heap Usage). The experimental results show that the statistical process control techniques used in our approach proposed method achieves good performance for memory-leak detection, when compared with other in comparison to techniques widely adopted in previous works (e.g., linear regression, moving average and median).

Learning from distributed data becomes increasingly important. Factors contributing to this trend include emergence of data sets exceeding RAM sizes and inherently distributed scenarios such as mobile environments. Also in these cases interpretable models are favored: they facilitate identifying artifacts and understanding the impact of individual variables. Given the distributed environment, even if the individual learner on each site is interpretable, the overall model usually is not (as e.g. in case of voting schemes). To overcome this problem we propose an approach for efficient merging of decision trees (each learned independently) into a single decision tree. The method complements the existing distributed decision trees algorithms by providing interpretable intermediate models and tolerating constraints on bandwidth and RAM size. The latter properties are achieved by trading RAM and communication constraints for accuracy. Our method and the mentioned trade-offs are validated in experiments on real-world data sets.

Memory-related software defects manifest after a long incubation time and are usually discovered in a production scenario. As a consequence, this frequently encountered class of so-called software aging problems incur severe follow-up costs, including performance and reliability degradation, need for workarounds (usually controlled restarts) and effort for localizing the causes. While many excellent tools for identifying memory leaks exist, they are inappropriate for automated leak detection or isolation as they require developer involvement or slow down execution considerably. In this work we propose a lightweight approach which allows for automated leak detection during the standardized unit or integration tests. The core idea is to compare at the byte-code level the memory allocation behavior of related development versions of the same software. We evaluate our approach by injecting memory leaks into the YARN component of the popular Hadoop framework and comparing the accuracy of detection and isolation in various scenarios. The results show that the approach can detect and isolate such defects with high precision, even if multiple leaks are injected at once.

Return on investment is a critical decision factor for end-users going for cloud deployments. However, major cloud vendors typically provide a myriad of interdependent cloud service options in a variety of purchasing models, that severely complicates cost estimation and optimization. In this paper, we propose a novel Amazon EC2 cost optimization system, called EC2 Bargain Hunter, that innovatively combines services and cloud computing principles with ideas from semantic technologies. The system supports the entire-range of EC2 instance types, and can be used in real-time to perform live cost optimization. We demonstrate that unprecedented cost savings, by a factor of 30, on Amazon EC2 offerings can be found with this system in a few clicks. Furthermore, our approach can be adapted to other IaaS providers, which enables truly real-life cloud cost optimization and thus is a significant step towards making the cloud really cost-effective for the end-users.

Recently introduced spot instances in the Amazon Elastic Compute Cloud (EC2) offer low resource costs in exchange for reduced reliability; these instances can be revoked abruptly due to price and demand fluctuations. Mechanisms and tools that deal with the cost-reliability tradeoffs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. We study how mechanisms, namely, checkpointing and migration, can be used to minimize the cost and volatility of resource provisioning. Based on the real price history of EC2 spot instances, we compare several adaptive checkpointing schemes in terms of monetary costs and improvement of job completion times. We evaluate schemes that apply predictive methods for spot prices. Furthermore, we also study how work migration can improve task completion in the midst of failures while maintaining low monetary costs. Trace-based simulations show that our schemes can reduce significantly both monetary costs and task completion times of computation on spot instance.

Recently introduced spot instances in the Amazon Elastic Compute Cloud (EC2) offer lower resource costs in exchange for reduced reliability; these instances can be revoked abruptly due to price and demand fluctuations. Mechanisms and tools that deal with the cost-reliability trade-offs under this schema are of great value for users seeking to lessen their costs while maintaining high reliability. We study how one such a mechanism, namely check pointing, can be used to minimize the cost and volatility of resource provisioning. Based on the real price history of EC2 spot instances, we compare several adaptive check pointing schemes in terms of monetary costs and improvement of job completion times. Trace-based simulations show that our approach can reduce significantly both price and the task completion times.

With the recent introduction of Spot Instances in the Amazon Elastic Compute Cloud (EC2), users can bid for resources and thus control the balance of reliability versus monetary costs. A critical challenge is to determine bid prices that minimize monetary costs for a user while meeting Service Level Agreement (SLA) constraints (for example, sufficient resource availability to complete a computation within a desired deadline). We propose a probabilistic model for the optimization of monetary costs, performance, and reliability, given user and application requirements and dynamic conditions. Using real instance price traces and workload models, we evaluate our model and demonstrate how users should bid optimally on Spot Instances to reach different objectives with desired levels of confidence.

Popular web services and applications such as Google Apps, DropBox, and Go.Pc introduce a wasteful imbalance of processing resources. Each host operated by a provider serves hundreds to thousands of users, treating their PCs as thin clients. Tapping the processing, storage and networking capacities of these non-dedicated resources promises to reduce the size of required hardware basis significantly. Consequently, it presents a noteworthy opportunity for service providers and operators of cloud computing infrastructures. We investigate how a mixture of dedicated (and so highly available) hosts and non-dedicated (and so highly volatile) hosts can be used to provision a processing tier of a large-scale web service. We discuss an operational model which guarantees long-term availability despite of host churn, and study multiple aspects necessary to implement it. These include: ranking of non-dedicated hosts according to their long-term availability behavior, short-term availability modeling of these hosts, and simulation of migration and group availability levels using real-world availability data from 10,000 non-dedicated hosts. We also study the tradeoff between a larger share of dedicated hosts vs. higher migration rate in terms of costs and SLA objectives. This yields an optimization approach where a service provider can find a suitable balance between costs and service quality. The experimental results show that it is possible to achieve a wide spectrum of such modes, ranging from 3.6 USD/hour to 5 USD/hour for a group of at least 50 hosts available with probability greater than 0.90.

The wide-spread phenomenon of software (running image) aging is known to cause performance degradation, transient failures or even crashes of applications. In this work we describe first a method for monitoring and modeling of performance degradation in SOA applications, particularly application servers. This method works for a large class of the aging processes caused by resource depletion (e.g. memory leaks). It can be deployed non-intrusively in a production environment, under arbitrary service request distributions. Based on this schema we investigate in the second part of the paper how machine learning (classification) algorithms can be used for proactive detection of performance degradation or sudden drops caused by aging. We leverage the predictive power of these algorithms with several techniques to make the measurement-based aging models more adaptive and more robust against transient failures. We evaluate several state-of-the-art classification methods for their accuracy and computational efficiency in this scenario. The studies are performed on a data set generated by a TPC-W benchmark instrumented with a memory leak injector. The results show that the probing method yields accurate aging models with low overhead and the machine learning approach gives statistically significant short-term predictions of degrading application performance. Both approaches can be used directly to fight aging via adaptive software rejuvenation (restart of the application), for operator alerting, or for short-term capacity planning.

Automated modeling of software aging processes is a prerequisite for cost-effective usage of adaptive software rejuvenation as a self-healing technique. We consider the problem of such automated modeling in server-type applications whose performance degrades depending on the "work" done since last rejuvenation, for example the number of served requests. This type of performance degradation - caused mostly by resource depletion - is common, as we illustrate in a study of the popular Axis Soap server 1.3. In particular, we propose deterministic models for approximating the leading indicators of aging and an automated procedure for statistical testing of their correctness. We further demonstrate how to use these models for finding optimal rejuvenation schedules under utility functions. Our focus is on the important case that the utility function is the average of a performance metric (such as maximum service rate). We also consider optional SLA constraints under which the performance should never drop below a specified level. Our approach is verified by a study of the aging processes in the Axis Soap 1.3 server. The experiments show that the deterministic modeling technique is appropriate in this case, and that the optimization of rejuvenation schedules can greatly improve the average maximum service rate of an aging application.

In this paper, we present an approach for software rejuvenation based on automated self-healing techniques that can be easily applied to off-the-shelf Application Servers and Internet sites. Software aging and transient failures are detected through continuous monitoring of system data and performability metrics of the application server. If some anomalous behavior is identified the system triggers an automatic rejuvenation action. This self-healing scheme is meant to be the less disruptive as possible for the running service and to get a zero downtime for most of the cases. In our scheme, we exploit the usage of virtualization to optimize the self-recovery actions. The techniques described in this paper have been tested with a set of open-source Linux tools and the XEN virtualization middleware. We conducted an experimental study with two applications benchmarks (Tomcat/Axis and TPC-W). Our results demonstrate that virtualization can be extremely helpful for software rejuvenation and fail-over in the occurrence of transient application failures and software aging.

In this paper, we present a checkpoint-based scheme to improve the turnaround time of bag-of-tasks applications executed on institutional desktop grids. We propose to share checkpoints among desktop machines in order to reduce the negative impact of resource volatility. Several scheduling policies are evaluated in our study: FCFS, adaptive timeouts, simple replication, replication with checkpoint on demand, and prediction-based checkpointing combined with replication. We used a set of real traces collected from an academic desktop grid environment to perform trace-driven simulations of the proposed scheduling algorithms. The results show that using a shared checkpoint approach may considerably reduce the turnaround time of the applications when compared to the private checkpoints methodology.

This paper describes a study of predicting machine availabilities and user presence in a pool of desktop computers. The study is based on historical traces collected from 32 machines, and shows that robust prediction accuracy can be achieved even in this highly volatile environment. The employed methods include a multitude of classification methods known from data mining, such as Bayesian methods and support vector machines. Further contribution is a time series framework used in the study which automates correlations search and attribute selection, and allows for easy reconfiguration and efficient prediction. The results illustrate the utility of prediction techniques in highly dynamic computing environments. Potential applications for proactive management of desktop pools are discussed

Summary form only given. Scientific computing clusters, enterprise data centers and grid and utility environments utilize the majority of the world's computing resources. Most of these resources are lightly utilized and offer a vast potential for resource sharing, an economically attractive and increasingly indispensable management option. A prerequisite for automating resource consolidation is modeling and prediction of demand characteristics. We present an approach for long-term demand characteristics prediction based on mining periodicities in historical demand data. In addition to characterizing the regularity of the past demand behavior (and so providing a measure of predictability) we propose a method for predicting probabilistic profiles which describe likely future behavior. The presented algorithms are change-adaptive in the sense that they automatically adjust to new regularities in demand patterns. A case study using data from an enterprise data center evaluates the effectiveness of the technique.

Proxy hit ratios tend to decrease as the demand and supply of Web contents are becoming more diverse. By case studies, we quantitatively confirm this trend and observe significant document duplications among a proxy and its client browsers' caches. One reason behind this trend is that the client/server Web caching model does not support direct resource sharing among clients, causing the Web contents and the network bandwidths among clients to be relatively underutilized. To address these limits and improve Web caching performance, we have extensively enhanced and deployed our browsers-aware framework, a peer-to-peer Web caching management scheme. We make the browsers and their proxy share the contents to exploit the neglected but rich data locality in browsers and reduce document duplications among the proxy and browsers' caches to effectively utilize the Web contents and network bandwidth among clients. The objective of our scheme is to improve the scalability of proxy-based caching both in the number of connected clients and in the diversity of Web documents. We show that building such a caching system with considerations of sharing contents among clients, minimizing document duplications, and achieving data integrity and communication anonymity is not only feasible but also highly effective.

We describe a simple algorithm for level-wise enumeration of the global states of a distributed computation. In addition to fast execution, it requires working memory for only two global states plus a variable amount of memory which permits the trading of higher speed for storage. Furthermore, we present a new caching strategy that speeds up the state enumeration algorithm described in [A. Andrzejak et al., (2003)].

With the desire towards ad-hoc collaboration across organizations, specifically fostered by grids, static, well-known and preconfigured management topologies are becoming hard to maintain. Dynamic topology creation and exploration is needed when new collaborations are established. Topology across organizational domain is also called management overlay. Algorithms are needed that can self-organize topology, as well as algorithms that can render and update the layout for visualizing topology information presenting management information on operator consoles. Changes constantly occurring in an ad-hoc topology need to be updated and presented accordingly. We discuss ad-hoc topologies and impact on management systems. Our work is based on experiments with various algorithms with self-organizing capabilities and hyperbolic visualization techniques for visualizing ad-hoc topologies for management overlays.

The explosion in globally connected devices, computers, and services ultimately evolves into very large-scale, inter-connected systems approaching a new era of planetary-scale computing. The backbone of planetary-scale computing is a global network of data centers. The paper provides an overview of research at HP Laboratories exploring new approaches under such a scenario based on HP's virtual data center platform enabling large-scale distributed virtual data center environments. Our approach is founded in a service-centric system view, and we explore agent technology for resource control, system organization, and balancing resource demand and supply.

Recent peer-to-peer (P2P) systems such as Tapestry, Chord or CAN act primarily as a distributed hash table (DHT). A DHT is a data structure for distributed storing of pairs (key, data) which allows fast locating of data when a key is given. To facilitate efficient queries on a range of keys, we propose a CAN-based extension of this DHT-functionality. The design of our extension suggests several range query strategies; their efficiency is investigated in the paper. A further goal is to enhance the routing aspects of current DHT-systems so that frequently changing data can also be handled efficiently. We show that relatively simple approaches are able to reduce the communication overhead in this case. The design of the system is driven by its application as a part of the information infrastructure for computational grids. Such grids provide an infrastructure for sharing computing resources; an information infrastructure is their inherent part which collects resource data and provides search functionality. Our approach complements current solutions such as MDS-2 by adding self-organization, fault-tolerance and an ability to efficiently handle dynamic attributes, such as server processing capacity. We evaluate our system in this context via a simulation and show that its design along with particular query and update strategies meet the goals of scalability, communication-efficiency and availability.

Let P be a set of n. points in IRd in general position, i.e., no i + 1 points on a common (i -1)-flat, 1 < i 5 d.A k-set @'P is a set S of E points in P that can be separated from P \ S by a hyperplane.A j-facet of P is an oriented (d -l)simplex spanned by d points in P which has exactly j points from P on the positive side of its affine hull.If P is a planar point set and n is even, a halving edge is an undirected edge between two points, such that the connecting line has the same number of points on either side.The number of (n/2)-sets is twice the number of halving edges.Inspired by Dey's recent proof of a new bound on the number of k-sets we show that where degp is the number of halving edges incident to point p and C is the number of crossing pairs of halving edges.The identity allows us, among other things, to determine the masimum number of halving edges in a set of 12 points.An anaIogous identity holds for j-facets.For P in IR3 we show that for j 5 n/4 -2 the number of cs j)-facets (i.e., i-facets with 0 5 i 5 j) is maximized for sets in convex position, where this number is known to be (j + l)(j + 2)n -2(j + l)(j + 2)(j + 3)/3.For 1; 5 n/4 -1, k2n -k(k -1)(2A + 5)/3 is the tight upper bound for the number of (5 A)-sets (i.e., i-sets with 1 ': i 5 k).'h't of this work %S Performed while R.S. and E.W. were visiting the DlhfAa center in November 1989.while R.S. visited FU Berlin in 1992, while E.W. visited