Online load balancing on uniform machines with limited migration - Maack, Marten (Operations Research Letters)
Keywords: Applied Mathematics; Industrial and Manufacturing Engineering; Management Science and Operations Research; Software

On-The-Fly Compute Centers II: Execution of Composed Services in Configurable Compute Centers - Karl, Holger; Maack, Marten; Meyer auf der Heide, Friedhelm; Pukrop, Simon; Redder, Adrian (On-The-Fly Computing -- Individualized IT-services in dynamic markets)

Server Cloud Scheduling - Maack, Marten; Meyer auf der Heide, Friedhelm; Pukrop, Simon (Algorithmica)
Abstract Consider a set of jobs connected to a directed acyclic task graph with a fixed source and sink. The edges of this graph model precedence constraints and the jobs have to be scheduled with respect to those. We introduce the server cloud scheduling problem, in which the jobs have to be processed either on a single local machine or on one of infinitely many cloud machines. For each job, processing times both on the server and in the cloud are given. Furthermore, for each edge in the task graph, a communication delay is included in the input and has to be taken into account if one of the two jobs is scheduled on the server and the other in the cloud. The server processes jobs sequentially, whereas the cloud can serve as many as needed in parallel, but induces costs. We consider both makespan and cost minimization. The main results are an FPTAS for the makespan objective for graphs with a constant source and sink dividing cut and strong hardness for the case with unit processing times and delays.
Keywords: Applied Mathematics; Computer Science Applications; General Computer Science

Scheduling with Many Shared Resources - Deppert, Max A.; Jansen, Klaus; Maack, Marten; Pukrop, Simon; Rau, Malin (2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS))

On-The-Fly Computing -- Individualized IT-services in dynamic markets - Haake, Claus-Jochen; Meyer auf der Heide, Friedhelm; Platzner, Marco; Wachsmuth, Henning; Wehrheim, Heike
In the proposal for our CRC in 2011, we formulated a vision of markets for IT services that describes an approach to the provision of such services that was novel at that time and, to a large extent, remains so today: „Our vision of on-the-fly computing is that of IT services individually and automatically configured and brought to execution from flexibly combinable services traded on markets. At the same time, we aim at organizing markets whose participants maintain a lively market of services through appropriate entrepreneurial actions.“ Over the last 12 years, we have developed methods and techniques to address problems critical to the convenient, efficient, and secure use of on-the-fly computing. Among other things, we have made the description of services more convenient by allowing natural language input, increased the quality of configured services through (natural language) interaction and more efficient configuration processes and analysis procedures, made the quality of (the products of) providers in the marketplace transparent through reputation systems, and increased the resource efficiency of execution through reconfigurable heterogeneous computing nodes and an integrated treatment of service description and configuration. We have also developed network infrastructures that have a high degree of adaptivity, scalability, efficiency, and reliability, and provide cryptographic guarantees of anonymity and security for market participants and their products and services. To demonstrate the pervasiveness of the OTF computing approach, we have implemented a proof-of-concept for OTF computing that can run typical scenarios of an OTF market. We illustrated the approach using a cutting-edge application scenario – automated machine learning (AutoML). Finally, we have been pushing our work for the perpetuation of On-The-Fly Computing beyond the SFB and sharing the expertise gained in the SFB in events with industry partners as well as transfer projects. This work required a broad spectrum of expertise. Computer scientists and economists with research interests such as computer networks and distributed algorithms, security and cryptography, software engineering and verification, configuration and machine learning, computer engineering and HPC, microeconomics and game theory, business informatics and management have successfully collaborated here.

mobile-env: An Open Platform for Reinforcement Learning in Wireless Mobile Networks - Schneider, Stefan Balthasar; Werner, Stefan; Khalili, Ramin; Hecker, Artur; Karl, Holger (IEEE/IFIP Network Operations and Management Symposium (NOMS))
Recent reinforcement learning approaches for continuous control in wireless mobile networks have shown impressive results. But due to the lack of open and compatible simulators, authors typically create their own simulation environments for training and evaluation. This is cumbersome and time-consuming for authors and limits reproducibility and comparability, ultimately impeding progress in the field. To this end, we propose mobile-env, a simple and open platform for training, evaluating, and comparing reinforcement learning and conventional approaches for continuous control in mobile wireless networks. mobile-env is lightweight and implements the common OpenAI Gym interface and additional wrappers, which allows connecting virtually any single-agent or multi-agent reinforcement learning framework to the environment. While mobile-env provides sensible default values and can be used out of the box, it also has many configuration options and is easy to extend. We therefore believe mobile-env to be a valuable platform for driving meaningful progress in autonomous coordination of wireless mobile networks.
Keywords: wireless mobile networks; network management; continuous control; cognitive networks; autonomous coordination; reinforcement learning; gym environment; simulation; open source

Cardinality Constrained Scheduling in Online Models - Epstein, Leah; Lassota, Alexandra; Levin, Asaf; Maack, Marten; Rohwedder, Lars (39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference))

Age of Information Process under Strongly Mixing Communication -- Moment Bound, Mixing Rate and Strong Law - Redder, Adrian; Ramaswamy, Arunselvan; Karl, Holger (Proceedings of the 58th Allerton Conference on Communication, Control, and Computing)
The decentralized nature of multi-agent systems requires continuous data exchange to achieve global objectives. In such scenarios, Age of Information (AoI) has become an important metric of the freshness of exchanged data due to the error-proneness and delays of communication systems. Communication systems usually possess dependencies: the process describing the success or failure of communication is highly correlated when these attempts are ``close'' in some domain (e.g. in time, frequency, space or code as in wireless communication) and is, in general, non-stationary. To study AoI in such scenarios, we consider an abstract event-based AoI process $Δ(n)$, expressing time since the last update: If, at time $n$, a monitoring node receives a status update from a source node (event $A(n-1)$ occurs), then $Δ(n)$ is reset to one; otherwise, $Δ(n)$ grows linearly in time. This AoI process can thus be viewed as a special random walk with resets. The event process $A(n)$ may be nonstationary and we merely assume that its temporal dependencies decay sufficiently, described by $α$-mixing. We calculate moment bounds for the resulting AoI process as a function of the mixing rate of $A(n)$. Furthermore, we prove that the AoI process $Δ(n)$ is itself $α$-mixing from which we conclude a strong law of large numbers for $Δ(n)$. These results are new, since AoI processes have not been studied so far in this general strongly mixing setting. This opens up future work on renewal processes with non-independent interarrival times.

Multi-agent Policy Gradient Algorithms for Cyber-physical Systems with Lossy Communication - Redder, Adrian; Ramaswamy, Arunselvan; Karl, Holger (Proceedings of the 14th International Conference on Agents and Artificial Intelligence)

Distributed gradient-based optimization in the presence of dependent aperiodic communication - Redder, Adrian; Ramaswamy, Arunselvan; Karl, Holger (arXiv:2201.11343)
Iterative distributed optimization algorithms involve multiple agents that communicate with each other, over time, in order to minimize/maximize a global objective. In the presence of unreliable communication networks, the Age-of-Information (AoI), which measures the freshness of data received, may be large and hence hinder algorithmic convergence. In this paper, we study the convergence of general distributed gradient-based optimization algorithms in the presence of communication that neither happens periodically nor at stochastically independent points in time. We show that convergence is guaranteed provided the random variables associated with the AoI processes are stochastically dominated by a random variable with finite first moment. This improves on previous requirements of boundedness of more than the first moment. We then introduce stochastically strongly connected (SSC) networks, a new stochastic form of strong connectedness for time-varying networks. We show: If for any $p \ge0$ the processes that describe the success of communication between agents in a SSC network are $α$-mixing with $n^{p-1}α(n)$ summable, then the associated AoI processes are stochastically dominated by a random variable with finite $p$-th moment. In combination with our first contribution, this implies that distributed stochastic gradient descend converges in the presence of AoI, if $α(n)$ is summable.