11institutetext: School of Information Technologies, University of Sydney,
Sydney, Australia 11email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# A CP-Net based Qualitative Composition Approach for an IaaS Provider

Sheik Mohammad Mostakim Fattah  Athman Bouguettaya  Sajib Mistry

###### Abstract

We propose a novel CP-Net based composition approach to qualitatively select
an optimal set of consumers for an IaaS provider. The IaaS provider’s and
consumers’ qualitative preferences are captured using CP-Nets. We propose a
CP-Net composability model using the semantic congruence property of a
qualitative composition. A greedy-based and a heuristic-based consumer
selection approaches are proposed that effectively reduce the search space of
candidate consumers in the composition. Experimental results prove the
feasibility of the proposed composition approach.

###### Keywords:

Cloud Service Composition IaaS Composition Qualitative Preference Composition
CP-Net composability model Monte Carlo Simulation

##  1 Introduction

Infrastructure-as-a-Service (IaaS) model is a cloud service delivery model
where computational resources are usually delivered as Virtual Machines (VMs)
to cloud consumers [1, 14]. The functional properties of an IaaS service are
usually CPU, storage, and memory [6]. The Non-functional properties (e.g.,
availability, throughput, and price) are usually attached with VMs or IaaS
services as Quality of Services (QoS). IaaS services are generally configured
based on the functional and non-functional requirements of consumers. For
example, Amazon EC2 IaaS provider has different types of VMs (e.g., CPU-
intensive, Memory-intensive, and Network-intensive) that are targeted for
different types of consumers (e.g., individuals, small enterprises, and large
organizations).

The long-term IaaS composition is a topical research issue [12]. The
composition from an IaaS provider’s perspective is defined as the selection of
a set of optimal consumer requests [11]. An effective IaaS composition
achieves the economic expectations, i.e., revenue and profit maximization of
the provider. The IaaS composition ensures the optimal utilization of
available computing resources for an IaaS provider. The selection of optimal
consumer requests is essential to achieve the IaaS composition. For example,
selecting service requests from a group of small enterprises may be more
profitable than the single service request from a large organization due to
the scale of economy.

We focus on the qualitative IaaS composition, i.e., selecting the optimal
consumer requests according to the qualitative preferences of the provider.
Qualitative preference models are effective tools for the selection where
there exists uncertainties or incomplete information. The service requirements
of future consumers are uncertain and probabilistic in nature [2, 10, 13]. A
provider’s preference may change with the requirements of the consumers. The
dynamic business environment may also trigger a change in the provider’s
qualitative preferences. For example, the provider may observe a very high
demand for Network-intensive services in the Christmas or holiday period. The
provider may prefer to compose Network-intensive services than CPU-intensive
services to increase its revenue.

IaaS consumers’ requirements can be represented in a natural and intuitive
manner using qualitative approaches [19]. Qualitative models provide the
necessary tool to select appropriate providers where quantitative models are
not applicable. A consumer requires to explicitly indicate the exact values of
the functional and non-functional properties of a service in a quantitative
model. It may not be possible to find providers that can meet the exact
requirements of the consumers. For example, a consumer may require 10 units of
CPU and 20 units of memory at 20 dollars/month at the level of 100%
availability. Such requirements may not be exactly fulfilled by any service
provider. In contrast, qualitative preferences can be expressed by comparison.
For instance, a content provider (IaaS consumer) prefers a “high” network
bandwidth to a “low” network bandwidth. The content provider may also specify
conditional preferences. For example, if the price of network bandwidth is
very low, a “high” network bandwidth is preferred over a “low” network
bandwidth. These qualitative preferences are used to select suitable providers
for consumers.

The IaaS composition problem is modeled in both quantitative and qualitative
approaches [14, 12, 20, 21, 8]. The quantitative approaches do not consider
the qualitative preferences of the provider. The composition of requests is
transformed into an optimization problem in quantitative approaches. The
proposed approaches (e.g., metaheuristic optimization and integer programming)
are not applicable in the qualitative IaaS composition. A heuristic based
sequential optimization approach is proposed in the qualitative IaaS
composition [11]. This approach considers quantitative requirements of the
consumers and matches them with the qualitative preferences of the provider.
To the best of our knowledge, existing composition approaches are not
applicable where both the provider and consumer have qualitative preferences.

We propose a Conditional Preference Network (CP-Net) based qualitative
composition approach for an IaaS provider. We represent qualitative
conditional preferences using CP-Nets. The CP-Net is a very effective tool to
represent and reason with qualitative conditional preferences under ceteris
paribus (“everything else being equal”) semantics. A CP-Net creates a directed
graph where each node is an attribute of a service preference. The edge
between nodes defines the priority among service preferences. The rank of
service preferences is generated by traversing the graph. We assume that the
CP-Nets of the provider and the consumers are provided for simplicity. Our
target is to select the optimal composition of consumers’ CP-Nets that has the
highest similarity measure with the CP-Net of the provider.

We propose a CP-Net based qualitative composition approach for an IaaS
provider. First, we propose a novel CP-Net composability model to compose CP-
Nets of multiple consumers using the semantic congruence property of a
qualitative composition. Next, we propose a similarity checking mechanism
between CP-Nets using the coefficient of correlations. It directs us to apply
the brute-force approach where all possible composition of consumers’ CP-Nets
is considered to select the optimal composition. The brute-force approach is
not a practical solution for composing a large set of consumer’s CP-Nets due
to its exponential runtime. we propose a heuristic-based algorithm and a
greedy algorithm that reduces search space for compositions. The key
contribution of our research is summarized below:

  * •

A CP-Net composability model for the qualitative composition of IaaS consumers
using the semantic congruence property.

  * •

A qualitative similarity measure approach using the correlation coefficient.

  * •

A heuristic-based and a greedy-based consumer selection approaches to reduce
the search space using semantic similarities between the provider’s and
consumer’s qualitative preferences.

##  2 Motivation Scenario

Let us assume an IaaS provider offers VM services based on a fixed set of
computational resources for a specific period of time. Its resource capacity
is up to 100 virtual CPU units and 100 memory units. For simplicity, we
consider “price” as the only QoS in a VM and we omit “network bandwidth (NB)”
functionality from a VM. We also assume that both the consumers’ qualitative
requirements and the providers’ qualitative preferences on CPU, memory, and
price are following the same semantic levels in Figure 1(a). Three levels of
semantics, i.e., high, moderate, and low for each attribute are specified in
the semantic table in Figure 1(a). The IaaS provider builds different types of
strategies of service provisions. As there exist uncertainties on future
consumers’ requirements, it builds the strategies using qualitative models. We
assume that the provider receives qualitative requests from three consumers.
The target is to select an optimal set of consumer requests that matches with
its preferred ways to service provisions.

We consider a “CPU-intensive” and a “memory-intensive” service provisions
strategies for the provider. As the CP-Net provides an effective way to
represent conditional qualitative preferences, we represent the “CPU-
intensive” strategy as CP1 and the “memory-intensive” strategy as CP2 in
Figure 1(b). The “CPU-intensive” strategy is to offer CPU intensive services
at relatively moderate prices to attract consumers with CPU intensive
requests. Therefore, the CPU is the most important attribute in the dependency
graph of CP1 followed by memory and price. The arc from “CPU” to “memory”
implies that the provision of “memory” levels in a VM depends on the selection
of “CPU” levels. The preference of CPU provisions is expressed as $c3\succ c2$
in the CPT of CPU. It implies that the provider does not want to offer the
“low” CPU services. The choice of CPU levels decides the choices of memory
levels in CP1. The provider prefers the “moderate” memory to the “high” memory
if the “high” CPU is chosen in the service provision according to CP1. If the
choice of CPU is “moderate”, the provider prefers the “high” memory to the
“moderate” memory. Based on the selection of memory levels, the provider
selects the price levels if the “high” memory is chosen according to the CPT
of price in CP1. The provider prefers the “high” price to the “moderate”
price. However, the provider prefers the “moderate” price to the “high” price
for the “moderate” memory units. Similarly, CP2 represents the “memory-
intensive” strategy where memory is the most important attribute in the
dependency graph of CP2 followed by CPU and price.

(a)  (b)

(c)

Figure 1: (a) Semantic Table for Service Attributes (b) CP-Nets of an IaaS
Provider (c) CP-Nets of consumers

The requirements of consumer A, B, and C are captured by CP3, CP4, and CP5
respectively in Figure 1(c). Consumer A prefers “price-sensitive” services.
The price is the most important attribute in the dependency graph of CP3
followed by memory and CPU. The Consumer A mentions its inability to consume
“high” priced (P3) services due to budget constraints and prefers the “low”
price to “moderate” priced services i.e., $p1\succ p2$ according to the CPT of
price in CP3. Its memory requirements depend on the choice of price. In the
CPT of memory in CP3, the “moderate” memory is preferred over the “high”
memory in the required service if the “low” price is already chosen. If the
“moderate” price is chosen, it sets a higher priority to “high” memory than
the “moderate” memory. Preferences of CPU requirements are defined based on
the choice of memory in a similar way. The consumer B has “memory-intensive”
qualitative requirements. Therefore, memory is the root attribute in CP4. The
choice CPU depends on the choice of memory and the choice of price depends on
the choice of CPU in CP4. The consumer C defines “CPU-intensive” preferences
in a similar way.

The IaaS provider can select the optimal composition of consumer’s requests,
i.e., CP-Nets from three consumers in $2^{3}-1$ = 7 possible ways. Multiple
consumer’s CP-Nets may not be composable for their semantic differences. For
example, the “Price-sensitive” requirement (CP3) of consumer A prefers to
receive the “low” memory level services if the price is at a “low” level. The
“memory-sensitive” requirement (CP4) of consumer B prefers to receive the
“high” memory level services even at a “high” level. Hence, CP3 and CP4 are
not composable as they create semantic ambiguity in the composition. We
propose a composability model to determine whether CP-Nets of two consumers
are composable or not.

Finding all possible compositions of preferences in a brute force approach can
be very inefficient. The number of all possible combination of N consumers is
($2^{N}-1$). We propose a heuristic algorithm to reduce the search space of
consumers by finding the relative similarity between the consumers’ CP-Net and
the provider’s CP-Net. For example, if the provider’s strategy is “CPU-
intensive”, i.e., CP1; selecting the “price-sensitive” consumer A in a
composition may not yield the optimal result as they are semantically very
dissimilar. The search space reduces to 2 consumers (consumer B and C) and the
optimal composition is selected from $2^{2}-1$ = 3 compositions out of the 7
possible ways.

##  3 CP-Nets for Qualitative IaaS requests and provisions

A CP-Net is a graphical model to formally represent and reason about
qualitative preference relations. A CP-Net consists of a directed dependency
graph and conditional preference tables (CPTs). The dependency graph is
defined over a set of functional and non-functional attributes
$V=\\{X_{1},….,X_{n}\\}$. A child node in a dependency graph depends on a set
of direct parent nodes $Pa(X_{i})$. The child node is connected by an arc from
$Pa(X_{i})$ to $X_{i}$ in the dependency graph. Parent attributes affect the
user’s preferences over the value of $X_{i}$. Each node $X_{i}$ in the
dependency graph has $Pa(X_{i})$ except for the root nodes.

The CPT of each variable $X_{i}$ is defined over the finite, discrete domain
$D(X_{i})$ and semantic domains $S(X_{i})$. Each value $x_{n}$ in $D(X_{i})$
is mapped into a semantic value in $S(X_{i})$ using a semantic mapping table,
$SemTable(X_{n},x_{n})$. Figure 1(a) is a semantic table that maps 71-100
units of CPU as a “high” CPU value. We only focus on the attributes that are
compatible with additive operations. Hence, we define $s_{i}+s_{j}=s_{k}$ for
$S(X_{i})$. For example, $c1+c1=c2$ implies two “low” CPU can be added and
generates a “moderate” CPU unit.

The preference between two values of an attribute $X_{i}$ is specified by
$\succ$ for a given value of the paraent attribute $Pa(X_{i})$. A user
explicitly defines its preferences over the semantic values of $X_{i}$ for
each complete outcome on $Pa(X_{i})$. The preferences take the form of total
or partial order over $S(X_{i})$. For example, the attributes of CP1 are $C$,
$M$, and $P$ with semantic domains containing $x_{i}$ if $X$ is the name of
the feature. The preferences statements are as follows: $c3\succ c2$,
$c3:m2\succ m3$, $c2:m3\land m2$, $m3:p3\succ p2$, $m2:p3\succ p2$. The
statement $x_{1}\succ x_{2}$ represents the unconditional preference for
$X=x_{1}$ over $X=x_{2}$.

A preference outcome is a combination of values of all attributes of a CP-Net.
For example, $\\{c3,m2,p3\\}$ and $\\{c2,m2,p1\\}$ are two preference outcomes
for CP1 denoted by $o_{1}$ and $o_{2}$. According to the value of attribute
$P$, it can be shown that $o_{1}\succ o_{2}$ or $o_{1}$ dominates $o_{2}$. The
dominance relationship of two preference outcomes is defined as a pre-order
between them. Figure 2 depicts the induced graph [5] of a CP-Net with all
preference outcomes.

Figure 2: Induced Graph

##  4 Composability Model for Qualitative Preferences

Let us consider two CP-Nets $CP_{A}$ and $CP_{B}$. We define the composability
of two CP-Nets as $composable(CP_{A},CP_{B})$ = $\\{true,false\\}$ to find
$CP_{C}$ where $CP_{C}=compose(CP_{A},CP_{B})$. Two CP-Nets are composable if
their composition is semantically congruent. A composition is called
semantically congruent if the relative importance order of preference
attributes for each consumer is preserved without any ambiguity. The relative
importance order is represented as $(a,b)$ which means $a$ is preferred over
$b$. Let us consider a consumer who has the relative importance order of
attributes as $(CPU,memory)$. Another consumer has the relative importance
order of attributes as $(memory,price)$. If the importance order of their
composition is $(CPU,memory,price)$, the composition is considered as
semantically congruent.

###### Definition 1

Semantic Congruence of a Qualitative Composition. A composition is called
semantically congruent when the importance order of preference attributes for
each consumer is preserved without any ambiguity.

The semantic congruence of a composition can be efficiently represented using
the directed acyclic graph of CP-Nets. We use semantic congruence property to
define the composability of two CP-Nets. A CP-Net contains a directed
dependency graph (DDG) and conditional preference table for each node in the
graph. We define the composability of the DDG and the CPT to define the
composability of CP-Nets. Two DDG are considered to be composable if their
combined DDG does not contain any cycle. Figure 3(a) shows two DDGs from two
different CP-Nets (CP1 and CP2). The CPU is the root of CP1. The memory
depends on the CPU and the price depends on the memory in CP1. The DDG of CP2
has the order of memory, CPU, and price. To merge them in a single DDG (i.e.,
CP12) (Figure 3(a)), we create a new DDG where all the attributes (i.e., CPU,
memory, and price) are added from both CP-Nets. The next step is to create
edges between the attributes. First, we take a pair of attributes (e.g., CPU
and price) from the new DDG. If the same pair of attributes has an edge in
either DDG (i.e., CP1 or CP2), we add an edge to the new DDG. We run this
process for each pair of nodes until we cover all edges from both DDGs. If the
resulted DDG contains any cycle, then DDGs are not composable. Two CP-Nets are
composable if their dependency graphs and CPTs are composable.

(a)  (b)

Figure 3: (a) Dependency Graph Composability (b) CPT Composability

###### Definition 2

CP-Net Dependency Graph Composability. Two dependency graphs are composable if
their combined dependency graph does not contain any cycle.

###### Definition 3

CPT Composability. Two CPTs from two different CP-Nets are composable if their
preference attributes are same and their values depend on the same set of
parent nodes.

Two CPTs are composable if they have two properties. First, both CPTs’
attribute nodes should be the same. In Figure 3(b), “CPU” nodes from both DDGs
can be valid candidates to be composable. A “CPU” node from one CP-Net and a
“memory” node from another CP-Net are not composable. Second, the parent nodes
of both nodes should have the same attribute. If two nodes have the same set
of parent nodes, then preference statements of both nodes will depend on the
same set of attributes. Therefore, the preference statements will be
composable. For example, “CPU” nodes of both CP-Nets are unconditional nodes
(i.e., no parent) in Figure 3(b). However, “price” nodes have different
parents (i.e., “memory” and “CPU”). The preference statements will have
conditional attributes. Therefore, the CPTs of the "price" nodes are not
composable.

##  5 Similarity Measurement with Qualitative Preferences

We assume that the IaaS provider expresses its qualitative preferences using
the CP-Net, $CP_{A}$. The provider requires to find an optimal set of consumer
CP-Nets from $\\{CP3,CP4,CP5\\}$ that matches with $CP_{A}$. We apply the
composability model described in the above section and find the composed CP-
Net $CP_{B}$ for a set of composable consumers. If $CP_{A}$ completely matches
with $CP_{B}$, we say it is the optimal composition. To compare the composed
CP-Net with provider’s CP-Net we need to find a similarity measurement
algorithm. The similarity measurement between two CP-Nets can be performed in
two ways [17, 18]. One way is to generate the induced graph of two CP-Nets and
compute the number of common edges between two CP-Nets. This similarity can be
computed by:

$Sim(CP_{A}:CP_{B})=\frac{|\\{e:e\ \in\ In(CP_{A})\ \land\ e\ \in\
In(CP_{B})\\}|}{|\\{e:e\ \in\ In(CP_{A})\ \lor\ e\ \in\ In(CP_{B})\\}|\ -\
|\\{e:e\ \in\ In(CP_{A})\ \land\ e\ \in\ In(CP_{B})\\}|}$

(1)

where $In(CP_{A})$ and $In(CP_{B})$ denotes the induced graph for $CP_{A}$ and
$CP_{B}$. The edge between two attributes is denoted by $e$. The equation 1
computes the ratio between the number of common and total edges between two
induced graphs. This method is computationally expensive and not applicable in
real time [19].

Another way is to compare the CPTs between two CP-Nets using the dependency
graphs. This method is only applicable when two CP-Nets share the same
dependency graph [18]. In that case, the similarity between the provider’s and
consumers’ CP-Net is calculated by the following equation:

$Sim(CP_{A}:CP_{B})=\frac{\sum_{X_{i}}\Big{(}|CPT_{A}(X_{i})\cap
CPT_{B}(X_{i})|\times\prod_{X_{j}\notin
Pa(X_{i})}|SemTable(X_{i})|\Big{)}}{\sum_{X_{i}}\Big{(}|CPT_{A}(X_{i})\cup
CPT_{B}(X_{i})|\times\prod_{X_{j}\notin Pa(X_{i})}|SemTable(X_{j})|\Big{)}}$

(2)

where $CPT_{A}$ and $CPT_{B}$ are the conditional preference table of $CP_{A}$
and $CP_{B}$. $Pa(X_{i})$ denotes the parent attributes of $X_{i}$ and
$SemTable(X_{i})$ represents all values that can be assigned into $X_{i}$. We
assume the composed CP-Net of consumers and the provider’s CP-Net have the
same dependency graph.

##  6 Heuristic-based Consumer Selection approaches

The number of composable consumers grows exponentially with the increase in
the number of consumers ($2^{n})$. Finding all possible combinations of
consumers is inapplicable as it may require a very large time depending on the
number of consumers [12]. Our target is to reduce the search space for the
consumer selection. We propose a greedy-based and a heuristic based consumer
selection algorithm using the similarity between a provider’s and a consumer’s
CP-Nets.

###  6.1 Greedy-based IaaS Consumer Selection Approach

We choose the first consumer who has the highest relative similarity with
provider’s CP-Net in the greedy selection approach. We iteratively choose the
next consumers to achieve the maximum similarity with the provider’s CP-Net.
The following steps are performed in the greedy based approach:

  1. 1.

Select a consumer CP-Net that is has the maximum coefficient of correlation
with the provider’s CP-Net.

  2. 2.

Create a new CP-Net based on the difference between the provider’s CP-Net and
the selected consumer’s CP-Net.

  3. 3.

Find and select a consumer CP-Net who has the maximum correlation coefficient
with the new CP-Net.

  4. 4.

Create a new CP-Net based on the difference between the consumer CP-Net and
the new CP-Net.

  5. 5.

Perform step 3 and 4 until the difference is zero or minimum.

###  6.2 IaaS Consumer Selection based on Correlation Coefficients

The greedy approach may not always provide the accurate results as it
considers only consumers with maximum correlation with the provider’s CP-Net.
We proposed a heuristic approach where we find those consumers who have
relatively similar CP-Nets with the provider’s CP-Net. Relatively similar CP-
Nets are more likely to form a composition that will match the CP-Nets of the
provider. Two CP-Nets are relatively similar if (1) they have the same
dependency graph (2) Nodes with similar attributes have similar preferences
statements in their CPTs. CP1 and CP5 have the same dependency graph in Figure
1. The relative similarity between two preferences statements is measured
based on their relative ordering. For example, consider two preferences
statements $c1\succ c3\succ c2$ and $c8\succ c10\succ c9$. Although values of
the attributes are different, patterns of both statements are same. We
consider $c1\succ c3\succ c2$ and $c8\succ c10\succ c9$ are relatively
similar. Let us consider two conditional preferences statements $c1\land
m2:p1\succ p2\succ p3$ and $c8\land m10:p6\succ p7\succ p8$. The condition of
the first statement $c1\land m2$ can be fulfilled by the condition of the
second statement $c8\land m10$. A similar statement can be found in the CPT of
the same attribute of the provider’s CP-Net for each statement of the CPT of
an attribute from the consumer’s CP-Net. We perform the following steps to
find the relative similarity between a consumer’s and the provider’s CP-Net:

  1. 1.

Compare the dependency graph of the provider’s and the consumer’s CP-Net. If
the dependency graphs are not the same, the CP-Nets are not similar.

  2. 2.

If the dependency graphs are same, find an unconditional node from provider’s
CP-Net for each unconditional node of the consumer CP-Net.

  3. 3.

Compute similarity between the unconditional nodes selected in step 2.

  4. 4.

Store the similarity measurement in a global variable.

  5. 5.

Find similar conditional nodes for each attribute from provider’s and
consumer’s CP-Nets.

  6. 6.

For each preference statement in a CPT of an attribute of the consumer’s CP-
Net, find a similar preference statement in the CPT of the same attribute of
provider’s CP-Net. The attributes and the conditions of both statements should
be also relatively similar.

  7. 7.

The similarity between the conditional nodes is computed. Update the total
similarity measurement.

Input : $CP_{A}$, $CP_{B}$, $SemanticTable$

Output : Similarity $Sim(CP_{A},CP_{B})$

1

2Integer $commonEdges\leftarrow 0$

3 Integer $allEdges\leftarrow 0$

4 $CPT_{A}\leftarrow$ find all CPT in $CP_{A}$

5 $CPT_{B}\leftarrow$ find all CPT in $CP_{B}$

6

7foreach  _ $X_{i}$ attribute in $CP_{A}$_ do

8 $visitedPreferences\leftarrow\varnothing$

9 foreach  _$P_{A}$ in $CPT_{A}[X_{i}]$_ do

10 boolean $flag\leftarrow false$

11 foreach  _$P_{B}$ in $CPT_{B}[X_{i}]$ _ do

12 if  _$P_{A}$ has similar pattern $P_{B}$ _ then

13 $visitedPreferences\leftarrow P_{B}$

14 $flag\leftarrow true$

15 $commonEdges\leftarrow commonEdges+\prod_{X_{j}\notin
P(X_{i})|SemTable(X_{j})|}$

16 $allEdges\leftarrow allEdges+\prod_{X_{j}\notin P(X_{i})|SemTable(X_{j})|}$

17

18 end if

19 if  _$!flag$_ then

20 $allEdges\leftarrow allEdges+\prod_{X_{j}\notin P(X_{i})|SemTable(X_{j})|}$

21

22 end if

23

24 end foreach

25

26 end foreach

27 foreach  _$P_{B}$ in $CPT_{B}[X_{i}]$_ do

28 if  _$P_{B}\notin visitedPreferences$_ then

29 $allEdges\leftarrow allEdges+\prod_{X_{j}\notin P(X_{i})|SemTable(X_{j})|}$

30

31 end if

32

33 end foreach

34

35 end foreach

36return $Sim(CP_{A},CP_{B})\leftarrow commonEdges/allEdges$

37

Algorithm 1 Similarity Checking between two CP-Nets

We propose Algorithm 1 to find relatively similar consumers based on the
provider’s CP-Nets. Algorithm 1 calculates the coefficient of correlation
between two CP-Nets using equation 2. The algorithm takes two CP-Nets with
same dependency graphs. Two variables are defined to calculate the number of
common edges and all edges between the CP-Nets ($commonEdges$ and $allEdges$).
According to our assumption, both CP-Nets have the same number of attributes.
For each attribute, we perform a check if the conditional preferences from
both CP-Nets have a similar pattern. When a preference has a similar pattern
in both CP-Nets, we update the number of common edges ($commonEdges$) and all
edges ($allEdges$). The preference is added in $visitedPreferences$. However,
if there is no preference from $CP_{A}$ is found, the algorithm updates only
the number of all edges ($allEdges$). $allEdges$ is updated with every
iteration. The relative similarity is calculated by the ratio of the number of
common edges ($commonEdges$) and the number of all edges ($allEdges$).

##  7 Experiments and Results

We have conducted a set of experiments to evaluate the efficiency and the
feasibility of the proposed heuristic based composition approach. The
heuristic and the greedy approaches are compared with the brute force approach
in term of accuracy and time. We conducted the experiment on computers with
Intel Core i7 (3.60GHz and 8GB RAM) using Java and Matlab.

###  7.1 Simulation Setup

It is difficult to find the real-world preferences of IaaS consumers. We have
generated 20 CP-Nets to represent consumers’ preferences. We have also
generated a semantic table for consumers which is a subset of provider’s
semantic table. The provider has the entire view of its resource capacity. As
the simulation has been performed based on randomly generated CP-Nets, the
result varies depending on the type of the CP-Nets. We run the experiment
based on Monte Carlo [3] simulation method for a conclusive result. We have
run the simulation several times for each approach and taken the average
accuracy and time for the different size of consumers. Table 1 shows the
simulation variables and their corresponding values that we have used in the
experiment to perform the performance analysis.

Table 1: Experiment Variables Variable Names | Values
---|---
Simulation Run | 100
Number of Consumers | 2 to 23
Coefficient of Correlation | 0.15, 0.20, 0.25
Homogeneous Domain Size | 20

###  7.2 Baseline: The Brute-force Approach

We generate all combination of the consumers for the brute force approach. For
each combination, we compose them using the composability model. The set of
composable CP-Nets are composed and compared with the provider’s CP-Net using
equation 1. A composed CP-Net that has maximum similarity with the provider’s
CP-Net is selected. As the brute force approach considers all consumers, it
achieves maximum similarity up to 90% with provider’s CP-Net.

(a)  (b)

(c)  (d)

(e)  (f)

Figure 4:  Accuracy of the proposed heuristic approach with Coeffecient (a)
0.15 (b) 0.20 (c) 0.25 (d) Accuracy of the greedy approach (e) Accuracy of the
heuristic and greedy approach (f) Execution time in log scale

###  7.3 Accuracy Analysis

We have applied the proposed heuristic approach to select and compose
relatively similar consumers according to the provider’s CP-Net. The accuracy
of the heuristic approach is calculated with respect to the brute force
approach. We also compose the consumers based on the greedy selection
approach. The accuracy of the greedy approach is calculated in a similar
manner.

The brute force approach normally provides more accurate result then the
heuristic approach as the brute force approach considers all possible
combination of consumers. For the heuristic approach, we select a consumer in
the composition only if its CP-Net is more than 20% relatively similar to the
provider’s CP-Net. We have run the experiments several times to find the
optimal threshold. For a specific provider and a service, this threshold
should be set manually before composition. Figure 4(a), (b), and (c) show the
histogram of the accuracy of the heuristic approach where the correlation
coefficients are 0.15, 0.20, and 0.25. The brute force approach provides the
optimal results. Compared to the brute force result, the heuristic approach
generates almost 60% accurate result on average when the coefficient is 0.2.
Figure 4(d) shows the accuracy result of the greedy based approach. The result
shows the histogram of the outcomes. Here, outcomes have below 50% accuracy
most of the time. Figure 4 (e) shows the average accuracy of the proposed
heuristic approach and the greedy approach. The greedy approach provides very
good accuracy if the number of consumers is low. The accuracy of the greedy
approach becomes low with the increase of consumers, as it starts to discard
more consumers. The heuristic approach provides better accuracy with the
increase in the number of consumers because it finds more similar consumers
according to the provider’s CP-Net.

###  7.4 Runtime Analysis

Figure 4(f) depicts the time comparison between the brute force, heuristic,
and greedy approaches in log scale. The figure shows that with the increase in
the number of consumers, time for composition in the brute force approach
grows exponentially ( i.e., linearly in log scale). The heuristic approach
does not show exponential behavior. For a particular IaaS provider, the
composition time increases very slowly compared to the brute force approach.
The greedy approach shows a very interesting result. It composes consumers
with a constant time for a particular service. The accuracy of the greedy
approach is unreliable.

##  8 Related Work

Qualitative user-preferences are represented by graphical models, especially
in multi-objective decision-making domain [7]. IaaS consumers can express
their preferences more directly, intuitively using qualitative
representations. A conditional preference network (CP-Net) provides a natural
and an efficient way to represent consumers’ preferences in qualitative manner
[5]. CP-Nets are widely used to represent user’s preferences to select and
compose services [18]. A web service selection mechanism is proposed to
incorporate incomplete or inconsistent user preferences from historical
preferences [18]. A CP-Net based similarity measurement approach is proposed
to find users with similar preferences [19]. Several variations of CP-Nets are
also proposed to enhance the expressiveness of users. A UCP-Net is a graphical
representation of utility functions that combines generalize additive models
and CP-Nets [4]. The TCP-Net is another variation of CP-Net where relative
importance between attributes can be captured through weighted edges [15]. The
WCP-Net is another weighted CP-Net that is proposed to capture user’s
preference more precisely to select web services. A deterministic temporal CP-
Net is used to express IaaS provider’s long-term business strategies [11]. A
probabilistic CP-Net is proposed to capture the IaaS provider’s business
strategies in a probabilistic manner [12].

Several existing studies propose different methods to compose multiple CP-
Nets. A multi-agent CP-Net or mCP-Net is proposed as an extension of CP-Net
[16]. Preferences from multiple users are aggregated into a single CP-Net. The
proposed method aggregates preferences according to a voting analogy where
preferences are selected based on the preference of majority user. A Majority-
rule-based preference aggregation method is proposed based on a hypercube-wise
composition to optimize the composition process. An aggregation method is
proposed to capture multi-valued CP-Nets based on majoritarian aggregation
rule [9]. The proposed method can aggregate CP-Nets even if they are cyclic.
Most existing works on the aggregation of CP-Nets consider the composition
problem as a multi-agent voting system. These approaches are not applicable in
the case of resource allocation based on multi-agent preferences. We compose
CP-Nets based on the composability model and the resource constraints in our
proposed composition approach. The composed CP-Nets capture the preferences of
multi-users instead of just considering the common preferences.

##  9 Conclusion

We propose a CP-Net based composition approach for an IaaS provider. The
proposed approach allows the IaaS provider and consumers to express their
qualitative conditional preferences using CP-Nets. We propose a composability
model for IaaS consumers using the semantic congruence property of a
qualitative composition. Finding the optimal composition may be difficult when
the number of consumers is large. A greedy-based and a heuristic-based
selection approaches are proposed to reduce the search space of candidate
consumers. Both approaches utilize correlation coefficients between CP-Nets to
find consumers who have similar preferences with the provider. Experimental
results show that the proposed heuristic-based approach is applicable to the
runtime and the performance is acceptable. One key limitation of the proposed
approach is that it considers only the deterministic model of CP-Nets. In the
future, we want to explore the composability model of probabilistic CP-Nets in
the context of the long-term IaaS composition.

##  10 Acknowledgement

This research was made possible by NPRP 7-481-1-088 grant from the Qatar
National Research Fund (a member of The Qatar Foundation). The statements made
herein are solely the responsibility of the authors.

## References

  * [1] Armbrust, M., Fox, A., Griffith, R., Joseph, A.D., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I., et al.: A view of cloud computing. Communications of the ACM 53(4), 50–58 (2010)
  * [2] Balke, W.T., Wagner, M.: Towards personalized selection of web services. In: WWW (Alternate Paper Tracks). pp. 20–24 (2003)
  * [3] Binder, K., Heermann, D., Roelofs, L., Mallinckrodt, A.J., McKay, S.: Monte carlo simulation in statistical physics. Computers in Physics 7(2), 156–157 (1993)
  * [4] Boutilier, C., Bacchus, F., Brafman, R.I.: Ucp-networks: A directed graphical representation of conditional utilities. In: Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence. pp. 56–64. Morgan Kaufmann Publishers Inc. (2001)
  * [5] Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res.(JAIR) 21, 135–191 (2004)
  * [6] Chaisiri, S., Lee, B.S., Niyato, D.: Optimization of resource provisioning cost in cloud computing. IEEE Transactions on Services Computing 5(2), 164–177 (2012)
  * [7] Lang, J., Xia, L.: Sequential composition of voting rules in multi-issue domains. Mathematical social sciences 57(3), 304–324 (2009)
  * [8] Li, L., Liu, D., Bouguettaya, A.: Semantic based aspect-oriented programming for context-aware web service composition. Information Systems 36(3), 551–564 (2011)
  * [9] Li, M., Vo, Q.B., Kowalczyk, R.: Aggregating multi-valued cp-nets: a csp-based approach. Journal of Heuristics 21(1), 107–140 (2015)
  * [10] Liu, X., Bouguettaya, A., Wu, J., Zhou, L.: Ev-lcs: A system for the evolution of long-term composed services. IEEE Transactions on Services Computing 6(1), 102–115 (2013)
  * [11] Mistry, S., Bouguettaya, A., Dong, H., Erradi, A.: Qualitative economic model for long-term iaas composition. In: International Conference on Service-Oriented Computing. pp. 317–332. Springer (2016)
  * [12] Mistry, S., Bouguettaya, A., Dong, H., Erradi, A.: Probabilistic qualitative preference matching in long-term iaas composition. In: International Conference on Service-Oriented Computing. pp. 256–271. Springer (2017)
  * [13] Mistry, S., Bouguettaya, A., Dong, H., Qin, A.K.: Predicting dynamic requests behavior in long-term iaas service composition. In: ICWS. pp. 49–56. IEEE (2015)
  * [14] Mistry, S., Bouguettaya, A., Dong, H., Qin, A.: Metaheuristic optimization for long-term iaas service composition. IEEE Transactions on Services Computing (2017)
  * [15] Mukhtar, H., Belaïd, D., Bernard, G.: A quantitative model for user preferences based on qualitative specifications. In: ICPS. pp. 179–188. ACM (2009)
  * [16] Rossi, F., Venable, K.B., Walsh, T.: mcp nets: representing and reasoning with preferences of multiple agents. In: AAAI. vol. 4, pp. 729–734 (2004)
  * [17] Wang, H., Shao, S., Zhou, X., Wan, C., Bouguettaya, A.: Web service selection with incomplete or inconsistent user preferences. In: International Conference on Service-Oriented Computing, pp. 83–98. Springer (2009)
  * [18] Wang, H., Tao, Y., Yu, Q., Lin, X., Hong, T.: Incorporating both qualitative and quantitative preferences for service recommendation. Journal of Parallel and Distributed Computing (2017)
  * [19] Wang, H., Wang, H., Guo, G., Tang, Y., Zhang, J.: Measuring similarity of users with qualitative preferences for service selection. Knowledge and Information Systems 51(2), 561–594 (2017)
  * [20] Ye, Z., Bouguettaya, A., Zhou, X.: Qos-aware cloud service composition based on economic models. In: International Conference on Service-Oriented Computing. pp. 111–126. Springer (2012)
  * [21] Ye, Z., Mistry, S., Bouguettaya, A., Dong, H.: Long-term qos-aware cloud service composition using multivariate time series analysis. IEEE Transactions on Services Computing 9(3), 382–393 (2016)


Probing up-down quark matter via gravitational waves
Chen Zhang

Department of Physics, University of Toronto, 60 St. George Street, Toronto, Ontario, Canada M5S 1A7

Recently, it was shown that quark matter with only $u$ and $d$ quarks ($ud$QM) can be the ground state of matter for baryon numbers $A>A_\textrm{min}$ with $A_{\rm min}\gtrsim 300$. In this paper, we explore $ud$ quark stars ($ud$QSs) that are composed of $ud$QM, in the context of the two-families scenario in which $ud$QSs and hadronic stars (HSs) can coexist. Distinct signatures are discussed compared to the conventional study regarding strange quark stars (SQSs). We show that the requirements of $A_{\rm min}\gtrsim 300$ and the most massive compact star observed being a $ud$QS together may put stringent constraints on the allowed parameter space of $ud$QSs. Then, we study the related gravitational-wave probe of the tidal deformability in binary star mergers, including the $ud$QS-$ud$QS and $ud$QS-HS cases. The obtained values of the tidal deformability at 1.4 solar masses and the average tidal deformability are all in good compatibility with the experimental constraints of GW170817. This study points to a new possible interpretation of the GW170817 binary merger event, where $ud$QS may be at least one component of the binary system detected.

§ INTRODUCTION

In the conventional picture of nuclear physics, quarks are confined in the state of hadrons. However, it is also possible that quark matter, a state consisting of deconfined quarks, exists. Bodmer [1], Witten [2] and Terazawa [4] proposed the hypothesis that quark matter with comparable numbers of $u$, $d$, and $s$ quarks, also called strange quark matter (SQM), might be the ground state of baryonic matter. However, this hypothesis is based on the bag model that cannot adequately model the flavor-dependent feedback of the quark gas on the QCD vacuum. Improved models have shown that quark matter with only $u$, and $d$ quarks ($ud$QM) is more stable than SQM [5, 6, 7, 8], but with the common conclusion that neither is more stable than ordinary nuclei. In a recent study [7], with a phenomenological quark-meson model that can give good fits to all the masses and decay widths of the light meson nonets and can account for the flavor-dependent feedback [9, 10], the authors demonstrated that $ud$QM can be more stable than the ordinary nuclear matter and SQM when the baryon number $A$ is sufficiently large above $A_{\rm min}\gtrsim 300$. The absolute stability of $ud$QM is tested to be robust within $10\%$ departures of the experimental data.
The large $A_{\rm min}$ ensures the stability of ordinary nuclei in the periodic table, which also results in a large positive charge. Recently, a collider search for such high-electric-charge objects was attempted using LHC data [11].

One can also look for the evidence of $ud$QM from gravitational-wave detection experiments. The binary merger of compact stars produces strong gravitational wave fields, the waveforms of which encode the information of the tidal deformation that is sensitive to the matter equation of state (EOS). In general, stars with stiff EOSs can be tidally deformed easily due to their large radii.

The GW170817 event detected by LIGO [12] is the first confirmed merger event of compact stars. Together with the subsequent detection of the electromagnetic counterpart, GRB 170817A and  AT2017gfo [13], they inspired a lot of studies that greatly move our understanding of nuclear matter forward [14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 21]. The initial analysis [12] determines the chirp mass of the binary to be $M_c = 1.188\,\ms$. For the low-spin case, the binary mass ratio $q=M_2/M_1$ is constrained to the range $q=$0.7–1.0. Upper bounds have been placed on the tidal deformability at 1.4 solar masses $ \Lambda (1.4\, \ms) \lesssim 800$, and on the average tidal deformability $ \tilde{\Lambda} \leq 800$ at a $90\%$ confidence level. Later, an improved LIGO analysis [28] gives $M_c=1.186^{+0.001}_{-0.001} \, M_{\odot}$, and a $90\%$ highest posterior density interval of $ \tilde{\Lambda}=300^{+420}_{-230}$ with $q=$0.73–1.00 for the low-spin prior. Lower bounds have been placed from AT2017gfo with kilonova models [15, 17, 16]. However, to the author's knowledge, the more strict lower bounds obtained in such analysis, including $\Lambda (1.4\, \ms) \gtrsim 200$ [16] and  $\tilde{\Lambda} \gtrsim 242$ [17], are all assuming the neutron star EOS. Therefore, we will not use them to constrain our study of quark stars here.

Conventionally, binary mergers are studied in the one-family scenario where it is assumed that all compact stars are within one family of hadronic matter EOSs [12, 18, 19, 20, 22]. However, the discovery of pulsars with large masses above $2\, M_\odot$  [29, 30, 31] ruled out a large number of soft EOSs that were expected with the presence of hyperons and $\Delta$ resonances in the interiors. Therefore, it is natural to expect that the stars with masses above $2\, M_\odot$ and large radii are actually quark stars (QSs), and most of the ones with small masses and small radii are the hadronic stars (HSs). This possibility is the so-called “two-families" scenario, which is based on the hypothesis that absolutely stable quark matter (either SQM or $ud$QM) exists, and that the hadronic stars can coexist with quark stars [32].  The binary merger in the two-families scenario includes three cases: HS-HS [21], HS-QS [22], and QS-QS [33]. Alternatively, dropping the hypothesis that quark matter is the ground state gives the twin-stars scenario [22, 26, 27], where quark matter only appears in the interiors of hybrid stars.

Several things make $ud$ quark stars ($ud$QSs), which are composed of $ud$QM, very distinct compared to the strange quark stars (SQSs) that are composed of SQM. First, $ud$QSs can satisfy the $2\, M_\odot$ constraint more easily than HSs and SQSs [7, 34] due to the nonhyperonic composition and the small effective bag constant.  Second, the coexistence of HSs and QSs requires that the conversion of hadronic matter to quark matter be neither too fast nor too slow compared to the age of our Universe. In contrast to the coexistence study for SQSs, where the conversion requires the presence of hyperons which only emerge above 1.5 solar masses, the conversion regarding $ud$QSs can happen at a smaller mass range since no hyperonic composition is needed. Therefore, it is possible that $ud$QSs can coexist with HSs even at the small mass range below $1.5 \, M_{\odot}$. This reasoning raises the possibility for GW170817 being a $ud$QS-$ud$QS merger or a $ud$QS-HS merger despite the smallness of the chirp mass $1.186 \, M_{\odot}$ and the high mass ratio $q=$0.73–1.00. Besides, the possibility of the QS-QS case is sometimes disfavored for GW170817/AT2017gfo because of the kilonova observation of nuclear radioactive decay [35]. However, it is possible that the $ud$QM ejected is quickly destabilized by the finite-size effects and converts into ordinary or heavy nuclei. The conversion is far more rapid for $ud$QM than for SQM, due to a much larger $A_{\rm min}$ and the nonstrange composition, so that there is no need to involve extra weak interactions to convert away strangeness. Note that the radii constraints derived from GW170817 are mostly for hadronic EOSs in the context of the one-family scenario [18, 19, 20], so that they have not much relevance to the $ud$QSs in the two-families scenario we are discussing here.

Motivated by these considerations, we explore the properties of $ud$QSs and the related gravitational-wave probe in the two-families scenario, including the binary merger cases $ud$QS-$ud$QS and $ud$QS-HS. We will discuss the related compatibility and constraints from GW170817. Note that we ignore the discussion of the HS-HS case since this possibility is not directly related to the study of quark stars and is disfavored to some extent for GW170817 based on the consideration of prompt collapse [21].

§ PROPERTIES OF $UD$QSS

The EOS of $ud$QM can be well approximated by the simple form $p=1/3\,(\rho-\rho_s)$, where $\rho_s$ is the finite density at the surface. For the EOS of SQM, the coefficient $1/3$ is modified by the strange quark mass effect, with the $\rho_s$ value also being different. In the region of interest for $ud$QM, we can take the relativistic limit where the energy per baryon number in the bulk limit takes the form $E/A=\rho/n_A\approx (\chi N_C p_F^4/4\pi^2+B_{\rm eff})/n_A =3/4\, N_C p_F \chi+3\pi^2 B_{\rm eff}/p_F^3$ [7], where $N_C=3$ is the color factor and $\chi=\sum_i f_i^{4/3}$ is the flavor factor, with the fraction $f_u=1/3=1/2\,f_d$ for $ud$QM. The effective Fermi momentum is $p_F=(3\pi^2 n_A)^{1/3}$. $B_{\rm eff}$ is the effective bag constant that accounts for the QCD vacuum contribution. Note that in this $ud$QM study, we can approximate $B_{\rm eff}$ as an effective constant since its dependence on flavor and density only causes a substantial effect when strangeness turns on at very large density [7, 5, 6]. Minimizing the energy per baryon number with respect to $p_F$ for fixed flavor composition gives
E/A=3√(2π)(χ^3 B_eff)^1/4,

at which $p=0$, $\rho=\rho_s=4 B_{\rm eff}$. Equation (<ref>) matches the exact numerical result of the phenomenological meson model [7] extremely well, with a mere error $\sim0.3\%$ due to a tiny $u$ $(d)$ quark mass. It was shown in Refs. [7, 5, 6] that $B_{\rm eff}$ has a smaller value in the two-flavor case than in the three-flavor case, so that $ud$QM is more stable than $\rm SQM$ in the bulk limit. Absolute stability of $ud$QM in the bulk limit implies $ E/A\lesssim 930 \,\rm MeV$, which corresponds to
B_eff≲56.8   MeV/fm^3

from Eq. (<ref>). In general, a larger $E/A$ or $B_{\rm eff}$ gives a larger $A_{\rm min}$. The stability of ordinary nuclei against $ud$QM requires $A_{\rm min}\gtrsim300$, which translates to $E/A \gtrsim 903 \, \rm MeV$ or
B_eff≳50   MeV/fm^3

for the quark-meson model that matches the low-energy phenomenology [7]. This quark-meson model also results in a quark-vacuum surface tension $\sigma\approx (91\,\rm MeV)^3$ that is robust against parameter variations.

The linear feature of $ud$QM EOS makes it possible to perform a dimensionless rescaling on parameters [36, 37]
ρ̅=ρ/4 B_eff,    p̅=p/4 B_eff,      r̅=r√(4 B_eff),    m̅=m√(4 B_eff),

which enter the Tolman–Oppenheimer–Volkoff (TOV) equation [39, 38]

dp(r)dr   =-[m(r)+4πr^3p(r)][ρ(r)+p(r)]r(r-2m(r)) ,

dm(r)dr   =4πρ(r)r^2,

so that the rescaled solution is also dimensionless, and thus is independent of any specific value of $B_{\rm eff}$. The TOV solution with a specific $B_{\rm eff}$ value can be obtained directly from rescaling the dimensionless solution back with Eq. (<ref>). Solving the rescaled TOV equation with the $ud$QM EOS gives the dimensionless result shown in Fig. <ref>, with the maximum rescaled mass at $(\bar{M},\bar{R})= (M{\sqrt{4\,B_{\rm eff}}},R{\sqrt{4\,B_{\rm eff}}})=(0.0517, 0.191),$ mapping to $M_{\rm max}\approx 15.174/\sqrt{B_{\rm eff}} \,\,M_\odot$, $R_{\rm M\,max}\approx 82.79/\sqrt{B_{\rm eff}}  \rm\, \, km$. Therefore, the requirement that $ud$QSs have a maximum mass not smaller than the recently observed most massive compact star J0740+6620 ($M\approx 2.14^{+0.10}_{-0.09}\,M_{\odot}$) [31] implies
B_eff≲50.3^+4.5_-4.4 MeV/fm^3,

which constrains more strictly than what Eq. (<ref>) imposes. Interestingly, the central value of the upper bound Eq. (<ref>) is very close to the lower bound Eq. (<ref>) at the critical value $B_{c}\approx\rm  50\, MeV/fm^3$. To be more conservative, we can take 10% departures, considering the theoretical and experimental uncertainties [40, 41, 42, 43, 44, 45, 46, 31], so that the allowed window of $B_{\rm eff}$ for $ud$QS is

{ B_ udQS }    ≈[45 ,  55]   MeV/fm^3

with the central value $B_{c}\approx 50 \rm\, MeV/fm^3$. The corresponding $M$-$R$ solution is shown in Fig. <ref>.

$\bar{M}$-$\bar{R}$ of $ud$QSs. The black dot at $(\bar{M},\bar{R})$= $(0.0517, 0.191)$ denotes the maximum mass configuration.

$M$-$R$ of $ud$QSs. Lines with darker color denote a larger effective bag constant $B_{\rm eff}$ and sample $(45, 50, 55)\rm\, MeV/fm^3$ respectively. The black dots denote the maximum mass location.

Note that some SQS studies [22, 33, 47] exploited similar small $B_{\rm eff}$ values to have maximum masses above $2 \,M_{\odot}$, but the smallness is not natural considering the appearance of strangeness, and a large perturbative QCD (pQCD) effect or a color superconducting phase has to be included to guarantee the stability.

The response of compact stars to external disturbance is characterized by the Love number $k_2$ [48, 49, 50, 51],

k_2    = 8 C^5/5 (1-2C)^2 [ 2 + 2 C (y_R-1) -y_R ]

×{ 2 C [ 6- 3y_R + 3C (5y_R-8)]+4C^3[ 13-11 y_R
+ C (3y_R-2)+2C^2(1+y_R)]

+ 3 (1-2C)^2 [ 2 - y_R + 2C (y_R-1)] log(1-2C )}^-1 .

Here $C=M/R=C(\bar{M})$. And $y_R$ is $y(r)$ evaluated at the surface, which can be obtained by solving the following equation [51]:

ry^'(r)+y(r)^2+ r^2Q(r)

+y(r)e^λ(r)[1+4πr^2(p(r)-ρ(r))]=0 ,

with the boundary condition $y(0)=2$. Here

Q(r)   =4πe^λ(r) (5ρ(r)+9p(r)+ρ(r)+p(r)/c_s^2(r))

\begin{equation}
e^{\lambda(r)}=\left[1-{2m(r)\over r}\right]^{-1}\,\,,\,
\nu^\prime(r)=2e^{\lambda(r)}{m(r)+4\pi p(r)r^3\over r^2}.
\label{eq:met}
\end{equation}

$c_s^2(r)\equiv dp/d\rho$ denotes the sound speed squared.
For stars with a finite surface density like quark stars, a matching condition should be used at the boundary $y_R^{\rm ext}=y_R^{\rm int}-  4\pi R^3\rho_s/M$ [52]. Solving Eq. (<ref>) with the $\rho(r)$ and $p(r)$ obtained from Eq. (<ref>), one obtains the function $k_2(C)$. The dimensionless tidal deformability $\Lambda=2k_2/(3C^5)$ as a function of mass $\bar{M}$ is thus obtained accordingly.
The result is shown in Fig. <ref>.

The tidal deformability $\Lambda$ vs the rescaled star mass $\bar{M}$ for $ud$QSs. For $\bar{M}$ with $M=1.4 M_{\odot}$, the red band represents the region with $B_{\rm eff} \in \{ B_{ud\rm QS} \}$, and the red dashed line shows $B_{\rm eff} = B_{\rm c}$. The blue band denotes the GW170817 constraints on $\Lambda(1.4 \, M_{\odot})$ [12].

We see from Fig. <ref> that for $M=1.4\,M_\odot$ and $B_{\rm eff}\in \{ B_{ud\rm QS} \}$, one has $\bar{M}=M\sqrt{4\,B_{\rm eff}}\in [0.032, 0.035]$, as the red band in Fig. <ref> represents. Mapping this range to Fig. <ref> gives $\Lambda(1.4 \, M_\odot)\in [530, 857]$. And  $\Lambda(1.4\,M_\odot)\approx 670$ for $B_{\rm eff}=B_c$. We see that these results are well compatible with the GW170817 constraint $ \Lambda(1.4\,M_\odot)\lesssim 800$ [12]. In particular, the point where $\Lambda(1.4M_\odot)$ reaches the upper bound $\Lambda(1.4\,M_\odot)\sim 800$ sets a more stringent lower bound that $B_{ud\rm QS}\gtrsim47.9 \, \rm MeV/fm^3$. We also see that the result is not sensitive to the possible uncertainties related to the lower bound of $\Lambda(1.4\,M_\odot)$ constraint.

§ BINARY MERGER IN THE TWO-FAMILIES SCENARIO

The average tidal deformability of a binary system is defined as
Λ̃   =    16/13
(1+12q)/(1+q)^5 Λ (M_1)+ 16/13  q^4 (12+q)/(1+q)^5Λ(M_2),

where $M_1$ and $M_2$ are the masses of the binary components. And $q=M_2/M_1$, with $M_2$ being the smaller mass so that $0<q\leq1$. Then for any given chirp mass  $M_{c} = (M_1 M_2)^{3/5}/(M_1+M_2)^{1/5}$, one has
$M_2=(q^2(q+1))^{1/5} M_c \text{ and } M_1=((1+q)/q^3)^{1/5} M_c$.

§.§ $ud$QS-$ud$QS merger

In this case, the average tidal deformability can be expressed as a function of the rescaled mass parameter $\bar{M}=M\sqrt{4 B_{\rm eff}}$:

\begin{equation}
\tilde \Lambda= \frac{16}{13}
\frac{ (1+12q)}{(1+q)^5} \Lambda (\bar{M}_1) + \frac{16}{13}  \frac{q^4 (12+q)}{(1+q)^5} \Lambda(\bar{M}_2).
\label{eq:LambdaQdim}
\end{equation}

Substituting the $\Lambda(\bar{M})$ obtained previously into the formula above, we get the results shown in Fig. <ref>.

The average tidal deformability $\tilde{\Lambda}$ vs the rescaled chirp mass $\bar{M}_c$ for the $ud$QS-$ud$QS merger case. Black curves show results with $q=M_2/M_1=(0.1, 0.2, 0.3,0.4, 0.5, 0.7, 1)$ from left to right, respectively. For the GW170817 event in which $M_c=1.186 \, M_\odot$, the red band represents the region of $\bar{M}_c$ with $B_{\rm eff}  \in \{ B_{ud\rm QS} \}$, and the red dashed line is with $B_{\rm eff}=B_{\rm c} $. The blue band is the GW170817 constraint on $\tilde{\Lambda}$ [28].

Note that in this figure, the lower end of each curve is determined by requiring each component of the binary system not to exceed its maximum mass. The $\bar{M}_c$ value of each end is negatively correlated with the $q$ value,  since for a given $M_c$, a less symmetric system has a larger component mass, which can exceed their maximum mass more easily.
The general shape of the figure matches our qualitative expectation. For given $\bar{M}_c$, a smaller mass ratio $q$ maps to a smaller $\tilde{\Lambda}$. Besides, for given $q$, a larger rescaled mass $\bar{M}_c=M_c \sqrt{4 B_{\rm eff}}$ corresponds to a smaller  $\tilde{\Lambda}$. These features are all due to the general fact that quark stars with larger masses have larger compactness, and thus are less likely to be tidally deformed.

As Fig. <ref> shows, for GW170817 in which $M_c=1.186 \,M_\odot$, the constraint $\tilde{\Lambda}=300^{+420}_{-230}$ [28] translates to $0.4\lesssim q\lesssim 1$ for $B_{\rm eff} \in \{B_{ud\rm QS}\}$, and especially to $q=0.74$ for $B_{\rm eff} =B_c=50 \, \rm \, MeV/fm^3$, all of which are compatible with the GW170817 constraint $q=$0.73–1.00 [12].  We see that $q\gtrsim 0.73$ and $\tilde{\Lambda}\lesssim720$ set a more stringent lower bound that $B_{ud\rm QS}\gtrsim 49.5\,\rm MeV/fm^3$. We also see that $B_{ud\rm QS}$ is not constrained much by the lower bound of $\tilde{\Lambda}$.

§.§ $ud$QS-HS merger

For the $ud$QS-HS merger case, we need the information of the hadronic matter EOS, which has large uncertainties in the intermediate-density region. Based on nuclear physics alone, the EOS should match the low-density many-body calculation and high-density pQCD result [53]. Here we use three benchmarks of hadron matter EOSs—SLy [54, 55], Bsk19, and Bsk21 [56]— that have unified representations from low density to high density.  Bsk19 is an example of soft EOSs. HSs with Bsk19 have maximum mass $M_{\rm max}=1.86\, M_\odot< 2 \,M_\odot$ and $R_{1.4 \,M_\odot}=10.74\rm\,km<11 \rm \,km$. The feature of small masses and small radii is preferred for the typical HSs branch of the two-families scenario. For illustration, we also show benchmarks of a hard EOS (Bsk21) with $M_{\rm max}=2.27 \,M_\odot$, $R_{1.4 \,M_\odot}=12.57\rm\,km$, and a moderate one (SLy) with $M_{\rm max}=2.05 \,M_\odot$, $R_{1.4 M_\odot}=11.3\rm\,km$. With Eq. (<ref>), the $\Lambda(M)$ results of $ud$QS, and the HS EOS benchmarks, we obtain the average tidal deformability  $\tilde{\Lambda}$ of the $ud$QS-HS system, as shown in Fig. <ref>.

The average tidal deformability $\tilde{\Lambda}$ vs $q=M_2/ M_1$ for the $ud$QS-HS merger case, with $M_2$ being the mass of the hadronic star and $M_{c}=1.186 \,M_{\odot}$ for the GW170817 event. For HS EOSs, SLy (blue), Bsk19 (red), and Bsk21 (black) are used. For $ud$QS EOSs, lines with darker color denote with larger $B_{\rm eff}$, sampling $(45, 50, 55){\rm\, MeV/fm^3}\in \{ B_{ud\rm QS} \}$, respectively. The blue band and gray band are the GW170817 constraints on $\tilde{\Lambda}$ and $q$, respectively [28].

We see from Fig. <ref> that the order of $\tilde{\Lambda}$ for different HS EOSs matches the expectation from the general rule that a HS with a stiffer EOS or a QS with a smaller effective bag constant has a larger radius, and thus has larger deformability. Lines with different hadronic EOSs tend to merge at lower $q$ as $\tilde{\Lambda}$ gets dominated by the contribution of large-mass quark stars. We see a good compatibility with current GW170817 constraint $\tilde{\Lambda}=300^{+420}_{-230}$ when $q=$0.73–1.00, except for an exclusion of the stiffest hadronic EOS (Bsk21).

§ CONCLUSIONS

We have discussed the distinct properties that make $ud$QSs good candidates for the two-families scenario in which hadronic stars can coexist with quark stars. We have shown that the requirements of $A_{\rm min}\gtrsim 300$ and $M_{\rm max}\gtrsim 2.14 \, M_{\odot}$ together stringently constrain the effective bag constant of $ud$QSs to $B_{\rm eff} \approx  50 \rm  \, MeV/fm^3$. A $10\%$ relaxation that accounts for the possible uncertainties gives the conservative range $B_{ud\rm QS}  \in [45 , \,55] \rm \, MeV/fm^3$. Then we studied the related gravitational-wave probe of tidal deformability of binary star mergers including the $ud$QS-$ud$QS and $ud$QS-HS cases. For the $ud$QS-$ud$QS case, the upper bound of tidal deformability and the binary mass ratio of GW170817 further confine the allowed parameter space to $B_{ud\rm QS}  \in [49.5 , \,55] \rm \, MeV/fm^3$. Also, with the dimensionless rescaling method used, the analysis can be straightforwardly generalized to an arbitrary binary chirp mass and effective bag constant for current and future gravitational-wave events. The $ud$QS-HS case is also well compatible with the GW170817 constraints. These point to a new possibility that GW170817 can be identified as either a $ud$QS-$ud$QS merger or a $ud$QS-HS merger event.

This research is supported in part by the Natural Sciences and Engineering Research Council of Canada. I thank Bob Holdom, Jing Ren, and Luciano Rezzolla for helpful discussions. I also thank Randy S. Conklin and Shenglin Jing for proofreading the article.

Note Added: As we were finalizing this paper, we became aware of the recent Ref. [57]. With a special version of the NJL model, Ref. [57] has some discussions on the $\Lambda(1.4M_\odot)$ of nonstrange quark stars for the low-spin case of GW170817, and the authors also found that $\Lambda(1.4M_\odot)$ can match the experimental constraints in a certain parameter space. However, they neglected the study of the two-families scenario and the corresponding average tidal deformability $\tilde{\Lambda}$. Also, they only explored the parameter space in which $ud$QM is more stable than SQM, with the parameter space where $ud$QM is even more stable than nuclear matter remaining uncertain in their model.

[1]
A. R. Bodmer,

Phys. Rev. D 4, 1601 (1971).

[2]

E. Witten,

Phys. Rev. D 30, 272 (1984).

[4]
H. Terazawa,

INS-Report-336 (INS, University of Tokyo, Tokyo) May, 1979.

[5]
M. Buballa and M. Oertel,

Phys. Lett. B 457, 261 (1999)

[6]
P. Wang, V. E. Lyubovitskij, T. Gutsche and A. Faessler,

Phys. Rev. C 67, 015210 (2003)

[7]
Bob Holdom, Jing Ren and Chen Zhang,

Phys. Rev. Lett.  120, no. 22, 222001 (2018)

[arXiv:1707.06610 [hep-ph]].

[8]
Q. Wang, T. Zhao and H. S. Zong,

arXiv:1908.01325 [hep-ph].

[9]
A. A. Osipov, B. Hiller and A. H. Blin,

Phys. Rev. D 88, 054032 (2013)

[arXiv:1309.2497 [hep-ph]].

[10]
J. Moreira, J. Morais, B. Hiller, A. A. Osipov and A. H. Blin,

Phys. Rev. D 98, no. 7, 074010 (2018)

[arXiv:1806.00327 [hep-ph]].

[11]
G. Aad et al. [ATLAS Collaboration],

Phys. Rev. Lett.  124, no. 3, 031802 (2020)

[arXiv:1905.10130 [hep-ex]].

[12]
B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations],

Phys. Rev. Lett.  119, no. 16, 161101 (2017)

[arXiv:1710.05832 [gr-qc]].

[13]
Abbott, B. P., et al. 2017b, Astrophys. J., 848, L13; —. 2017c, Astrophys. J., 848, L12

[14]
B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations],

Phys. Rev. Lett.  121, no. 16, 161101 (2018)

[arXiv:1805.11581 [gr-qc]].

[15]
D. Radice, A. Perego, F. Zappa and S. Bernuzzi,

Astrophys. J.  852, no. 2, L29 (2018)

[arXiv:1711.03647 [astro-ph.HE]].

[16]
A. Bauswein et al.,

AIP Conf. Proc.  2127, no. 1, 020013 (2019)

[arXiv:1904.01306 [astro-ph.HE]].

[17]
K. Kiuchi, K. Kyutoku, M. Shibata and K. Taniguchi

Astrophys. J.  bf 876, no. 2, L31 (2019)

[arXiv:1903.01466 [astro-ph.HE]].

[18]
E. Annala, T. Gorda, A. Kurkela and A. Vuorinen,

Phys. Rev. Lett.  120, no. 17, 172703 (2018)

[arXiv:1711.02644 [astro-ph.HE]].

[19]
F. J. Fattoyev, J. Piekarewicz and C. J. Horowitz,

Phys. Rev. Lett.  120, no. 17, 172702 (2018)

[arXiv:1711.06615 [nucl-th]].

[20]
S. De, D. Finstad, J. M. Lattimer, D. A. Brown, E. Berger and C. M. Biwer,

Phys. Rev. Lett.  121, no. 9, 091102 (2018)
Erratum: [Phys. Rev. Lett.  121, no. 25, 259902 (2018)]

[arXiv:1804.08583 [astro-ph.HE]].

[21]
A. Drago and G. Pagliara,

Astrophys. J.  852, no. 2, L32 (2018)

[arXiv:1710.02003 [astro-ph.HE]].

[22]
G. F. Burgio, A. Drago, G. Pagliara, H. J. Schulze and J. B. Wei,

Astrophys. J.  860, no. 2, 139 (2018)

[arXiv:1803.09696 [astro-ph.HE]].

[23]
E. R. Most, L. R. Weih, L. Rezzolla and J. Schaffner-Bielich,

Phys. Rev. Lett.  120, no. 26, 261103 (2018)

[arXiv:1803.00549 [gr-qc]].

[24]
E. R. Most, L. J. Papenfort, V. Dexheimer, M. Hanauske, S. Schramm, H. Stöcker, and L. Rezzolla,

Phys. Rev. Lett.  122, no. 6, 061101 (2019)

[arXiv:1807.03684 [astro-ph.HE]].

[25]
L. R. Weih, E. R. Most and L. Rezzolla,

Astrophys. J.  881, 73 (2019)

[arXiv:1905.04900 [astro-ph.HE]].

[26]
G. Montana, L. Tolos, M. Hanauske and L. Rezzolla,

Phys. Rev. D 99, no. 10, 103009 (2019)

[arXiv:1811.10929 [astro-ph.HE]].

[27]
V. Dexheimer, L. T. T. Soethe, J. Roark, R. O. Gomes, S. O. Kepler and S. Schramm,

Int. J. Mod. Phys. E 27, no. 11, 1830008 (2018)

[arXiv:1901.03252 [astro-ph.HE]].

[28]
B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations],

Phys. Rev. X 9, no. 1, 011001 (2019)

[arXiv:1805.11579 [gr-qc]].

[29]
P. Demorest, T. Pennucci, S. Ransom, M. Roberts and J. Hessels,

Nature 467, 1081 (2010)

[arXiv:1010.5788 [astro-ph.HE]].

[30]
J. Antoniadis et al.,

Science 340, 6131 (2013)

[arXiv:1304.6875 [astro-ph.HE]].

[31]
H. T. Cromartie et al.,

arXiv:1904.06759 [astro-ph.HE].

[32]
A. Drago, A. Lavagno and G. Pagliara,

Phys. Rev. D 89, no. 4, 043014 (2014)

[arXiv:1309.7263 [nucl-th]].

[33]
E. P. Zhou, X. Zhou and A. Li,

Phys. Rev. D 97, no. 8, 083015 (2018)

[arXiv:1711.04312 [astro-ph.HE]].

[34]
T. Zhao, W. Zheng, F. Wang, C. M. Li, Y. Yan, Y. F. Huang and H. S. Zong,

Phys. Rev. D 100, no. 4, 043018 (2019)

[arXiv:1904.09744 [nucl-th]].

[35]
A. Drago, G. Pagliara, S. B. Popov, S. Traversi and G. Wiktorowicz,

Universe 4, no. 3, 50 (2018)

[arXiv:1802.02495 [astro-ph.HE]].

[36]
J. L. Zdunik,

Astron. Astrophys.  359, 311 (2000)

[37]
P. Haensel, A. Y. Potekhin and D. G. Yakovlev,

Astrophys. Space Sci. Libr.  326, pp.1 (2007).

[38]
R. C. Tolman,

Phys. Rev.  55, 364 (1939).

[39]
J. R. Oppenheimer and G. M. Volkoff,

Phys. Rev.  55, 374 (1939).

[40]
M. S. Berger and R. L. Jaffe,

Phys. Rev. C 35, 213 (1987).

[41]
G. Lugones, A. G. Grunfeld and M.A. Ajmi,

Phys. Rev. C 88, no. 4, 045803 (2013)

[arXiv:1308.1452 [hep-ph]].

[42]
W. y. Ke and Y. x. Liu,

Phys. Rev. D 89, no. 7, 074041 (2014)

[arXiv:1312.2295 [hep-ph]].

[43]
A. F. Garcia and M. B. Pinto,

Phys. Rev. C 88, no. 2, 025207 (2013)

[arXiv:1306.3090 [hep-ph]].
[44]
L. F. Palhares and E. S. Fraga,

Phys. Rev. D 82, 125018 (2010)

[arXiv:1006.2357 [hep-ph]].

[45]
M. B. Pinto, V. Koch and J. Randrup,

Phys. Rev. C 86, 025203 (2012)

[arXiv:1207.5186 [hep-ph]].

[46]
E. S. Fraga, M. Hippert and A. Schmitt,

Phys. Rev. D 99, no. 1, 014046 (2019)

[arXiv:1810.13226 [hep-ph]].

[47]
S. Weissenborn, I. Sagert, G. Pagliara, M. Hempel and J. Schaffner-Bielich,

Astrophys. J.  740, L14 (2011)

[arXiv:1102.2869 [astro-ph.HE]].

[48] A. E. H. Love, Proc. R. Soc. A 82, 73 (1909).
[49]
T. Hinderer,

Astrophys. J.  677, 1216 (2008)

[arXiv:0711.2420 [astro-ph]].

[50]
T. Hinderer, B. D. Lackey, R. N. Lang and J. S. Read,

Phys. Rev. D 81, 123016 (2010)

[arXiv:0911.3535 [astro-ph.HE]].

[51]
S. Postnikov, M. Prakash and J. M. Lattimer,

Phys. Rev. D 82, 024016 (2010)

[arXiv:1004.5098 [astro-ph.SR]].

[52]
T. Damour and A. Nagar,

Phys. Rev. D 80, 084035 (2009)

[arXiv:0906.0096 [gr-qc]].

[53]
E. L. Oter, A. Windisch, F. J. Llanes-Estrada and M. Alford,

J. Phys. G 46, no. 8, 084001 (2019)

[arXiv:1901.05271 [gr-qc]].

[54]
F. Douchin and P. Haensel,

Astron. Astrophys.  380, 151 (2001)

[55]
P. Haensel and A. Y. Potekhin,

Astron. Astrophys.  428, 191 (2004)

[56]
A. Y. Potekhin, A. F. Fantina, N. Chamel, J. M. Pearson and S. Goriely,

Astron. Astrophys.  560, A48 (2013)

[arXiv:1310.0049 [astro-ph.SR]].

[57]
Q. Wang, C. Shi and H. S. Zong,

Phys. Rev. D 100, no. 12, 123003 (2019)
Erratum: [Phys. Rev. D 100, no. 12, 129903 (2019)]

[arXiv:1908.06558 [hep-ph]].