Modern High-Performance Computing (HPC) systems play a fundamental role in driving scientific research, as they execute computationally intensive jobs originating from diverse domains. However, HPC jobs are characterized by conflicting computational requirements, which may cause inefficiencies in resource usage, system throughput and energy consumption. One approach to tackling this problem is to distinguish between memory-bound and compute-bound jobs at their submission time, with the goal of making informed decisions about their execution. In this paper, we present MCBound, the first online data-driven framework to classify HPC jobs as memory/compute-bound before job execution, without user intervention. We propose a systematic characterization technique to generate a reference dataset from historical data for initial classification model training. Using the proposed characterization technique, we analyze the data of 2.2 million job runs on the Supercomputer Fugaku1, a production HPC system installed at the RIKEN Center for Computational Science, in Japan. We implement MCBound for Fugaku and classify the jobs executed during February 2024. Our approach is proven effective, as it obtains an F1-macro average score of at least 0.89 as prediction quality, while incurring a negligible overhead on the system’s operations. Our Python-based implementation of MCBound can be seamlessly configured and deployed in other HPC systems.1https://www.fujitsu.com/global/about/innovation/fugaku/

Cognification - the act of transforming ordinary objects or processes into their intelligent counterparts through Data Science and Artificial Intelligence - is a disruptive technology that has been revolutionizing disparate fields ranging from corporate law to medical diagnosis. Easy access to massive data sets, data analytics tools and High-Performance Computing (HPC) have been fueling this revolution. In many ways, cognification is similar to the electrification revolution that took place more than a century ago when electricity became a ubiquitous commodity that could be accessed with ease from anywhere in order to transform mechanical processes into their electrical counterparts. In this paper, we consider two particular forms of distributed computing - Data Centers and HPC systems - and argue that they are ripe for cognification of their entire ecosystem, ranging from top-level applications down to low-level resource and power management services. We present our vision for what "Cognified Distributed Computing" might look like and outline some of the challenges that need to be addressed and new technologies that need to be developed in order to make it a reality. In particular, we examine the role cognification can play in tackling power consumption, resiliency and management problems in these systems. We describe intelligent software-based solutions to these problems powered by on-line predictive models built from streamed real-time data. While we cast the problem and our solutions in the context of large Data Centers and HPC systems, we believe our approach to be applicable to distributed computing in general. We believe that the traditional systems research agenda has much to gain by crossing discipline boundaries to include ideas and techniques from Data Science, Machine Learning and Artificial Intelligence.

Summary Power consumption of current High Performance Computing systems has to be reduced by at least one order of magnitude before they can be scaled up towards ExaFLOP performance. While we can expect novel hardware technologies and architectures to contribute towards this goal, significant advances have to come also from software technologies such as proactive and power‐aware scheduling, resource allocation, and fault‐tolerant computing. Development of these software technologies in turn relies heavily on our ability to model and accurately predict power consumption in large computing systems. In this paper, we present a data‐driven model of power consumption for a hybrid supercomputer (which held the top spot in the Green500 ranking in June 2013) that combines CPU, GPU, and MIC technologies to achieve high levels of energy efficiency. Our model takes as input workload characteristics—the number and location of resources that are used by each job at a certain time—and calculates a predicted power consumption at the system level. The model is application‐code‐agnostic and is based solely on a data‐driven predictive approach, where log data describing the past jobs in the system are employed to estimate future power consumption. For this, three different model components are developed and integrated. The first employs support vector regression to predict power usage for jobs before these are started. The second uses a simple heuristic to predict the length of jobs, again before they start. The two predictions are then combined to estimate power consumption due to the job at all computational elements in the system. The third component is a linear model that takes as input the power consumption at the computing units and predicts system‐wide power consumption. Our method achieves highly‐accurate predictions starting solely from workload information and user histories. The model can be applied to power‐aware scheduling and power capping: alternative workload dispatching configurations can be evaluated from a power perspective and more efficient ones can be selected. The methodology outlined here can be easily adapted to other HPC systems where the same types of log data are available.

The success of Cloud computing, where computing power is treated as a utility, has resulted in the creation of many large data centers that are very expensive to build and operate. In particular, the energy bill accounts for a significant fraction of the total operation costs. For this reason a significant attention is being devoted to energy conservation techniques, for example by taking advantage of the built-in power saving features of modern hardware. Cloud computing offers novel opportunities for achieving energy savings: Cloud systems rely on virtualization techniques to allocate computing resources on demand, and modern Virtual Machine (VM) monitors allow live migration of running VMs. Thus, energy conservation can be achieved through server consolidation, moving VM instances away from lightly loaded computing nodes so that they become empty and can be switched to low-power mode. In this paper we present V-MAN, a fully decentralized algorithm for consolidating VMs in large Cloud datacenters. V-MAN can operate on any arbitrary initial allocation of VMs on the Cloud, iteratively producing new allocations that quickly converge towards the one maximizing the number of idle hosts. V-MAN uses a simple gossip protocol to achieve efficiency, scalability and robustness to failures. Simulation experiments indicate that, starting from a random allocation, V-MAN produces an almost-optimal VM placement in just a few rounds; the protocol is intrinsically robust and can cope with computing nodes being added to or removed from the Cloud.

Abstract This paper presents the design and implementation of Jgroup/ARM, a distributed object group platform with autonomous replication management along with a novel measurement‐based assessment technique that is used to validate the fault‐handling capability of Jgroup/ARM. Jgroup extends Java RMI through the group communication paradigm and has been designed specifically for application support in partitionable systems. ARM aims at improving the dependability characteristics of systems through a fault‐treatment mechanism. Hence, ARM focuses on deployment and operational aspects, where the gain in terms of improved dependability is likely to be the greatest. The main objective of ARM is to localize failures and to reconfigure the system according to application‐specific dependability requirements. Combining Jgroup and ARM can significantly reduce the effort necessary for developing, deploying and managing dependable, partition‐aware applications. Jgroup/ARM is evaluated experimentally to validate its fault‐handling capability; the recovery performance of a system deployed in a wide area network is evaluated. In this experiment multiple nearly coincident reachability changes are injected to emulate network partitions separating the service replicas. The results show that Jgroup/ARM is able to recover applications to their initial state in several realistic failure scenarios, including multiple, concurrent network partitionings. Copyright © 2007 John Wiley & Sons, Ltd.

The concept of superpeer has been introduced to improve the performance of popular P2P applications. A superpeer is a "powerful" node that acts as a server for a set of clients, and as an equal with respect to other superpeers. By exploiting heterogeneity, the superpeer paradigm can lead to improved efficiency, without compromising the decentralized nature of P2P networks. The main issues in constructing superpeer-based overlays are the selection of superpeers and the association between superpeers and clients. Generally, superpeers are either run voluntarily (without an explicit selection process), or chosen among the "best" nodes in the network, for example those with the most abundant resources, such as bandwidth or storage. In several contexts, however, shared resources are not the only factor; latency between clients and superpeers may play an important role, for example in online games and IP-Telephony applications. This paper presents SG-2, a novel protocol for building and maintaining proximity-aware superpeer topologies. SG-2 uses a gossip-based protocol to spread messages to nearby nodes and a biology-inspired task allocation mechanism to promote the "best" nodes to superpeer status. The paper includes extensive simulation experiments to prove the efficiency, scalability and robustness of SG-2.

Recent developments in information technology have brought about important changes in distributed computing. New environments such as massively large-scale, wide-area computer networks and mobile ad hoc networks have emerged. Common characteristics of these environments include extreme dynamicity, unreliability, and large scale. Traditional approaches to designing distributed applications in these environments based on central control, small scale, or strong reliability assumptions are not suitable for exploiting their enormous potential. Based on the observation that living organisms can effectively organize large numbers of unreliable and dynamically-changing components (cells, molecules, individuals, etc.) into robust and adaptive structures, it has long been a research challenge to characterize the key ideas and mechanisms that make biological systems work and to apply them to distributed systems engineering. In this article we propose a conceptual framework that captures several basic biological processes in the form of a family of design patterns. Examples include plain diffusion, replication, chemotaxis, and stigmergy. We show through examples how to implement important functions for distributed computing based on these patterns. Using a common evaluation methodology, we show that our bio-inspired solutions have performance comparable to traditional, state-of-the-art solutions while they inherit desirable properties of biological systems including adaptivity and robustness.

Peer-to-peer applications can benefit from human friendship networks (e.g., e-mail contacts or instant message buddy lists). However these are not always available. We propose an algorithm, called SLACER that allows peer nodes to create their own friendship networks, through randomized interactions, producing an artificial social network (ASN) where nodes share high trust with their neighbors

Structured peer-to-peer overlay networks are now an established paradigm for implementing a wide range of distributed services. While the problem of maintaining these networks in the presence of churn and other failures is the subject of intensive research, the problem of building them from scratch has not been addressed (apart from individual nodes joining an already functioning overlay). In this paper we address the problem of jump-starting a popular structured overlay, Chord, from scratch. This problem is of crucial importance in scenarios where one is assigned a limited time interval in a distributed environment such as Planet-Lab, or a grid, and the overlay infrastructure needs to be set up from the ground up as quickly and efficiently as possible, or when a temporary overlay has to be generated to solve a specific task on demand. We introduce T-Chord, that can build a Chord network efficiently starting from a random unstructured overlay. After jump-starting, the structured overlay can be handed over to the Chord protocol for further maintenance. We demonstrate through extensive simulation experiments that the proposed protocol can create a perfect Chord topology in a logarithmic number of steps. Furthermore, using a simple extension of the protocol, we can optimize the network from the point of view of message latency.

As computer networks increase in size, become more heterogeneous and span greater geographic distances, applications must be designed to cope with the very large scale, poor reliability, and often, with the extreme dynamism of the underlying network. Aggregation is a key functional building block for such applications: it refers to a set of functions that provide components of a distributed system access to global information including network size, average load, average uptime, location and description of hotspots, and so on. Local access to global information is often very useful, if not indispensable for building applications that are robust and adaptive. For example, in an industrial control application, some aggregate value reaching a threshold may trigger the execution of certain actions; a distributed storage system will want to know the total available free space; load-balancing protocols may benefit from knowing the target average load so as to minimize the load they transfer. We propose a gossip-based protocol for computing aggregate values over network components in a fully decentralized fashion. The class of aggregate functions we can compute is very broad and includes many useful special cases such as counting, averages, sums, products, and extremal values. The protocol is suitable for extremely large and highly dynamic systems due to its proactive structure---all nodes receive the aggregate value continuously, thus being able to track any changes in the system. The protocol is also extremely lightweight, making it suitable for many distributed applications including peer-to-peer and grid computing systems. We demonstrate the efficiency and robustness of our gossip-based protocol both theoretically and experimentally under a variety of scenarios including node and communication failures.

Aggregation refers to a set of functions that provide global information about a distributed system. These junctions operate on numeric values distributed over the system and can be used to count network size, determine extremal values and compute averages, products or sums. Aggregation allows important basic functionality to be achieved in fully distributed and peer-to-peer networks. For example, in a monitoring application, some aggregate reaching a specific value may trigger the execution of certain operations; distributed storage systems may need to know the total free space available; load-balancing protocols may benefit from knowing the target average load so as to minimize the transfered load. Building on the simple but efficient idea of antientropy aggregation (a scheme based on the antientropy epidemic communication model), in this paper we introduce practically applicable robust and adaptive protocols for proactive aggregation, including the calculation of average, product and extremal values. We show how the averaging protocol can be applied to compute further aggregates like sum, variance and the network size. We present theoretical and empirical evidence supporting the robustness of the averaging protocol under different scenarios.

Recent peer-to-peer (P2P) systems are characterized by decentralized control, large scale and extreme dynamism of their operating environment. As such, they can be seen as instances of complex adaptive systems (CAS) typically found in biological and social sciences. We describe Anthill, a framework to support the design, implementation and evaluation of P2P applications based on ideas such as multi-agent and evolutionary programming borrowed from CAS. An Anthill system consists of a dynamic network of peer nodes; societies of adaptive agents travel through this network, interacting with nodes and cooperating with other agents in order to solve complex problems. Anthill can be used to construct different classes of P2P services that exhibit resilience, adaptation and self-organization properties. We also describe preliminary experiences with Anthill in implementing a file sharing application.

Over the last years, many replica control protocols have been developed that take advantage of the ordering and reliability semantics of group communication primitives to simplify database system design and to improve performance. Although current solutions are able to mask site failures effectively, many of them are unable to cope with recovery of failed sites, merging of partitions, or joining of new sites. This paper addresses this important issue. It proposes efficient solutions for online system reconfiguration providing new sites with a current state of the database without interrupting transaction processing in the rest of the system. Furthermore, the paper analyzes the impact of cascading reconfigurations, and argues that they call be handled in an elegant way by extended forms of group communication.

Gives a formal specification and an implementation for a partitionable group communication service in asynchronous distributed systems. Our specification is motivated by the requirements for building "partition-aware" applications that can continue operating without blocking in multiple concurrent partitions and can reconfigure themselves dynamically when partitions merge. The specified service guarantees liveness and excludes trivial solutions, it constitutes a useful basis for building realistic partition-aware applications, and it is implementable in practical asynchronous distributed systems where certain stability conditions hold.

Network applications and services need to be environment-aware in order to meet non-functional requirements in increasingly dynamic contexts. We consider partition awareness as an instance of environment awareness in network applications that need to be reliable and self-managing. Partition-aware applications dynamically reconfigure themselves and adjust the quality of their services in response to partitioning and merging of networks. As such, they can automatically adapt to changes in the environment so as to remain available in multiple partitions without blocking, albeit with reduced or degraded functionality. We propose a system layer consisting of group membership and reliable multicast services that provides systematic support for partition-aware application development. We illustrate the effectiveness of the proposed interface by solving several problems that represent different classes of realistic network applications.

We consider network applications that are based on the process group paradigm. When such applications are deployed over networks that are subject to failures, they may partition across several disconnected clusters resulting in multiple views of the group's current composition to exist concurrently. Application semantics determine which operations, if any, can be performed in different partitions without compromising consistency. For certain application classes, most (possibly all) operations need to be confined to a single primary partition while other partitions are allowed to service only a (possibly empty) subset of the operations. We propose a mechanism for deciding when a view constitutes the primary partition for the group. Our solution is highly flexible and has the following novel features: each group member can establish if it belongs to the primary partition or not, based solely on local information; the group can be dynamic as processes voluntarily join and leave it; the selection rule for establishing the primary partition need not be universal but can be decided on a per-application basis and can be modified at run time; the primary partition can be re-established even after total failures. Layering our solution on top of a partitionable group membership service allows a wide range of applications with different and possibly conflicting notions of "primary partition" to be supported on a common computing base.

Distributed systems constructed using off-the-shelf communication infrastructures are becoming common vehicles for doing business in many important application domains. Large geographic extent due to increased globalization, increased probability of failures, and highly dynamic loads all contribute toward a partitionable and asynchronous characterization for these systems. In this paper, we consider the problem of developing reliable applications to be deployed in partitionable asynchronous distributed systems. What makes this task difficult is guaranteeing the consistency of shared state despite asynchrony, failures, and recoveries, including the formation and merging of partitions. While view synchrony within process groups is a powerful paradigm that can significantly simplify reasoning about asynchrony and failures, it is insufficient for coping with recoveries and merging of partitions after repairs. We first give an abstract characterization for shared state management in partitionable asynchronous distributed systems and then show how views can be enriched to convey structural and historical information relevant to the group's activity. The resulting, paradigm, called enriched view synchrony, can be implemented efficiently and leads to a simple programming methodology for solving shared state management in the presence of partitions.

View synchrony has been proposed as a programming paradigm for developing reliable distributed applications. The paradigm is particularly attractive when the underlying computing system is asynchronous and prone to complex failure scenarios including partitions. View synchrony encourages a programming style where groups of processes cooperate closely in order to maintain some form of shared state among them. In this paper we examine the technical problems that arise in shared state management when programming applications using view synchrony. We identify three classes of problems corresponding to state transfer upon group joins, state recreation after total failures and state merging after partition unions. We argue that shared state problems are inherent to any implementation, and without explicit support, attempts to solve them may easily obscure much of the simplicity and elegance of view synchrony. Finally, we propose an extension to the traditional view synchrony model based on the notion of subviews that addresses the problems raised by shared state management.

Modern distributed systems consisting of powerful workstations and high-speed interconnection networks are an economical alternative to special-purpose supercomputers. The technical issues that need to be addressed in exploiting the parallelism inherent in a distributed system include heterogeneity, high-latency communication, fault tolerance and dynamic load balancing. Current software systems for parallel programming provide little or no automatic support towards these issues and require users to be experts in fault-tolerant distributed computing. The Paralex system is aimed at exploring the extent to which the parallel application programmer can be liberated from the complexities of distributed systems. Paralex is a complete programming environment and makes extensive use of graphics to define, edit, execute, and debug parallel scientific applications. All of the necessary code for distributing the computation across a network and replicating it to achieve fault tolerance and dynamic load balancing is automatically generated by the system. In this paper we give an overview of Paralex and present our experiences with a prototype implementation.

Modern distributed systems consisting of powerful workstations and high-speed interconnection networks are an economical alternative to special-purpose super computers. The technical issues that need to be addressed in exploiting the parallelism inherent in a distributed system include heterogeneity, high-latency communication, fault tolerance and dynamic load balancing. Current software systems for parallel programming provide little or no automatic support towards these issues and require users to be experts in fault-tolerant distributed computing. The Paralex system is aimed at exploring the extent to which the parallel application programmer can be liberated from the complexities of distributed systems. Paralex is a complete programming environment and makes extensive use of graphics to define, edit, execute and debug parallel scientific applications. All of the necessary code for distributing the computation across a network and replicating it to achieve fault tolerance and dynamic load balancing is automatically generated by the system. In this paper we give an overview of Paralex and present our experiences with a prototype implementation.

The designer of a fault-tolerant distributed system faces numerous alternatives. Using a stochastic model of processor failure times, we investigate design choices such as replication level, protocol running time, randomized versus deterministic protocols, fault detection, and authentication. We use the probability with which a system produces the correct output as our evaluation criterion. This contrasts with previous fault-tolerance results that guarantee correctness only if the percentage of faulty processors in the system can be bounded. Our results reveal some subtle and counterintuitive interactions between the design parameters and system reliability.

A site broadcasting its local value to all other sites ina fault-prone environment is a fundamental paradigm in constructing reliable distributed systems. Time complexity lower bounds and network connectivity requirements for reliable broadcast protocols in point-to-point communication networks are well known. In this paper, we consider the reliable broadcast problem in distributed systems with broadcast networks (for example, Ethernets) as the basic communication architecture. We show how properties of such network architectures can be used to effectively restrict the externally visible behavior of faulty processors. We use these techniques to derive simple protocols that implement reliable broadcast in only two rounds, independent of the failure upper bounds.

We consider a model of computation consisting of a sequence of n tasks. In the absence of failures, each task i has a known completion time $t_i $ . Checkpoints can be placed between any two consecutive tasks. At a checkpoint, the state of the computation is saved on a reliable storage medium. Establishing a checkpoint immediately before task i is known to cost $s_i $. This is the time spent in saving the state of the computation. When a failure is detected, the computation is restarted at the most recent checkpoint. Restarting the computation at checkpoint i requires restoring the state to the previously saved value. The time necessary for this action is given by $r_i $. We derive an $O(n^3 )$ algorithm to select out of the $n - 1$ potential checkpoint locations those that result in the smallest expected time to complete all the tasks. An $O(n^2 )$ algorithm is described for the reasonable case where $s_i > s_j $ implies $r_i \geqslant r_j $. These algorithms are applied to two models of failure. In the first one, each task i has a given probability $p_i $ of completing without a failure, i.e., in time $t_i $. Furthermore, failures occur independently and are detected at the end of the task during which they occur. The second model admits a continuous time failure mode where the failure intervals are independent and identically distributed random variables drawn from any given distribution. In this model, failures are detected immediately. In both models, the algorithm also gives the expected value of the overall completion time and we show how to derive all the other moments.

One of the primary motivations for implementing virtual memory is its ability to automatically manage a hierarchy of storage systems with different characteristics. The composite system behaves as if it were a single-level system having the more desirable characteristics of each of its constituent levels. In this paper we extend the virtual memory concept to within the top level of a two-level hierarchy. Here, the top level is thought of as containing two additional levels within it. This hierarchy is not a physical one, but rather an artificial one arising from the employment of two different replacement algorithms. Given two replacement algorithms, one of which has good performance but high implementation cost and the other poor performance but low implementation cost, we propose and analyze schemes that result in an overall algorithm having the performance characteristics of the former and the cost characteristics of the latter. We discuss the suitability of such schemes in the management of storage hierarchies that lack page reference bits.

This paper discusses the modifications made to the UNIX operating system for the VAX-11/780 to convert it from a swap-based segmented system to a paging-based virtual memory system. Of particular interest is that the host machine architecture does not include page-referenced bits. We discuss considerations in the design of page-replacement and load-control policies for such an architecture, and outline current work in modeling the policies employed by the system. We describe our experience with the chosen algorithms based on benchmark-driven studies and production system use.