Tuesday, July 2, 2019

Autonomous Computing Systems: The Convergence of Control Theory and Computing Systems

Associate editor: Danilo Pianini (@DanySK86)

Computing systems are becoming increasingly complex both in terms of scale, and in terms of functionality. Applications need to process large amounts of data with time requirements that are becoming smaller and smaller. The distribution of computation has an unprecedented growth. It is sufficient to think about the number of Internet of Things (IoT) devices that is increasing exponentially, and it is expected to reach 31.4 billion by 2023.
Such an increasing complexity needs cannot be handled with static policies or with human operators, and sound mathematical approaches are needed, as also highlighted in the seminal paper by A.-L. Barabási, 2005. In particular, novel applications like smart houses, smart grids and cities, Industry 4.0, and robotics, pose a number of challenges for the efficient management of the computational resources, and for the design of scalable and efficient autonomous solutions.

The need for self-adaptation

The design of decision-making strategies for computing systems is known in the literature as self-adaptation, i.e., computing systems dynamically adapt to changes. Several disciplines have been identified as potential contributors. Among these, machine learning provides additional knowledge of the system; see for example the work by Esfahani et al., 2013, and control theory provides a vast array of tools for designing robust adaptive physical systems with formally assured behavior; see for example Cheng et al., 2009 or Filieri et al., 2017. The combination of knowledge, robustness and formal guarantees has led to increased interest in developing control-based approaches in various computing system problems, as highlighted in the surveys by Patikirikorala et al., 2012 and by Shevtsov et al., 2018.

Modeling computing systems

In almost every field of science, there is an attempt of building mathematical representations of the physical world. On the other hand, Computer Science seems to be a bit different. Linus Tolvalds wrote:

I'm personally convinced that computer science has a lot in common with physics. Both are about how the world works at a rather fundamental level.
The difference, of course, is that while in physics you're supposed to figure out how the world is made up, in computer science you create the world.
Within the confines of the computer, you're the creator. You get to ultimately control everything that happens. If you're good enough, you can be God. On a small scale. 
Linus Torvalds, Just for Fun

Even though we are the ones creating our computing systems, it seems that we have a little understanding on how to model their runtime behavior. This may be due to the fact that the way we conceive algorithms is fundamentally different with respect to the way we describe dynamic models. The gap in the two approaches is very difficult to fill, and several attempts has been made. Techniques ranging from Markov Decision Processes to Neural Networks, have been widely explored in the scientific literature in different fields.

One model to rule them all?

A very important distinction should be made on the nature of models in science. There are (at least) three types of models:

  • Simulation models, where the objective is to represent in the most accurate way the behavior of the modeled system, and to simulate it completely in silico, i.e., in a computer simulation. They are the most common models in almost every field of science, including physics, chemistry, and computer science.
  • Prediction models, where the objective is to provide forecasts on the future behavior of a system, based on its known past behavior. The main difference with respect to simulation models is that at every time step the model is fed with the most updated values of its behavior. This is a very common model in statistics, finance, or even weather forecast, where we try to make our best guesses on the future behavior of some financial indexes or what will the weather look like in the next few days, based on the current knowledge of the system.
  • Control models, where the objective is to describe the main dynamics of the system with simple models, in order to capture basic properties, i.e., how the system responds to external stimuli in terms of timing properties during transients.

The need for control models

A famous quote says:
All models are wrong but some are useful
In fact, all the types of models are approximations of the reality, and they are meant for a specific purpose. Using a prediction model to simulate the behavior of a complex system is not a good idea.

As a simple example, Gulisano et al., 2018 provided a very accurate, yet complex, mathematical description of how to model performance in a join operator in data streaming applications. The results show that it is possible to model the latency and throughput of the operator even in presence of overload, and obtain an error in the order of fractions of milliseconds. However, adopting such a model for designing a control strategy is extremely challenging.

More in general, several  not all  of the models proposed in computer science get closer to simulation models rather than control models. They are extremely accurate but they fall short when it comes to model-based self-adaptation design. To make a physics parallel, most of the time, the proposed models are focusing on describing the motion of single particles to infer what is the temperature in a room: The model itself becomes extremely complicated, but it is of little use when a controller needs to be designed for controlling the temperature in a room. The concept of a higher level of abstraction is key to enable control models for computing systems.

Control-based Computing System Design

The importance of scalable methods for analysis and synthesis of large-scale inter-connected systems is widely recognized. Resource efficient solutions will not be possible without a firm mathematical foundation. Being able to program and manage computing systems in an efficient way is of fundamental importance. By combining feedback-based computing with suitable programming models, it is possible to design predictable applications with guarantees on response time, resource allocation, and power consumption.

Control theory seems to be the most promising approach to tame such complexity. Other machine learning approaches represent a valid alternative, with the disadvantage of limiting the capabilities of formally assess properties of the controlled system, as well as the generality of the proposed solutions. Such limitations generated the new trend of explainable Artificial Intelligence (AI), in order to describe the way several machine learning strategies take their decisions.
On the other hand, control-based approaches are typically designed according to well understood policies, with deterministic algorithms. Model-based design is in fact the most common approach, since it allows the control engineer to provide formal guarantees on the robustness and on the performance that can be obtained with the designed solutions.

Wrapping up

The main challenge in applying control theory to computing systems lies in the modeling step. Nonetheless, there have been in the past several works control-based solutions, trying to combine model-free or black-box modeling approaches to compensate for the lack of suitable control models. Even in such cases, control-based solutions have proven to be a more effective approach with respect to classical machine learning approaches, e.g., see Maggio et al., 2012, as well as other heuristic approaches, e.g., see Terraneo et al., 2014.

The area of the design of autonomous computing systems is extremely broad, and with a lot of opportunities to advance science and engineering. The innovation of the next generation computing systems lies in between different scientific communities, including software engineering, computer engineering, computer science, control theory, statistics, and mathematics.

1 comment:

  1. A very interesting article. The insights are really helpful and informative. Thanks for posting.
    Personalized Learning And Development