=Paper=
{{Paper
|id=Vol-3812/paper9
|storemode=property
|title=Using Answer Set Programming for Assigning Tasks to Computing Nodes
|pdfUrl=https://ceur-ws.org/Vol-3812/paper9.pdf
|volume=Vol-3812
|authors=Franz Wotawa
|dblpUrl=https://dblp.org/rec/conf/confws/Wotawa24
}}
==Using Answer Set Programming for Assigning Tasks to Computing Nodes==
https://ceur-ws.org/Vol-3812/paper9.pdf
Using Answer Set Programming for Assigning Tasks to
Computing Nodes
Franz Wotawa1,*
1
Graz University of Technology (TU Graz), Institute of Software Technology, Inffeldgasse 16b/2, A-8010 Graz, Austria
Abstract
Allocating tasks to computing nodes in a network is an important configuration problem. In the case of fail-safe networks,
such configuration must be changed during operation if a computing node fails. Hence, a fast configuration is required. In
this paper, we formulate a tasks-to-computing-nodes assignment problem and its constraints using answer set programming.
We performed an initial experimental evaluation utilizing several smaller to mid-size problem instances to show whether
logic reasoning based on answer set programming is feasible for practical applications. We discovered that reasoning is fast
if a solution exists but not when there is no solution. Further constraints help to decide that a problem instance is unsolvable
early in the search, which improves the outcome.
Keywords
Configuring computing nodes, ASP models for configuration, Experimental analysis
1. Introduction clingo [8]. The question we want to answer is regard-
ing the approachβs limitations regarding the problem size.
There has been plenty of work in the area of configuration Can we use answer set programming (and in particular
and recommender systems, including service configura- clingo) to provide task assignments fast enough to be
tion [1], governance systems [2], or product configura- used during operation?
tion [3] to refer to recent work. However, answer set We structure this paper as follows. First, we introduce
programming for representing models used for config- the underlying configuration problem and clingo im-
uration and reasoning to obtain valid configuration has plementation. Afterward, we discuss the experimental
recently gained more attention, e.g., see [3, 4, 5]. In this evaluation, i.e., the basic setup and the results obtained.
paper, we contribute to this research direction and intro- Finally, we conclude the paper.
duce a model and an evaluation for configuring networks
comprising computing nodes for executing pre-defined
tasks. The underlying problem is related to scheduling 2. Problem description
and shift designs [6].
The main motivation behind our work comes from We start defining the task to node assignment problem.
practical applications, where, for example, tasks, i.e., pro- We assume we have π computing nodes π1 , . . . , ππ and
grams, have to be deployed on computing nodes in a π tasks π‘1 , . . . , π‘π to be assigned to the nodes. For each
network. Although this problem can be seen as a static node ππ , we know the maximum number of tasks π(ππ )
one that must only be solved before the operation, we it can hold and the available memory π(ππ ). For each
may require to re-configure such a task assignment dur- task π‘π , we know its memory consumption π(π‘π ). From
ing operation whenever a computing node fails (see, e.g., this knowledge, we obtain several constraints an as-
[7]). Such re-configuration tasks have to be carried out signment must fulfill to be valid. In the following, we
under time restrictions. To evaluate whether modern formalize these constraints assuming that the function
reasoning methods like answer set programming can be ππ π πππππ(ππ ) returns a set of tasks that is assigned to a
used for this task, we conduct an experimental evalua- node ππ
tion. This evaluation comprises several instances of the First, the required memory from the tasks assigned to
corresponding task to computing node assignment prob- a node shall never exceed the available memory of this
lems considering various sizes of nodes and tasks. The node. These constraints can be formalized as follows:
β β
evaluation utilizes the answer set programming solver βοΈ
βπ β {1, . . . , π} : β π(π‘π ) β€ π(ππ )β
π‘π βππ π πππππ(ππ )
ConfWSβ24: 26th International Workshop on Configuration, Sep 2β3,
2024, Girona, Spain (1)
*
Corresponding author. Second, the number of tasks assigned to a node shall
" wotawa@ist.tugraz.at (F. Wotawa) never exceed the maximum number of tasks the node
~ https://www.tugraz.at/ (F. Wotawa)
can hold, i.e., formally, we write:
0000-0002-0462-2283 (F. Wotawa)
Β© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0). βπ β {1, . . . , π} : (|ππ π πππππ(ππ )| β€ π(ππ )) (2)
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
A solution to the tasks to computing nodes assignment of a task. Let us call this predicate select that takes a
problem is an assignment of all tasks to all nodes such task T as the first parameter and node N as the second.
that βπ β {1, . . . , π} : βπ β {1, . . . , π} : π‘π β In clingo, the generate part for the node assignment
ππ π πππππ(ππ ), there is no tasks assigned to two different problem is given as follows:
nodes, i.e., βπ, π β {1, . . . , π}, π ΜΈ= π : ππ π πππππ(ππ ) β©
ππ π πππππ(ππ ) = β
, and all constraints are fulfilled. Such { select(T,N) : node(N) } = 1 :- task(T).
an assignment is a valid one and may not exist. For ex-
ample, if the number of tasks exceeds the number of free This rule generates a grounded predicate that assigns
slots of the nodes or if the required memory for the tasks tasks to each computing node. Obviously, not all as-
is not provided, there is no solution. Hence, we have signments are correct when considering the constraints.
two necessary conditions that must hold for obtaining a Hence, in the last part, we formalize the first two con-
solution, i.e.: straints of the general problem, i.e., Equations 1 and 2,
π but not the other Equations 3 and 4. For this purpose, we
introduce a predicate nrTasksAssigned that holds the
βοΈ
πβ€ π(ππ ) (3)
π=1 number of tasks that are assigned to a particular node and
π π a predicate memRequired that holds the required mem-
ory for a node considering the assigned tasks. The infor-
βοΈ βοΈ
π(π‘π ) β€ π(ππ ) (4)
π=1 π=1 mation regarding the predicates can be obtained from the
selected task for a node (select predicate) and the mem-
It is worth noting that similar problems have additional ory required for a task. For the latter, we introduce the
constraints, e.g., stating that tasks need to be together predicate memory. The predicate nrTasksAssigned
in the same computing node. We may also introduce can be formalized in clingo as follows:
optimality criteria like preferring solutions requiring the
least amount of computing nodes. Furthermore, we may nrTasksAssigned(N,M) :-
also consider variants of the problem, i.e., reconfiguration M = #count {T:select(T,N)},
of assignments. In the context of this paper, we do not node(N).
tackle such extensions. We solely focus on answering
the question regarding the applicability of the answer Similar, we can define the memRequired predicate:
set program to solve the problem within a reasonable
amount of time. memRequired(N,M) :-
M = #sum {NM:select(T,N), memory(T,NM)},
After outlining the problem in general, we present a
node(N).
solution using answer set programming where we rely
on the syntax of the clingo solver1 [8], which is similar Using these predicates, we can formulate the con-
to the Prolog language. Due to space restrictions, we straints:
do not give an introduction to answer set programming
(ASP). Instead, we refer to introductory literature into :- nrTasksAssigned(N,M), tcapacity(N,C), M>C.
ASP, e.g., [9]. :- memRequired(N,M), mcapacity(N,C), M > C.
A clingo model for the node assignment problem
comprises three parts. First, we define the number of The first constraint states that it is impossible to as-
computing nodes and tasks and their capacities and re- sign more tasks to a node than the node can hold. The
quirements. For every node, e.g., n2, we use three facts, second constraint states that the memory requirements
where the predicate tcapacity denotes the maximum of all tasks should not exceed the memory capacity of
number of tasks, and mcapacity the maximum available the computing node.
memory for the given task.:
node(n2). tcapacity(n2,1). mcapacity(n2,20). 3. Experimental evaluation
For each task, e.g., t1, we add two facts, where the The following experimental evaluation aims to investi-
predicate memory is for defining the required memory gate the runtime behavior for finding one solution of the
of the given task to a pre-defined value: task to computation node assignment problem using the
ASP solver clingo. In particular, we are interested in
task(t1). memory(t1,30). the number of nodes that can be handled requiring less
than a fixed boundary of time, e.g., 0.01 or 0.1 seconds.
Second, we generate all potential solutions. For this In the following, we outline the experimental setup and
purpose, we introduce a predicate for a node assignment present and discuss the obtained results.
1
See https://potassco.org/about/
which can be achieved for 20 or 13 nodes, respectively.
Runtime in seconds vs. number of nodes
Motivated by the results, we performed further ex-
periments, considering problems that likely cannot be
100
time π‘ in seconds
solved. Unfortunately, in this case, we often ran into
reaching the solving time limit of 10 seconds, even start-
10β1 ing with small examples only considering 5 computing
nodes. Instances with more than 7 nodes that might be
10β2 unsatisfiable always reach the 10-second limit. For those
instances where unsatisfiability could be established, the
10β3 runtime varies between 0.003 and 6.255 seconds. The
0 50 100
latter was obtained for a problem instance comprising
nodes π
7 computing nodes. Hence, unsatisfiable instances can
hardly be identified when considering more computing
Figure 1: Solving runtime of consistent instances
nodes, which might also be an issue for practical applica-
tions.
We carried out another experiment to tackle the men-
Experimental setup: To develop several instances of tioned problem of potential unsatisfiability. We selected
the task assignment problem, we wrote a Java program 3 problem instances for which we could not compute
for generating such instances automatically. We ranged a result. Two instances had 7 nodes, and one had 15
the number of nodes from 5 to 100. The number of tasks nodes. For these problem instances, we added further
for each instance was randomly chosen between the num- constraints that cover Equations 3 and 4. For all three
ber of nodes and double the number of nodes. The ca- clingo files that correspond to the problem instances,
pacity of each node was randomly set from 1,2, . . . , 10. we added the following code:
The memory provided by each node was randomly cho-
sen from 20, 40, 60,. . . , 200. The memory required by totalCapacity(C) :- C=#sum{T:tcapacity(N,T)}.
every task was randomly set from 10, 20, and 30. With totalMemReq(C) :- C=#sum{M:memory(T,M)}.
this setup, we generated only satisfiable instances, i.e., totalMem(C) :- C=#sum{N:mcapacity(CN,N)}.
problem instances where a solution exists. For a category :- totalCapacity(C), C < 21.
:- totalMemReq(Ctask), totalMem(Cnode),
of instances comprising π nodes, we called the instance Ctask > Cnode.
generator 10 times. Finally, we received 200 different
problem instances. Note that the 21 in the above code represents the num-
We conducted the experiments using an Apple Mac- ber of tasks2 . We adapted this value for each instance
Book Pro, with an Apple M1 CPU comprising 8 cores and and set it to 21, 28, and 60 respectively. When running
16 GB of main memory, running under macOS Sonoma clingo on the three files, we obtained an immediate
Version 14.4.1. For computing solutions, we relied on response of unsatisfiability. In all cases, this response
clingo version 5.7.1 and applied the standard setup. was less than 0.025 seconds. Hence, adding further con-
straints that allow distinguishing satisfiable from unsat-
Experimental results: After generating the prob- isfiable cases as early as possible solves the problem.
lem instances, we ran clingo to compute one solu- In summary, clingo allows for fast computation of
tion, i.e., we ran clingo using the prompt clingo solutions if they exist. The reasoning for the mentioned
βtime-limit=10 βoutf=2 for each file. Hence, we tasks-to-computing-nodes assignment problem is fast
set a time limit of 10 seconds and obtained all results in enough for at least smaller examples to ensure a timely
JSON format. After analyzing the results for correctness, response. However, whether this is good enough depends
we summarized the outcome, i.e., the runtime for each on the application domain. The challenges we obtained in
category of a particular number of nodes. Figure 1 de- the case of unsatisfiability can be solved by setting a time
picts the minimum, maximum, and average runtime for limit for clingo and introducing additional constraints.
all 10 runs for each category. Results from this case study may also apply to other
We see that when using ASP solving utilizing clingo configuration problems.
we can provide one solution even for larger instances
of 100 computing nodes in a reasonable amount of time. Threats to validity: There are many threats to valid-
However, when using the approach during operation, and ity worth mentioning. The experimental evaluation is
especially for systems with harder requirements regard- 2
ing answering time, e.g., real-time systems, a runtime of The number of tasks for a particular problem instance can also
be obtained using clingo. The command #count{T:task(T)}
almost 3 seconds might not be feasible. We would like delivers this number. However, we set the number manually for
answers in less than 0.1 or 0.01 seconds for such systems, the three experiments.
limited in the number of problem instances. There might Taupe, L. Fuentes (Eds.), Proc. 25th Intl. Workshop
be satisfiable instances that may take longer than re- on Configuration, MΓ‘laga, Spain, September 6-7,
ported for a given number of computing nodes. However, 2023, CEUR-WS.org, 2023, pp. 67β74. URL: https:
we do not expect a very large deviation from the results. //ceur-ws.org/Vol-3509/paper10.pdf.
Furthermore, we only considered one rather simple con- [3] R. Comploi-Taupe, G. Friedrich, T. Niestroj, Dynamic
figuration problem. In case of more complex problems, aggregates in expressive ASP heuristics for config-
we expect different runtimes. Nevertheless, the effect of uration problems, in: J. M. Horcas, J. A. Galindo,
adding constraints to determine unsatisfiability as early R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl.
as possible should still be visible. This might also hold Workshop on Configuration, MΓ‘laga, Spain, Septem-
for the observation that unsatisfiability might be hard ber 6-7, 2023, CEUR-WS.org, 2023, pp. 75β84. URL:
to identify and, therefore, require more computing time. https://ceur-ws.org/Vol-3509/paper11.pdf.
We carried out all experiments using clingoβs standard- [4] N. RΓΌhling, T. Schaub, T. Stolzmann, Towards a for-
setting. There might be differences to observe when malization of configuration problems for asp-based
changing parameters and setup. There might also be reasoning: Preliminary report, in: J. M. Horcas, J. A.
differences when considering other versions of clingo, Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc.
the hardware, or the operating system. Finally, the repre- 25th Intl. Workshop on Configuration, MΓ‘laga, Spain,
sentation of the problem in clingo might also influence September 6-7, 2023, CEUR-WS.org, 2023, pp. 85β94.
the performance. URL: https://ceur-ws.org/Vol-3509/paper12.pdf.
[5] R. Comploi-Taupe, A. A. Falkner, S. Hahn, T. Schaub,
G. Schenner, Interactive configuration with ASP
4. Conclusions multi-shot solving, in: J. M. Horcas, J. A. Galindo,
R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl.
In this paper, we used the configuration problem of as-
Workshop on Configuration, MΓ‘laga, Spain, Septem-
signing tasks to computing nodes to answer whether
ber 6-7, 2023, CEUR-WS.org, 2023, pp. 95β103. URL:
answer-set programming is feasible for practical appli-
https://ceur-ws.org/Vol-3509/paper13.pdf.
cations. For smaller problem instances, answer set pro-
[6] M. Abseher, M. Gebser, N. Musliu, T. Schaub,
gramming might be feasible, providing a fast response
S. Woltran, Shift design with answer set program-
within a fraction of a second. For larger instances, we
ming, in: F. Calimeri, G. Ianni, M. Truszczyn-
may not be able to provide a solution within a reasonable
ski (Eds.), Proc. 13th Intl. Conf. on Logic Program-
answer time. Furthermore, we identified a challenge, i.e.,
ming and Nonmonotonic Reasoning, 2015, Lex-
the extended runtime required for providing an answer
ington, KY, USA, September 27-30, 2015., volume
in case of unsatisfiability, and a solution, i.e., the effect of
9345 of LNCS, Springer, 2015, pp. 32β39. URL:
additional constraints on reducing the runtime. In future
https://doi.org/10.1007/978-3-319-23264-5_4. doi:10.
research, we want to extend the configuration problem to
1007/978-3-319-23264-5\_4.
capture the case of task assignments for computing net-
[7] A. Ballesteros, M. Barranco, J. Proenza, L. Almeida,
works at runtime. For this purpose, we want to formulate
F. Pozo, P. Palmer-RodrΓguez, An infrastructure
a corresponding re-configuration problem. Furthermore,
for enabling dynamic fault tolerance in highly-
we want to extend the experimental evaluation using
reliable adaptive distributed embedded systems
more example instances and additional constraints and
based on switched ethernet, Sensors 22 (2022)
consider computing optimal solutions concerning a given
7099. URL: https://doi.org/10.3390/s22187099. doi:10.
optimization criteria, e.g., using the least number of com-
3390/S22187099.
puting nodes.
[8] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub,
Multi-shot asp solving with clingo, Theory and
References Practice of Logic Programming 19 (2019) 27β82.
doi:10.1017/S1471068418000054.
[1] E. M. StrΓΈm, T. M. MΓΌnsberg, L. Hvam, Identifying [9] T. Eiter, G. Ianni, T. Krennwallner, Answer
potential applications of service configuration sys- set programming: A primer, in: S. Tessaris,
tems in a logistics company, in: J. M. Horcas, J. A. E. Franconi, T. Eiter, C. Gutierrez, S. Hand-
Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. schuh, M.-C. Rousset, R. A. Schmidt (Eds.), Rea-
25th Intl. Workshop on Configuration, MΓ‘laga, Spain, soning Web. Semantic Technologies for Informa-
September 6-7, 2023, CEUR-WS.org, 2023, pp. 60β66. tion Systems: 5th Intl. Summer School, Brixen-
URL: https://ceur-ws.org/Vol-3509/paper9.pdf. Bressanone, Italy, August 30 - September 4, 2009,
[2] S. MuΓ±oz-Hermoso, D. Benavides, F. J. D. Mayo, pp. 40β110, Springer Berlin Heidelberg, . URL:
Multi-level configuration in smart governance sys- https://doi.org/10.1007/978-3-642-03754-2_2. doi:10.
tems, in: J. M. Horcas, J. A. Galindo, R. Comploi- 1007/978-3-642-03754-2\_2.