# A new lower bound for doubly metric dimension and related extremal
differences

Jozef Kratica 11footnotemark: 1<EMAIL_ADDRESS>Vera Kovačević-Vujčić
22footnotemark: 2<EMAIL_ADDRESS>Mirjana Čangalović
33footnotemark: 3<EMAIL_ADDRESS>Mathematical
Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36/III, 11 000
Belgrade, Serbia  Faculty of Organizational Sciences, University of Belgrade,
Jove Ilića 154, 11000 Belgrade, Serbia

###### Abstract

In this paper a new graph invariant based on the minimal hitting set problem
is introduced. It is shown that it represents a tight lower bound for the
doubly metric dimension of a graph. Exact values of new invariant for paths,
stars, complete graphs and complete bipartite graph are obtained. The paper
analyzes some tight bounds for the new invariant in general case. Also several
extremal differences between some related invariants are determined.

###### keywords:

doubly metric dimension, hitting set problem, metric dimension, extremal
differences.

##  1 Introduction

The metric dimension problem was introduced independently by Slater in 1975
[1] and Harary and Melter in 1976 [2]. Given a simple connected undirected
graph $G=(V,E)$, $d(u,v)$ denotes the distance between vertices $u$ and $v$,
i.e. the length of a shortest $u-v$ path. Vertex $w\in V(G)$ of graph $G$ is
said to resolve two vertices $u,v\in V(G)$ if $d(u,w)\neq d(v,w)$.

Set $S\subseteq V(G)$ is a resolving set of $G$ if any pair of distinct
vertices of $G$ are resolved by some vertex from $S$. A metric basis of $G$ is
a resolving set of minimal cardinality. The metric dimension of $G$, denoted
by $\beta(G)$, is the cardinality of its metric basis. The problem of
computing the metric dimension of an arbitrary graph is NP-hard [3].

In 2007, Caceres et al. [4] defined the notion of a doubly resolving set as
follows. Vertices $x,y\in V(G)$ are said to doubly resolve vertices $u,v\in
V(G)$ if $d(u,x)-d(u,y)\neq d(v,x)-d(v,y)$. Set $D\subseteq V(G)$ is a doubly
resolving set of $G$ if every two distinct vertices of $G$ are doubly resolved
by some two vertices of $D$. The doubly metric dimension of $G$, denoted by
$\psi(G)$, is the minimal cardinality of doubly resolving sets of $G$. The
problem of finding the doubly metric dimension of an arbitrary graph $G$ is
also NP-hard [5].

The concepts of edge and mixed metric dimensions were introduced by Kelenc et.
al [6, 7]. For the sake of simplicity, edge $e\in E(G)$ with endpoints $u$ and
$v$ will be denoted by $e=uv$. The distance between edge $e=uv\in E(G)$ and
vertex $w\in V(G)$, denoted by $d(e,w)$, is defined as
$d(e,w)=min\\{d(u,w),\,d(v,w)\\}$. Vertex $w$ resolves two edges $e_{1}$ and
$e_{2}$ if $d(e_{1},w)\neq d(e_{2},w)$. Set $N\subseteq V(G)$ is an edge
resolving set if for any pair of edges from $E(G)$ there is some vertex in $N$
that resolves them. The edge metric dimension of $G$, denoted by
$\beta_{E}(G)$, is the minimum cardinality of edge resolving sets of $G$.

Finally, the concept of mixed metric dimension unifies metric and edge metric
dimensions in the following way. Vertex $w$ resolves two items $a,b\in
V(G)\bigcup E(G)$ if $d(a,w)\neq d(b,w)$. Mixed resolving set $M\subseteq
V(G)$ is defined as a set such that for any pair of items from $V(G)\bigcup
E(G)$ there is some vertex in $M$ that resolves them. Following earlier
definitions, the mixed metric dimension of $G$, denoted by $\beta_{M}(G)$ is
defined as the minimal cardinality of mixed resolving sets of $G$. Finding
$\beta_{E}(G)$ and $\beta_{M}(G)$ are both NP-hard in general case [6, 7].

In the sequel the following definitions will be used. Let $\Delta(G)$ denote
the maximal degree of vertices in graph $G$. Additionally, $N(v)=\\{w\in
V(G)|vw\in E(G)\\}$ and $N[v]=\\{v\\}\bigcup N(v)$ are open and closed
neighbourhood of $v$, respectively.

######  Definition 1.

([8]) For an arbitrary edge $e=uv\in E(G)$

$W_{uv}=\\{w\in V(G)|d(u,w)<d(v,w)\\}$

and

$W_{vu}=\\{w\in V(G)|d(v,w)<d(u,w)\\}$

Complements of sets $W_{uv}$ and $W_{vu}$, denoted by $\overline{W_{uv}}$ and
$\overline{W_{vu}}$, are the following sets: $\overline{W_{uv}}=\\{w\in
V(G)|d(u,w)\geq d(v,w)\\}$ and $\overline{W_{vu}}=\\{w\in V(G)|d(v,w)\geq
d(u,w)\\}$.

The set of vertices on equal distances from $u$ and $v$ is denoted in the
literature by ${}_{u}{W_{v}}$ ([8]). Note that
${}_{u}{W_{v}}=\overline{W_{uv}}\setminus W_{vu}=\overline{W_{vu}}\setminus
W_{uv}$. Also, $\overline{W_{uv}}\bigcup\overline{W_{vu}}=V(G)$.

The following definition introduces the well-known concept of hitting sets
[9].

######  Definition 2.

For a given set $S$ and family $\mathop{F}=\\{S_{1},...,S_{k}\\}$,
$S_{i}\subseteq S$, $\bigcup\limits_{i=1}^{k}S_{i}=S$, a hitting set
$H\subseteq S$ of family $F$ is a set which has a non-empty intersection with
each $S_{i}$, i.e. $(\forall i\in\\{1,...,k\\})H\bigcap S_{i}\neq\emptyset$.

The minimal hitting set problem is to find a hitting set of the minimal
cardinality. This problem is equivalent to the set covering problem and is
known to be NP-hard [10].

######  Definition 3.

([11]) Value $mhs_{<}(G)$ is defined to be the minimal cardinality of hitting
sets of family $\\{W_{uv},W_{vu}|uv\in E(G)\\}$.

It is easy to see that the following property holds:

######  Property 1.

$mhs_{<}(G)\geq 2$.

###### Proof.

Let $uv$ be an arbitrary edge of $G$. Since $W_{uv}\cap W_{vu}=\emptyset$, a
hitting set of $\\{W_{uv},W_{vu}\\}$ has at least two elements, one from
$W_{uv}$ and one from $W_{vu}$. Therefore, a hitting set of family
$\\{W_{uv},W_{vu}|uv\in E(G)\\}$ also has at least two elements. By Definition
3, it follows that $mhs_{<}(G)\geq 2$. ∎

The following proposition was proved in [11]:

######  Proposition 1.

([11]) Let $G$ be a connected graph, $uv\in E(G)$ an arbitrary edge and $M$ a
mixed resolving set of $G$. Then

  * (i)

$W_{uv}\cap M\neq\emptyset;$

  * (ii)

$W_{vu}\cap M\neq\emptyset$.

######  Corollary 1.

([11]) For every connected graph $G$ it holds $\beta_{M}(G)\geq mhs_{<}(G)$.

In the sequel we will use the following results about $\psi(G)$,
$\beta_{E}(G)$ and $\beta_{M}(G)$.

######  Proposition 2.

([4]) Let $G$ be any graph of order $n$, then $2\leq\psi(G)\leq n-1$.

######  Proposition 3.

([4]) Let $K_{n}$ be a complete graph of order $n$, then
$\psi(K_{n})=max\\{2,n-1\\}$.

######  Proposition 4.

([4]) Let $T$ be any tree with $l(T)$ leaves, then $\psi(T)=l(T)$.

######  Corollary 2.

For any path $P_{n}$ it holds $\psi(P_{n})=2$.

######  Proposition 5.

([4]) For any cycle $C_{n}$, $n\geq 3$, it holds

$\psi(C_{n})=\begin{cases}2,&n\,is\,odd\\\ 3,&n\,is\,even\end{cases}$

######  Proposition 6.

([6]) For $n\geq 2$ it holds $\beta_{E}(P_{n})=\beta(P_{n})=1$,
$\beta_{E}(C_{n})=\beta(C_{n})=2$, $\beta_{E}(K_{n})=\beta(K_{n})=n-1$.
Moreover, $\beta_{E}(G)=1$ if and only if $G$ is a path.

######  Proposition 7.

([6]) Let $G$ be a connected graph. Then $\beta_{E}(G)\geq\lceil
log_{2}\Delta(G)\rceil$

######  Proposition 8.

([7]) For a connected graph $G$, it holds $2\leq\beta_{M}(G)\leq n$. Moreover,
$\beta_{M}(G)=2$ if and only if $G$ is a path.

######  Proposition 9.

([7]) For any complete bipartite graph $K_{r,t}$, $r,t\geq 2$, it holds

$\beta_{M}(K_{r,t})=\begin{cases}r+t-1,&r=2\vee t=2\\\ r+t-2,&otherwise\\\
\end{cases}$

######  Definition 4.

Let $v$ be a vertex of graph $G$. A vertex $u\in N(v)$ is called a maximal
neighbour of $v$ if $N[v]\subseteq N[u]$. $G$ is a maximal neighbour graph if
each vertex $v\in V(G)$ has a maximal neighbour.

######  Theorem 1.

([7]) Let $G$ be any graph of order $n$. Then $\beta_{M}(G)=n$ if and only if
$G$ is a maximal neighbour graph.

The following definition introduces a new graph invariant which will be
analyzed in this paper.

######  Definition 5.

Value $mhs_{\leq}(G)$ is defined to be the minimal cardinality of hitting sets
of family $\\{\overline{W_{uv}},\overline{W_{vu}}|uv\in E(G)\\}$.

The paper also deals with extremal differences of graph invariants which are
defined as follows.

######  Definition 6.

Let $\xi_{1}(G)$ and $\xi_{2}(G)$ be two graph invariants. Then extremal
difference $(\xi_{1}-\xi_{2})(n)$ is defined as the maximal value of
difference $\xi_{1}(G)-\xi_{2}(G)$ for all connected graphs $G$ of order $n$.

It should be noted that the minimal value of difference
$\xi_{1}(G)-\xi_{2}(G)$ is equal to $-(\xi_{2}-\xi_{1})(n)$. Also, only non-
trivial extremal differences are in cases when $n\geq 3$, since path $P_{2}$
is only connected graph of order 2, so it holds
$(\xi_{1}-\xi_{2})(2)=\xi_{1}(P_{2})-\xi_{2}(P_{2})$.

The paper is organized as follows. In Section 2 it is shown that
$mhs_{\leq}(G)$ is a new lower bound for $\psi(G)$. Exact values of the new
invariant are obtained for some special classes of graphs. Also, some tight
bounds for $mhs_{\leq}(G)$ in general case are derived. Section 3 provides the
exact values of extremal differences between invariants $\psi(G)$ and
$mhs_{\leq}(G)$, $mhs_{<}(G)$ and $mhs_{\leq}(G)$, $\beta_{M}(G)$ and
$mhs_{<}(G)$, as well as some upper and lower bounds for extremal difference
between $\psi(G)$ and $\beta_{E}(G)$. Section 4 gives concluding remarks about
obtained results and gives some directions for future work.

##  2 A new lower bound for $\psi(G)$

The following theorem and its corollary give a new lower bound for $\psi(G)$.

######  Theorem 2.

Let $G$ be a connected graph, $uv\in E(G)$ an arbitrary edge and $S$ a doubly
resolving set of $G$. Then

  * (i)

$\overline{W_{uv}}\cap S\neq\emptyset;$

  * (ii)

$\overline{W_{vu}}\cap S\neq\emptyset$.

###### Proof.

Let us suppose that the statement of Theorem 2 does not hold, i.e. there
exists an edge $uv\in E(G)$ such that
$\overline{W_{uv}}\cap S=\emptyset$ or $\overline{W_{vu}}\cap S=\emptyset$.
In the first case it follows that $d(u,w)<d(v,w)$ for each $w\in S$. Since
$uv\in E(G)$ it follows that $d(v,w)=d(u,w)+1$, i.e. $d(v,w)-d(u,w)=1$ for
each $w\in S$. This implies that vertices $u$ and $v$ are not doubly resolved
by any pair of vertices from $S$, which is a contradiction.
In the case when $\overline{W_{vu}}\cap S=\emptyset$ a similar contradiction
can be derived. ∎

Theorem 2 implies that any doubly resolving set $S$ of $G$ is a hitting set of
family $\\{\overline{W_{uv}},\overline{W_{vu}}|uv\in E(G)\\}$. Since
$mhs_{\leq}(G)$ is the minimal cardinality of hitting sets of this family, the
following corollary of Theorem 2 holds.

######  Corollary 3.

For every connected graph $G$ it holds $\psi(G)\geq mhs_{\leq}(G)$

In the following Proposition 10 exact values of $mhs_{\leq}(G)$ and
$mhs_{<}(G)$ for some special types of graphs are derived.

The obtained values are used in Lemma 1 to prove that certain lower and upper
bounds of $mhs_{\leq}(G)$ and $mhs_{<}(G)$ for arbitrary connected graph $G$
are tight.

######  Proposition 10.

  * (i)

For path $P_{n}$, $n\geq 2$, it holds that
$mhs_{\leq}(P_{n})=mhs_{<}(P_{n})=2$;

  * (ii)

For star $S_{n}$, $n\geq 3$, it holds that
$mhs_{\leq}(S_{n})=mhs_{<}(S_{n})=n-1$;

  * (iii)

For complete graph $K_{n}$, $n\geq 3$, it holds that
$mhs_{\leq}(K_{n})=2,mhs_{<}(K_{n})=n$.

  * (iv)

For complete bipartite graph $K_{2,m}$, $m\geq 2$, it holds that
$mhs_{\leq}(K_{2,m})=mhs_{<}(K_{2,m})=2$.

###### Proof.

(i) Let $H$ be a hitting set of family $\\{W_{uv},W_{vu}|uv\in E(P_{n})\\}$.
Since $V(P_{n})=\\{v_{i}|1\leq i\leq n\\}$ and $E(P_{n})=\\{v_{i}v_{i+1}|1\leq
i\leq n-1\\}$, it is easy to see that $W_{v_{i}v_{i+1}}=\\{v_{j}|1\leq j\leq
i\\}$ and $W_{v_{i+1}v_{i}}=\\{v_{j}|i+1\leq j\leq n\\}$ implying
$\overline{W_{v_{i}v_{i+1}}}=W_{v_{i+1}v_{i}}$ and
$\overline{W_{v_{i+1}v_{i}}}=W_{v_{i}v_{i+1}}$. Therefore $H$ is also a
hitting set of family $\\{\overline{W_{uv}},\overline{W_{vu}}|uv\in
E(P_{n})\\}$. Since $W_{v_{1}v_{2}}=\\{v_{1}\\}$ and $W_{v_{1}v_{2}}\cap
S\neq\emptyset$ it holds that $v_{1}\in H$. In the same way, since
$W_{v_{n}v_{n-1}}=\\{v_{n}\\}$ and $W_{v_{n}v_{n-1}}\cap H\neq\emptyset$ it
holds that $v_{n}\in H$. Therefore, $|H|\geq 2$. Since $v_{1}\in
W_{v_{i}v_{i+1}}$ and $v_{n}\in W_{v_{i+1}v_{i}}$, $i=1,...,n-1$ the hitting
set of the minimal cardinality is exactly $H=\\{v_{1},v_{n}\\}$ and
$mhs_{<}(P_{n})=mhs_{\leq}(P_{n})=2$.
(ii) Star $S_{n}$ is defined by $V(S_{n})=\\{v_{i}|1\leq i\leq n\\}$,
$E(S_{n})=\\{v_{1}v_{i}|2\leq i\leq n\\}$. It is easy to see that
$W_{v_{i}v_{1}}=\\{v_{i}\\}$ and $W_{v_{1}v_{i}}=V(S_{n})\setminus\\{v_{i}\\}$
for each $i=2,...,n$. Therefore, a hitting set $H$ of family
$\\{W_{v_{i}v_{1}},W_{v_{1}v_{i}}|2\leq i\leq n\\}$ satisfies
$\\{v_{2},...,v_{n}\\}\subseteq H$. Since
$W_{v_{1}v_{i}}\bigcap\\{v_{2},...,v_{n}\\}\neq\emptyset$ and
$W_{v_{i}v_{1}}\bigcap\\{v_{2},...,v_{n}\\}\neq\emptyset$ for $i=2,...,n$ it
follows that $\\{v_{2},...,v_{n}\\}$ is a hitting set of the minimal
cardinality, i.e. $mhs_{<}(S_{n})=n-1$. Furthermore, since
$\overline{W_{v_{i}v_{1}}}=W_{v_{1}v_{i}}$ and
$\overline{W_{v_{1}v_{i}}}=W_{v_{i}v_{1}}$ for $i=2,...,n$ it follows that
$\\{v_{2},...,v_{n}\\}$ is also a hitting set of family
$\\{\overline{W_{v_{i}v_{1}}},\overline{W_{v_{1}v_{i}}}|2\leq i\leq n\\}$ with
the minimal cardinality and hence $mhs_{\leq}(S_{n})=n-1$.
(iii) It is easy to check that $W_{uv}=\\{u\\}$, $W_{vu}=\\{v\\}$ for each
$uv\in E(K_{n})$. Therefore $V(K_{n})$ is a hitting set of family
$\\{W_{uv},W_{vu}|uv\in E(K_{n})\\}$ with the minimal cardinality and
$mhs_{<}(K_{n})=n$.
Also, $\overline{W_{uv}}=V(K_{n})\setminus\\{u\\}$ and
$\overline{W_{vu}}=V(K_{n})\setminus\\{v\\}$, for each $uv\in E(K_{n})$. As
$u\notin\overline{W_{uv}}$ and $v\notin\overline{W_{vu}}$, a set consisting of
one vertex can not be a hitting set of family
$\\{\overline{W_{uv}},\overline{W_{vu}}|uv\in E(K_{n})\\}$, i.e.
$mhs_{\leq}(K_{n})\geq 2$.
Let $a,b\in V(K_{n})$, $a\neq b$, be two arbitrrary distinct vertices. Then
for each $uv\in E(K_{n})$ there are three possible cases:
Case 1: If $u\neq a$ and $v\neq a$ then $a\in\overline{W_{uv}}$ and
$a\in\overline{W_{vu}}$;
Case 2: If $u=a$ then $a\notin\overline{W_{av}}$ and $a\in\overline{W_{va}}$;
Case 3: If $v=a$ then $a\in\overline{W_{ua}}$ and $a\notin\overline{W_{au}}$.
However, $b\in\overline{W_{av}}$ and $b\in\overline{W_{au}}$. Therefore,
$\\{a,b\\}$ is a hitting set of family
$\\{\overline{W_{uv}},\overline{W_{vu}}|uv\in E(K_{n})\\}$ with the minimal
cardinality and hence $mhs_{\leq}(K_{n})=2$.
(iv) Complete bipartite graph $K_{2,m}$ is defined by $V(K_{2,m})=V_{1}\bigcup
V_{2}$, $V_{1}=\\{u_{1},u_{2}\\}$, $V_{2}=\\{v_{i}|1\leq i\leq m\\}$ and
$E(K_{2,m})=\\{u_{i}v_{j}|1\leq i\leq 2,1\leq j\leq m\\}$. From Property 1 it
follows that $mhs_{<}(K_{2,m})\geq 2$. Next we prove that set
$\\{u_{1},u_{2}\\}$ is a hitting set of family
$\\{W_{u_{i}v_{j}},W_{v_{j}u_{i}}|1\leq i\leq 2,1\leq j\leq m\\}$.
As $d(a,b)=1$ if $a\in V_{1}$ and $b\in V_{2}$ and $d(a,b)=2$ for $a,b\in
V_{1}$ or $a,b\in V_{2}$ it follows that for each edge $u_{i}v_{j}\in
E(K_{2,m})$ we have
$W_{u_{i}v_{j}}=\\{u_{i}\\}\bigcup(V_{2}\setminus\\{v_{j}\\})$,
$W_{v_{j}u_{i}}=\\{v_{j}\\}\bigcup(V_{1}\setminus\\{u_{i}\\})$. Then $u_{1}\in
W_{u_{1}v_{j}}$, $u_{1}\notin W_{v_{j}u_{1}}$, $u_{2}\in W_{u_{2}v_{j}}$,
$u_{2}\notin W_{v_{j}u_{2}}$ for each $j=1,...,m$. However, $u_{1}\in
W_{v_{j}u_{2}}$ and $u_{2}\in W_{v_{j}u_{1}}$. Therefore, $\\{u_{1},u_{2}\\}$
is a hitting set of the minimal cardinality and $mhs_{<}(K_{2,m})=2$.
As $\overline{W_{u_{i}v_{j}}}=W_{v_{j}u_{i}}$ and
$\overline{W_{v_{j}u_{i}}}=W_{u_{i}v_{j}}$ for $i=1,2$ and $j=1,...,m$ then
$\\{u_{1},u_{2}\\}$ is a hitting set of family
$\\{\overline{W_{u_{i}v_{j}}},\overline{W_{v_{j}u_{i}}}|1\leq i\leq 2,1\leq
j\leq m\\}$ with the minimal cardinality and hence $mhs_{\leq}(K_{2,m})=2$. ∎

According to Corollary 2, Corollary 3 and Proposition 10, new invariant
$mhs_{\leq}(G)$ represents a tight lower bound for doubly metric dimension
$\psi(G)$ as $\psi(P_{n})=mhs_{\leq}(P_{n})=2$.

Next lemma gives tight lower and upper bounds for $mhs_{\leq}(G)$ and
$mhs_{<}(G)$ for arbitrary connected graph $G$.

######  Lemma 1.

For $n\geq 3$ and graph $G$ of order $n$ it holds:

  * (i)

$mhs_{\leq}(G)\leq mhs_{<}(G)$

  * (ii)

$2\leq mhs_{\leq}(G)\leq n-1$

  * (iii)

$mhs_{<}(G)\leq n$

###### Proof.

(i) As $W_{vu}\subseteq\overline{W_{uv}}$ and
$W_{uv}\subseteq\overline{W_{vu}}$ for each $uv\in E(G)$ it follows that
$mhs_{\leq}(G)\leq mhs_{<}(G)$ This inequality is tight since by Propostion 10
it holds $mhs_{\leq}(P_{n})=mhs_{<}(P_{n})=2$;
(ii) Let us prove that $mhs_{\leq}(G)>1$. If we suppose that $mhs_{\leq}(G)=1$
then there exist vertex $x\in V(G)$ such that $\\{x\\}$ is a hitting set of
family $\\{\overline{W_{uv}},\overline{W_{vu}}|uv\in E(G)\\}$, i.e.
$x\in\overline{W_{uv}}$ and $x\in\overline{W_{vu}}$ for each $uv\in E(G)$. As
$G$ is connected there exists vertex $a\in V(G)$ such that $ax\in E(G)$. Since
$\overline{W_{ax}}=\\{w\in V(G)|d(a,w)\geq d(x,w)\\}$ and
$\overline{W_{xa}}=\\{w\in V(G)|d(x,w)\geq d(a,w)\\}$ it follows that
$x\in\overline{W_{ax}}$ but $x\notin\overline{W_{xa}}$, which is a
contradiction. Therefore, $mhs_{\leq}(G)\geq 2$. This lower bound is tight
since by Propostion 10 it can be achieved for path $P_{n}$ or complete graph
$K_{n}$.
From Corollary 3 it is known that $mhs_{\leq}(G)\leq\psi(G)$, while by
Propostion 2 from [4] it is known that $2\leq\psi(G)\leq n-1$, implying that
$mhs_{\leq}(G)\leq n-1$. By Propostion 10 this upper bound is reached for star
$S_{n}$.
(iii) As $W_{uv}$ and $W_{vu}$ are subsets of $V(G)$ for each $uv\in E(G)$,
and $G$ is of order $n$, it follows $mhs_{<}(G)\leq n$. By Propostion 10 this
upper bound is reached for complete graph $K_{n}$. ∎

Is should be noted that lower bound $mhs_{<}(G)\geq 2$ from Property 1 is
tight for e.g. path $P_{n}$.

##  3 Extremal differences

The first task in this section is to find extremal diferences between doubly
metric dimension $\psi(G)$ and new invariant $mhs_{\leq}(G)$. The complete
answer is given in Theorem 3.

######  Theorem 3.

For $n\geq 3$ it holds

  * (i)

$(mhs_{\leq}-\psi)(n)=0$

  * (ii)

$(\psi-mhs_{\leq})(n)=n-3$

###### Proof.

(i) For any connected graph $G$, from Corollary 3 it follows that
$mhs_{\leq}(G)\leq\psi(G)$, i.e. $(mhs_{\leq}-\psi)(n)\leq 0$. Since, by
Corrolary 2 and Proposition 10, $\psi(P_{n})=mhs_{\leq}(P_{n})=2$ it follows
$(mhs_{\leq}-\psi)(n)=0$.
(ii) From Proposition 2 and Lemma 1 it is evident that for every graph $G$ it
holds $\psi(G)-mhs_{\leq}(G)\leq n-3$. By Proposition 3 and Proposition 10
this upper bound is reached for complete graph $K_{n}$. ∎

Since $mhs_{\leq}(G))$ is a lower bound for $\psi(G)$ and $mhs_{<}(G)$
represents a lower bound for $\beta_{M}(G)$ it is interesting to find extremal
differences between these lower bounds. Their exact values are given by
Theorem 4.

######  Theorem 4.

For $n\geq 3$ it holds

  * (i)

$(mhs_{\leq}-mhs_{<})(n)=0$

  * (ii)

$(mhs_{<}-mhs_{\leq})(n)=n-2$

###### Proof.

(i) By Lemma 1 it holds $(mhs_{\leq}-mhs_{<})(n)\leq 0$. By Proposition 10
this upper bound is reached for e.g. path $P_{n}$, which implies
$(mhs_{\leq}-mhs_{<})(n)=0$.
(ii) From Lemma 1 it follows $mhs_{<}(G)\leq n$ and $mhs_{\leq}(G)\geq 2$
which implies that $mhs_{<}(G)-mhs_{\leq}(G)\leq n-2$. Acording to Proposition
10 this upper bound is reached for complete graph $K_{n}$. ∎

Since both invarinats $mhs_{\leq}(G)$ and $mhs_{<}(G)$ are based on the
minimal hitting set problem and their definitions are similar, it is expected
that there exist classes of graphs for which they have the same value.
However, Theorem 4 shows that values of these invariants can drastically
differ.

In [11] it is shown that $mhs_{<}(G)$ is a lower bound of $\beta_{M}(G)$.
Therefore, it is interesting to see what extremal differences of them are.
This task is solved in Theorem 6, which uses Theorem 5 and Corollary 4.

######  Theorem 5.

Let $G$ be any connected graph of order $n$. Then $mhs_{<}(G)=n$ if and only
if $G$ is a maximal neighbour graph.

###### Proof.

($\Rightarrow$) If $mhs_{<}(G)=n$ from Corrolary 1 it follows $\beta_{M}(G)=n$
which by Theorem 1 implies that $G$ is a maximal neighbour graph.
($\Leftarrow$)Let $G$ be a maximal neighbour graph and $v\in V(G)$ be an
arbitrary vertex. Then there exists vertex $u\in N(v)$ such that
$N(v)\subseteq N(u)$. Let us prove that
$W_{vu}=\\{w|d(v,w)<d(u,w)\\}=\\{v\\}$. Let $z$ be an arbitrary vertex of $G$
different from $v$. If $z\in N(v)$ then $d(v,z)=1=d(u,z)$ and hence $z\notin
W_{vu}$.
If $z\in V(G)\setminus N(v)$ then $d(v,z)=1+d(x,z)$ where $x\in N(v)$.
If $x=u$ then $d(v,z)=1+d(u,z)$ and $z\notin W_{vu}$.
If $x\neq u$ then $d(v,z)=1+d(x,z)=d(u,z)$ and we again conclude that $z\notin
W_{vu}$.
Since $W_{vu}=\\{v\\}$ for each $v\in V(G)$ the hitting set of the family
$\\{W_{uv},W_{vu}|uv\in E(G)\\}$ has to contain all nodes from $V(G)$ and
therefore $mhs_{<}(G)=n$. ∎

Theorem 1 and Theorem 5 imply the following corollary.

######  Corollary 4.

Let $G$ be any connected graph of order $n$. Then $mhs_{<}(G)=n$ if and only
if $\beta_{M}(G)=n$.

######  Theorem 6.

For $n\geq 3$ it holds

  * (i)

$(mhs_{<}-\beta_{M})(n)=0$

  * (ii)

$(\beta_{M}-mhs_{<})(n)=n-3$

###### Proof.

(i) For any connected graph $G$, from Corollary 1 it follows that
$mhs_{<}(G)-\beta_{M}(G)\leq 0$. Since, by Proposition 8 and Proposition 10,
$\beta_{M}(P_{n})=mhs_{<}(P_{n})=2$ it follows $(mhs_{<}-\beta_{M})(n)=0$.
(ii) By Proposition 8 it holds $\beta_{M}(G)\leq n$ and by Lemma 1 it follows
$mhs_{<}(G)\geq 2$. Case 1. $\beta_{M}(G)=n$.
According to Corolary 4 it holds $mhs_{<}(G)=n$ and consequently it is
$\beta_{M}(G)-mhs_{<}(G)=0$.
Case 2. $\beta_{M}(G)\leq n-1$.
In this case it holds $\beta_{M}(G)-mhs_{<}(G)\leq n-3$.
Since $n\geq 3$ in both cases it holds $\beta_{M}(G)-mhs_{<}(G)\leq n-3$. This
upper bound is reached for complete bipartite graphs $K_{2,n-2}$ since by
Proposition 9 from [7] it is $\beta_{M}(K_{2,n-2})=n-1$ and by Proposition 10
it is $mhs_{<}(K_{2,n-2})=2$. ∎

Finally, it is interesting to find extremal diferences between $\psi(G)$ and
$\beta_{E}(G)$.

For $n=3$ this task is completely resolved by Property 2. For $n\geq 4$, this
task is partially resolved by Theorem 7, which gives upper and lower bounds
for extremal difference between $\psi(G)$ and $\beta_{E}(G)$.

######  Property 2.

$(\psi-\beta_{E})(3)=1$ and $(\beta_{E}-\psi)(3)=0$

###### Proof.

There exist only two connected graphs of order 3: path $P_{n}$ and cycle
$C_{n}$. Since $\beta_{E}(P_{3})=1$ and
$\beta_{E}(C_{3})=\psi(P_{3})=\psi(C_{3})=2$ then $(\psi-\beta_{E})(3)=1$. ∎

######  Theorem 7.

For $n\geq 4$ it holds $\lfloor\frac{n}{2}\rfloor-1\leq(\psi-\beta_{E})(n)\leq
n-3$

###### Proof.

Let $m=\lfloor\frac{n}{2}\rfloor$ and let $T^{\prime}_{n}$ be a tree with
$V(T^{\prime}_{n})=\\{v_{1},...,v_{n}\\}$ and
$E(T^{\prime}_{n})=\\{v_{i}v_{i+1}|1\leq i\leq
n-m\\}\bigcup\\{v_{i}v_{n-m+i}|2\leq i\leq m\\}$ [12, 13]. Figure 1
illustrates trees $T^{\prime}_{n}$ for odd and even $n$. From Proposition 4 it
follows that $\psi(T^{\prime}_{n})=l(T^{\prime}_{n})=m+1$. It is proved in
[12, 13] that $\beta_{E}(T^{\prime}_{n})=2$ with edge metric base
$\\{v_{1},v_{n-m+1}\\}$. Therefore
$\psi(T^{\prime}_{n})-\beta_{E}(T^{\prime}_{n})=m-1=\lfloor\frac{n}{2}\rfloor-1$
implying $(\psi-\beta_{E})(n)\geq\lfloor\frac{n}{2}\rfloor-1$. Since for any
graph $G$ it holds $\psi(G)\leq n-1$ and $\beta_{E}(G)\geq 1$ it follows that
$(\psi-\beta_{E})(n)\leq n-2$.
Furthermore, this bound can be improved using a similar argument as in [12,
13].
Since $G$ is connected graph of order $n\geq 3$ it follows that maximal degree
$\Delta(G)\geq 2$. We consider two cases:
Case 1. $\Delta(G)=2$. The only such graphs of order $n$, $n\geq 3$ are path
$P_{n}$ and cycle $C_{n}$. Since by Corollary 2 it holds $\psi(P_{n})=2$ and
by Proposition 6 from [6] $\beta_{E}(P_{n})=1$ it follows that
$\psi(P_{n})-\beta_{E}(P_{n})=1$. Also, by Proposition 5 from [4] and
Proposition 6 from [6] it follows that $\psi(C_{n})-\beta_{E}(C_{n})\leq 1$.
In both cases the difference for $n\geq 4$ is less or equal than $n-3$.
Case 2. $\Delta(G)\geq 3$. From Proposition 7 ([6]) $\beta_{E}(G)\geq\lceil
log_{2}\Delta(G)\rceil\geq\lceil log_{2}3\rceil=2$. As $\psi(G)\leq n-1$ it
follows $\psi(G)-\beta_{E}(G)\leq n-3$. ∎

Tree
$T^{\prime}_{8}$$v_{1}$$v_{2}$$v_{6}$$v_{3}$$v_{7}$$v_{4}$$v_{8}$$v_{5}$Tree
$T^{\prime}_{9}$$v_{1}$$v_{2}$$v_{7}$$v_{3}$$v_{8}$$v_{4}$$v_{9}$$v_{5}$$v_{6}$
Figure 1: Trees $T^{\prime}_{8}$ and $T^{\prime}_{9}$.

##  4 Conclusions

This paper defines a new graph invariant $mhs_{\leq}(G)$, which is a new lower
bound for $\psi(G)$. Exact values of the new invariant are obtained for some
special classes of graphs. Next, some tight bounds for the new invariant in
general case are derived. Finally, some extremal differences between several
related invariants are obtained.

Direction of future work could be focused to find exact values of the new
invariant for some other interesting classes of graphs and consider other
extremal differences.

## References

## References

  * [1] P. J. Slater, Leaves of trees, Congr. Numer 14 (37) (1975) 549–559.
  * [2] F. Harary, R. Melter, On the metric dimension of a graph, Ars Combin 2 (1) (1976) 191–195.
  * [3] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics 70 (3) (1996) 217–229.
  * [4] J. Cáceres, C. Hernando, M. Mora, I. Pelayo, M. Puertas, C. Seara, D. Wood, On the metric dimension of cartesian products of graphs, SIAM Journal in Discrete Mathematics 21 (2) (2007) 423–441.
  * [5] J. Kratica, M. Čangalović, V. Kovačević-Vujčić, Computing minimal doubly resolving sets of graphs, Computers & Operations Research 36 (7) (2009) 2149–2159.
  * [6] A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Applied Mathematics 251 (2018) 204–220.
  * [7] A. Kelenc, D. Kuziak, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs, Applied Mathematics and Computation 314 (2017) 429–438.
  * [8] K. Balakrishnan, M. Changat, I. Peterin, S. Špacapan, P. Šparl, A. R. Subhamathi, Strongly distance-balanced graphs and graph products, European Journal of Combinatorics 30 (5) (2009) 1048–1053.
  * [9] D. Simovici, C. Reischer, Collections of sets and intractable problems in relational databases, Congressus Numerantium 59 (1970) 291.
  * [10] M. R. Garey, D. S. Johnson, Computers and intractability, Vol. 174, freeman San Francisco, 1979.
  * [11] M. Milivojević Danas, J. Kratica, A. Savić, Z. Maksimović, Some new general lower bounds for mixed metric dimension of graphs, Filomat 35 (2021) 4275–4285.
  * [12] M. Milivojević-Danas, Mixed metric dimension of graphs, Ph.D. thesis, University of Kragujevac, Serbia, (in Serbian) (2022).
  * [13] M. Milivojević-Danas, The difference between several metric dimension graph invariants, Discrete Applied Mathematics 332 (2023) 1–6.


# The War of the Efficiencies: Understanding the Tension between Carbon and
Energy Optimization

Walid A. Hanafy, Roozbeh Bostandoost, Noman Bashir, David Irwin, Mohammad
Hajiesmaili, and Prashant Shenoy  University of Massachusetts Amherst USA

(2023)

###### Abstract.

Major innovations in computing have been driven by scaling up computing
infrastructure, while aggressively optimizing operating costs. The result is a
network of worldwide datacenters that consume a large amount of energy, mostly
in an energy-efficient manner. Since the electric grid powering these
datacenters provided a simple and opaque abstraction of an unlimited and
reliable power supply, the computing industry remained largely oblivious to
the carbon intensity of the electricity it uses. Much like the rest of the
society, it generally treated the carbon intensity of the electricity as
constant, which was mostly true for a fossil fuel-driven grid. As a result,
the cost-driven objective of increasing energy-efficiency — by doing more work
per unit of energy — has generally been viewed as the most carbon-efficient
approach. However, as the electric grid is increasingly powered by clean
energy and is exposing its time-varying carbon intensity, the most energy-
efficient operation is no longer necessarily the most carbon-efficient
operation. There has been a recent focus on exploiting the flexibility of
computing’s workloads—along temporal, spatial, and resource dimensions—to
reduce carbon emissions, which comes at the cost of either performance or
energy efficiency. In this paper, we discuss the trade-offs between energy
efficiency and carbon efficiency in exploiting computing’s flexibility and
show that blindly optimizing for energy efficiency is not always the right
approach.

Carbon Efficiency, Energy Efficiency, Sustainable Computing

††journalyear: 2023††copyright: acmlicensed††conference: 2nd Workshop on
Sustainable Computer Systems; July 9, 2023; Boston, MA, USA††booktitle: 2nd
Workshop on Sustainable Computer Systems (HotCarbon ’23), July 9, 2023,
Boston, MA, USA††price: 15.00††doi: 10.1145/3604930.3605709††isbn:
979-8-4007-0242-6/23/07††ccs: Computer systems organization Cloud
computing††ccs: Hardware Renewable energy††ccs: Social and professional topics
Sustainability

##  1\. Introduction

The demand for computing has experienced rapid growth and is expected to
accelerate even further. However, the increase in computing demand has not
resulted in a proportional increase in energy demand so far (iea, 2022a). The
growth in computing’s energy consumption has been kept in check by massive
gains in algorithmic efficiency, measured in cycles per unit of work, of its
software and energy efficiency, measured in energy consumption per cycle, of
its hardware (Bashir et al., 2022). However, as the algorithmic and energy
efficiency gains slow down, an increase in computing demand directly increases
the energy demand. A conservative estimate projects that the energy
consumption of datacenters will increase by at least 10% per year till 2030
(Bangalore et al., 2023), much higher than an estimated increase of 1.65% per
year in 2010s (Masanet et al., 2020). As society has begun to recognize the
environmental impact of our activities, reducing the carbon footprint of this
accelerating energy demand has attracted significant attention from academic
researchers (Souza et al., 2023; Lechowicz et al., 2023; Wiesner et al., 2021;
Switzer et al., 2023) and industry leaders (Acun et al., 2023; Radovanović et
al., 2023).

The carbon footprint of computing depends on the computing’s carbon
efficiency, denoted as $\eta_{\texttt{C}}$, which is calculated by dividing
the computing’s energy efficiency $\eta_{\texttt{E}}$, measured as work done
per unit of energy, by the energy’s carbon intensity $c$, measured as the
amount of emitted greenhouse gases (GHG) per kWh of energy. Traditionally, the
electric grid has been powered by fossil fuels such as coal, and oil, which
have similar carbon intensities of 1038 $g.CO_{2}eq/kWh$ and 1106
$g.CO_{2}eq/kWh$ (car, 2022). Furthermore, even if energy’s carbon intensity
slightly varied across space and time, it was invisible to electricity
consumers due to the simple and opaque abstraction exposed by the grid. As a
result, the carbon intensity of electricity was viewed as constant, every unit
of energy was the same, and a unit improvement in computing’s energy
efficiency meant a proportional improvement in computing’s carbon efficiency.
As the industry aggressively optimized for computing’s energy
efficiency—driven by the need to scale while reducing operational costs—it was
only serendipitous that a cost-driven approach was also the environmentally
conscious choice.

Figure 1. _Energy’s carbon intensity (05/15/2022 - 05/31/2022)._

However, the evolution of the electric grid over the last decade has
diversified the mix of energy sources used for electricity generation. With a
higher penetration of renewable energy in the electric grid and advancements
in traditional power plant technologies, such as combined heat and power (CHP)
plants, the carbon intensity of electricity now varies widely over time and
across locations (iea, 2022b; Sukprasert et al., 2023). Figure 1 illustrates
the carbon intensity of energy in $gCO_{2}eq/kWh$ for four locations around
the globe. Sweden exhibits a very low carbon intensity due to its reliance on
hydropower, while the Netherlands has a higher carbon intensity due to its
fossil fuel-heavy resource mix. Furthermore, Ontario and California experience
diurnal changes in carbon intensity due to the increased use of solar energy.
The growing penetration of renewables in the electric grid has decreased the
carbon intensity worldwide but also highlighted the importance of considering
the timing and location of energy consumption. Computing workloads offer the
flexibility to choose when and where to execute and consume energy. However,
mechanisms that enable the exploitation of computing’s flexibility tend to be
energy-inefficient. Therefore, in most cases, achieving carbon efficiency
requires sacrificing energy efficiency.

From a business standpoint, it does not make financial sense to be
purposefully energy-inefficient as it costs money, especially in the absence
of penalties on carbon emissions. However, there is a social incentive to
reduce carbon footprint, and the computing industry is responding to this
problem in two ways. First, assuming a time-varying carbon intensity,
operators are leveraging the performance flexibility of workloads such as
delaying or relocating workloads. Second, the industry is using various forms
of carbon credits and offsets to reduce its estimated carbon emissions.
Initially, carbon credits and power purchase agreements were used to offset
carbon emissions on an annual basis. However, recently, the industry has
started using more stricter forms of carbon offsets that match the energy
demand of datacenters with renewable energy generation on the same
distribution grid on an hourly basis, known as 24/7 matching (goo, 2023).
While this is a step in the right direction, it should not be construed as
running the datacenters purely on zero-carbon energy because datacenters still
rely on the electric grid. As the electric grid still uses carbon-intensive
energy sources, no one can be fully carbon-free until the grid itself is
carbon-free. In this futuristic world, the focus can shift back toward the
gains in energy efficiency that the industry has helped achieve. In the
meanwhile, blindly focusing on energy efficiency leaves many possible carbon-
specific optimizations on the table. Unfortunately, just like the tension
between alternating and direct current in the late nineteenth century, this
debate has become a war of narratives and financial levers rather than a
technical one (war, 2014, 2023). As grids worldwide still rely on carbon-
emitting energy generation sources, we need to exploit all the flexibility of
computing workloads such that we maximize carbon efficiency while optimizing
energy efficiency.

Computing workloads, depending on the application, offer flexibility along
multiple dimensions. They can be delayed, paused, and resumed (temporal
flexibility). They can be assigned more or fewer resources (resource scaling).
They can be scaled up or down using Dynamic Voltage and Frequency Scaling
(DVFS) (rate shifting). Finally, they can be executed at a different
geographical location (spatial shifting). These mechanisms for exploiting
flexibility could be energy-inefficient to varying degrees and yield different
amounts of carbon savings. As energy inefficiency costs money, we need to
analyze the trade-offs between carbon efficiency and energy efficiency. This
can not only guide the industry in estimating the cost of optimizing for
carbon but also help regulators determine the appropriate incentives and
penalties for carbon emissions.

The management of carbon emissions in cloud datacenters is receiving
significant attention due to the growing impact of climate change (Souza et
al., 2023; Chien, 2021; Gupta et al., 2021, 2022; Patterson et al., 2021,
2022; Wiesner et al., 2021; Dodge et al., 2022; Sukprasert et al., 2023).
While some studies have focused on embodied carbon, which refers to carbon
emissions from the manufacturing and relocation of infrastructure, we are
concentrating on the operational energy and carbon footprint of powering and
cooling the infrastructure. Although our efficiency metrics can encapsulate
other accounting methods, such as embodied carbon, by spreading the embodied
carbon over the actual lifespan of the infrastructure, we did not use that
combination since it does not comply with the GHG protocol (ghg, 2022) as
highlighted by other researchers (Bashir et al., 2023).

To the best of our knowledge, our work is the first to explicitly quantify the
energy-carbon trade-offs of various flexibility mechanisms. To demonstrate
this trade-off, we consider real-world carbon traces and analytically-modeled
applications and simulate the effect of carbon-saving mechanisms. We use a
state-of-the-art energy-efficient execution as the baseline and demonstrate
how carbon efficiency can be significantly increased by being energy
inefficient, and blindly optimizing for energy efficiency is not always the
right approach. We also highlight the trade-off breadth of different
techniques and show that there exists a tipping point where carbon savings is
not yet affected by the energy inefficiency of such mechanisms. Beyond this
point, the carbon footprint of energy overheads overweighs the reduction in
carbon savings from exploiting flexibility.

##  2\. Illustrating Efficiency Trade-offs

In this section, we investigate the trade-off between carbon efficiency and
energy efficiency of four commonly-used mechanisms for exploiting computing’s
flexibility: temporal shifting, resource scaling, rate shifting, and spatial
shifting. We choose state-of-the-art energy-efficient execution as the
baseline unless stated otherwise. Therefore, our carbon efficiency gains come
from optimizing specifically for carbon and not from improving computing’s
energy efficiency. Furthermore, the term “ _carbon efficiency_ ” refers to
computing’s carbon efficiency and not energy’s carbon efficiency, which is
referred to by the reciprocal term of carbon intensity.

We use a 3-year-long carbon intensity trace for Ontario, Canada, from
electricity map (ele, 2023) spanning January 1, 2020, to December 31, 2022.
The trace provides the hourly average intensity values, measured in
$gCO_{2}eq/kWh$. Unless stated otherwise, we assume that the job starts at the
hour boundary, and aggregate our results across jobs starting at each hour of
the year. We report carbon efficiency and energy efficiency values, with the
results normalized to the most energy-efficient for energy efficiency and the
least carbon-efficient for carbon efficiency, unless otherwise specified.
Furthermore, we present our analysis across a wide range of empirically-driven
configurations that map to real-world server classes and application
characteristics to ensure our results are broadly applicable and not tied to a
particular application or hardware.

###  2.1. Temporal Shifting

The time-varying nature of electricity’s carbon intensity creates green time
periods, where the carbon intensity is significantly lower than the average
carbon intensity for that location, as shown in Figure 1. The simplest, and
most common, strategy to increase computing’s carbon efficiency is to wait for
such low carbon periods to arrive, execute the job during a given period,
suspend the job at the end of this period, and resume its operation during the
next low carbon period. However, this intermittent execution of jobs leverages
checkpoint and restore techniques to save the state between low carbon
periods, incurring energy overhead. The amount of overhead depends on the
frequency of checkpoint and restore operations and the energy cost of a single
checkpoint and restore operation, which, in turn, depends on the size of the
state of the application (Sharma et al., 2016).

(a) Carbon Efficiency

(b) Energy Efficiency

Figure 2. _Carbon and energy efficiency of jobs with different overheads.
Longer deadlines allow a higher use of checkpoint & restore to operate in low
carbon periods._

Prior work on temporal shifting to reduce the carbon footprint has focused on
configuring the thresholds for identifying low carbon periods, with or without
future knowledge of carbon intensity, and the trade-offs between carbon
savings and job completion times (Souza et al., 2023; Radovanović et al.,
2023; Wiesner et al., 2021), while ignoring the overhead of suspend-resume.
There is also a recent work that explores online algorithms, taking into
account the overhead of suspend and resume methods (Lechowicz et al., 2023).
However, these studies do not explicitly discuss or quantify the trade-off
between the loss of energy efficiency and gains in carbon efficiency. We
bridge this gap in an empirical study outlined next.

_1\. Experimental Setup._ Our setup presumes multiple jobs with different
overhead percentages, aiming to optimize carbon efficiency using state-of-the-
art carbon-aware execution policies.

Applications. We consider an application that constantly performs computation,
such as ML training, and requires a certain memory size to store the
intermediate results. We assume that the job has performance flexibility and
allows the operator to checkpoint & restore its state. We use three variants
of this job represented by their checkpoint & restore overheads, which we
configure as the time it takes to checkpoint or restore the memory state of
the job. We set the overheads for the three variants as 5 minutes (low), 10
minutes (medium), and 15 (high) minutes, which can be mapped to real-world
applications by assuming ML training over different-sized models. The job also
has temporal flexibility, aka slack, which we define as a multiple of the
job’s uninterrupted execution time. For example, a slack factor of 1.5$\times$
for a 24hrs job without interruption means that it has 36hrs to finish. In our
experiments, we consider a 24hrs long job and vary the slack factor from
1$\times$ to 3$\times$ of the job’s runtime.

Policy. We use a deadline-aware _suspend-resume_ policy to execute the job
that has been proposed in recent work to reduce the carbon footprint of jobs
with temporal flexibility (Wiesner et al., 2021). This policy assumes perfect
future knowledge of carbon intensity and selects low carbon slots for
executing the job such that it finishes before the deadline. It does not take
into account the energy overhead of checkpoint & restore when determining the
number and selection of slots for execution. However, we take into account the
carbon overhead of intermittent execution and subtract that from carbon
savings when calculating carbon efficiency gains.

_2\. Experimental Results._ The results in Figure 2(a) show that a higher
degree of flexibility (higher slack) can lead to greater reductions in carbon
emissions (increased carbon efficiency). However, flexibility comes at the
cost of energy efficiency. As shown in Figure 2(b), larger slacks allow
applications to checkpoint & restore more often, increasing the energy and
carbon overhead, which reduces energy efficiency. In Figure 2(b), the y-axis
limit is set between 1 and 0.94 to ensure clear visibility of the lines
representing normalized energy efficiency. It is important to note that the
magnitude of carbon savings and the impact on energy efficiency are
application-specific, but their relationship is fundamental and will hold
across application characteristics and carbon intensity profiles.

_3\. Key Takeaways. Higher temporal flexibility enables applications to
increase their carbon efficiency, but the gains depend on how often
applications incur the energy and carbon overhead of the checkpoint and
restore mechanism to take advantage of low carbon periods. _

###  2.2. Resource Scaling

Resource scaling is the method of adding or removing resources to a given job
to speed up or slow down the speed of execution, respectively. In the context
of carbon-aware computing, resource scaling can be used as an antidote to the
increase in job completion time under _suspend-resume_ execution (Souza et
al., 2023; Hanafy et al., 2023). Instead of resuming the job at 1$\times$
during low carbon periods, it can be scaled up to k$\times$ to make up for the
time spent in suspend state. However, the effectiveness of scaling depends on
the application characteristics, such as the size of sequential barriers
modeled by Amdahl’s law (Amdahl, 1967). As a result, as the allocated
resources increase, the speed up increases sub-linearly, reducing the energy
efficiency of execution.

(a) Throughput

(b) Energy Efficiency

Figure 3. _As applications with sub-linear scaling characteristics scale,
their energy efficiency reduces._

_1\. Experimental Setup._ In this experiment, we demonstrate the carbon
efficiency and energy efficiency trade-off for an application that leverages
resource scaling to reduce its carbon footprint.

Applications. Since applications’ scalability dictates the energy overhead, we
consider different scalability in terms of the throughput reduction per
additional node. Figure 3 shows the scalability characteristics for three
applications with excellent scaling (5% reduction in normalized throughput per
additional node), high scaling (10% reduction per additional node), and
moderate scaling (15% reduction per additional node) characteristics. This
behavior is similar to many real-world distributed applications as shown in
(Qi et al., 2017). We assume that the energy consumption of each additional
node is the same. As a result, as shown in Figure 3(b), the energy efficiency
of the computing decreases due to reduced normalized throughput after scaling.

Policy. Souza et al. (2023) propose a carbon-aware scaling policy called _Wait
&Scale_, which selects an application-specific scale factor based on its
scalability characteristics. It assumes perfect knowledge of future carbon
intensity. Similar to a carbon-aware suspend-resume policy, it generates a
schedule that suspends the job during high carbon periods and resumes it at
the application-specific scale factor during the low carbon periods. In this
scenario, the scale factor is set to 1, which means that the job completion
time is the same as the completion time for an uninterrupted execution. As a
result, jobs do not gain carbon savings from temporal flexibility.

(a) Excellent

(b) High

(c) Moderate

Figure 4. _Normalized carbon and energy efficiency for different scalability
profiles when running in Ontario, Canada._

_2\. Experimental Results._ Figure 4 shows the normalized carbon efficiency
and energy efficiency of the three scalable applications with scalability
characteristics shown in Figure 3. The results indicate that maximizing energy
efficiency does not necessarily result in maximum carbon efficiency. Rather,
the increase in carbon efficiency depends on the flexibility that comes with a
decrease in energy efficiency. Furthermore, the results in Figure 4
demonstrate that the application’s scalability plays a significant role in
carbon efficiency gains and energy efficiency losses. For instance, the job
with excellent scaling (Figure 4(a)) was able to increase its carbon
efficiency by 68% at an energy efficiency loss of 15%. Conversely, the
moderately scalable job showed only a 34% increase in carbon efficiency but
paid more than a 25% loss in energy efficiency.

It is also worth noting that, in all three cases, Figure 4 illustrates that
increasing the scaling factor does not always improve carbon efficiency.
Beyond a certain scaling factor, the gain in throughput during high carbon
periods does not overcome the carbon cost due to low energy efficiency at high
scales. Hence, the reciprocal behavior that loss of energy efficiency does not
always lead to carbon efficiency should also be considered while scaling
applications.

_3\. Key Takeaways. Carbon-aware application of scaling policies can yield
significant gains in carbon efficiency. However, the high energy overhead of
scaling means that applications must be highly judicious in choosing their
scale factor as gains become marginal at high scales._

###  2.3. Rate Shifting

Dynamic Voltage and Frequency Scaling (DVFS) has been widely used for energy
optimization for servers in datacenters by leveraging the non-linear
relationship between power consumption and application throughput (Krzywda et
al., 2018; Weiser et al., 1996; Lo et al., 2015; Zhang et al., 2021). DVFS can
also be used for optimizing carbon efficiency where the application runs
faster using a higher frequency during low carbon periods and saves energy by
lowering the CPU frequency and its execution speed during high carbon periods,
possibly at a lower energy-efficiency. DVFS can especially be helpful for
uninterruptible applications that cannot be suspended, as it makes progress at
all times without suspension.

The energy savings in using DVFS come from the non-linear relationship between
a processor’s power demand ($P$) and its frequency ($f$) and voltage ($V$)
governed by the following equation,

(1) $P=CfV^{2}+P_{\texttt{static}}.$

Here, $C$ and $P_{\texttt{static}}$ are processor architecture-specific
constants. As shown in this equation, power demand has a dynamic and a static
range. The dynamic range is dictated by the linear relation with its
frequency; reducing the operating frequency by 50% will reduce the dynamic
range by 50%. However, higher savings in the dynamic range come from the non-
linear relationship with the operating voltage of the processor; decreasing
the operating voltage to half reduces the dynamic power consumption of the
processor by a factor of 4. It is worth mentioning that a decrease in the
power consumption of a processor does not lead to a proportional decrease in
its performance. The decrease in performance, denoted by $S$, depends on the
CPU-boundedness of applications and can be modeled using Amdahl’s law (Amdahl,
1967) by the following equation:

(2) $S=\frac{1}{io+\nicefrac{{(1-io)}}{{f_{n}^{\prime}}}}.$

where $io$ is the fraction of time an application spends accessing
Input/Output (IO) peripherals at the maximum operating frequency ($F_{max}$),
which is one of the major reasons affecting the application’s slowdown due to
their sequential nature. $f_{n}^{\prime}$ is the normalized frequency w.r.t.
the highest frequency $f_{n}^{\prime}=f_{n}/F_{max}$, where
$f_{n}\in[F_{\min},F_{\max}]$.

Considering only the dynamic range, by assuming $P_{static}$ to be 0 and $C$
to be 1, a 50% decrease in operating frequency for an application with 50% IO
yields only a 34% reduction in the application’s performance, making it more
efficient. While the reduction of frequency alone yields 50% savings in power,
more savings will be achieved if the operating voltage is decreased as well.
However, many modern processors do not allow direct and separate control of
the processor’s operating voltage. Instead, changing the operating frequency
alters the operating voltage to a pre-determined voltage level. As a result,
applications may not have a full range of parameters available to them to
optimize energy efficiency using DVFS. Furthermore, depending on the practical
values for $P_{static}$ and $C$, energy efficiency gains may be further
limited.

_1\. Experimental Setup._ We next evaluate the impact of DVFS for different
application characteristics under different operation frequencies to highlight
the tension between carbon and energy efficiency.

Figure 5. _Normalized energy efficiency across different application profiles
defined by their IO-intensiveness._

Server Configurations. Figure 5 shows our modeled server, modeled after a
local server in our lab, that has an Intel-Xeon Processor E5-2620 v4 with DVFS
enabled. The server dynamic power range was controlled through the frequency
range of (0.9 to 2.1GHz, 0.1 MHz step), voltage range of 0.8 to 1.2V. The
CPU’s transistor gate’s capacitance ($3\times 10^{-2}$), while the static
power of the server is 30W, which is approximately 25% of its operational
power. In practice, frequency levels and voltage values are tied together.
Thus, we split the voltage range into the same number of steps as frequency
and establish a direct relationship between frequency and voltage levels.

Applications. We model three different applications that map to real-world:
“CPU-bound” application such as matrix multiplication in ML training (0% time
spent on input/output), “IO-bound”application of text processing, e.g., Hadoop
(70% time spent on I/O), and “balanced” application such as in-memory data
processing, e.g., Spark, (40% time spent on I/O). In all of these examples,
I/O time is configured when the processor is running at the highest frequency.
The application-specific energy efficiency profile is created based on its
I/O%, under different frequencies, by equations 1 and 2.

Policy. There is no prior work on leveraging DVFS to optimize for carbon
efficiency. Therefore, we devise a simple strategy to explore the carbon and
energy efficiency trade-off. Our policy uses the application-specific profile
to operate at a high frequency, often less energy efficient, during low carbon
periods and operate at a low frequency, e.g., highest energy efficient
frequency, during high carbon periods. The complex decision space necessitated
evaluating the policy against all frequency permutations. In this case, the
policy is given all permutations of $F_{1},F_{2}\in[900,...,2100]$, and we
also use the mean carbon intensity $\mu_{c}$, during the expected execution
period, as the threshold. In this case, at a time slot $i$, the application
runs at frequency $F_{1}$ if the carbon intensity $c_{i}$ is less than or
equal to the threshold $\mu$ ($c_{i}\leq\mu$), and it runs at frequency
$F_{2}$ otherwise.

_2\. Experimental Results._ We model the energy efficiency behavior of our
applications by computing the normalized energy consumption at the highest
frequency with respect to other frequencies. Figure 5 shows that across
application classes, I/O-bound applications observe the most gains since an
I/O-heavy application does not utilize the CPU to its full extent and is not
affected by the slower processing speed of the CPU at lower frequencies, while
a CPU-bound application barely sees any gains as its throughput is highly
affected by the processing speed. The efficiency gains from DVFS were further
in prior work (Le Sueur and Heiser, 2010).

Figure 7 shows the carbon and energy efficiency, of the three applications
denoted as CPU-bound (0% IO), IO-Bound (70% IO), and balanced (40% IO). The
results clearly indicate that energy-efficient configurations do not always
yield the highest carbon efficiencies. For example, Figure 7(a) shows that the
highest carbon efficiency is achieved by running fast ($\sim$1.7GHz) when
energy’s carbon intensity is low while running slow ($\sim$1GHz) otherwise,
contrarily, always running at ($\sim$1.3GHz) yields highest energy efficiency.
Figure 7(c) shows another example where energy and carbon efficiency are more
correlated as the energy and carbon efficiency increase from lowering the
frequency. We point out that other configurations resulted in similar
conclusions, but we had to leave them out due to space constraints.

_3\. Key Takeaways. Using DVFS in a carbon-aware manner can greatly improve
carbon efficiency. Adjusting the operating frequency can result in high-
efficiency gains that might bridge the gap between energy and carbon-efficient
computing._

(a) CPU-bound Task

(b) Balanced Task

(c) IO-bound Task

Figure 7. _Carbon and energy efficiency of different tasks._

###  2.4. Spatial Shifting

Migrating services across the network in order to optimize cost or latency has
been widely discussed (Wood et al., 2011; Shen et al., 2016; Lemay et al.,
2012; Sukprasert et al., 2023). Similarly, migrations can be utilized to
increase carbon efficiency by transferring jobs to a region where the carbon
intensity of energy is lower. For example, a task can be migrated across the
globe by following the availability of carbon-free solar energy. However,
flexibly transferring jobs between locations decreases energy efficiency as it
involves energy overheads from checkpointing, transferring, and restoring
execution state as well as application data. For instance, for migrating a
data processing application (e.g., ML training), the application state must be
checkpointed at the source, moved across the network, and restarted at the
destination. Also, the data must be moved or cloned in both locations which
incurs extra energy consumption. The process of checkpointing and restoring
depends on the application size as explained in section 2.1, while the
migration depends on the state and data size, and cloning also comes with
energy and financial cost overheads. A full analysis of spatial shifting
trade-offs is left to future work.

##  3\. Conclusion

For a long-time, energy efficiency has been a key objective for cost-effective
and sustainable computing. The necessity to decrease computing’s operating
costs and the environmental impact of computing made energy efficiency a
first-class citizen in computing. However, the wide adoption of clean energy
in electrical grids, along with increasing public awareness about energy
sources, and the enabled visibility of the time-varying carbon intensity, has
resulted in a shift where the most energy-efficient operations may no longer
be considered the most sustainable or socially acceptable choice. For these
reasons, carbon efficiency (the amount of work per unit of carbon) appeared as
a “true” sustainability metric. The key idea in increasing carbon efficiency
is to exploit computing’s workloads flexibility by adjusting execution time
(Temporal Shifting), speed (Scaling and Rate Shifting), and location (Spatial
Shifting) according to the grid’s carbon intensity. In this paper, we
highlighted an inevitable tension between carbon and energy efficiency. We
explored the core mechanisms used in carbon-efficient computing along with
policies from the state-of-the-art in a wide range of scenarios. The paper
demonstrated qualitatively and quantitatively that “striving for maximum
energy efficiency is not always the most sustainable (carbon-efficient)
approach”. The gains and overheads of combining multiple carbon-aware
flexibility mechanisms is left for future work.

## Acknowledgements

We thank the HotCarbon reviewers for their valuable comments, which improved
the quality of this paper. We also thank WattTime and electricityMap for
providing the carbon-intensity data. This research is supported by NSF grants
2213636, 2136199, 2106299, 2102963, 2105494, 2021693, 2020888, 2045641, as
well as VMware.

## References

  * (1)
  * war (2014) 2014\.  The War of the Currents: AC vs. DC Power.  https://www.energy.gov/articles/war-currents-ac-vs-dc-power.
  * car (2022) 2022\.  Annual Electric Power Industry Report.  https://www.eia.gov/electricity/data/eia861/
  * iea (2022a) 2022a.  Global Trends in Internet Traffic, Data Centre Workloads and Data Centre Energy Use, 2010-2019.  https://www.iea.org/data-and-statistics/charts/global-trends-in-internet-traffic-data-centre-workloads-and-data-centre-energy-use-2010-2019.
  * ghg (2022) 2022\.  Greenhouse Gas Protocol.  https://ghgprotocol.org/.
  * iea (2022b) 2022b.  Share of Cumulative Power Capacity by Technology, 2010-2027.  https://www.iea.org/data-and-statistics/charts/share-of-cumulative-power-capacity-by-technology-2010-2027.
  * goo (2023) 2023\.  24/7 by 2030: Realizing a Carbon-free Future.  https://www.gstatic.com/gumdrop/sustainability/247-carbon-free-energy.pdf.
  * ele (2023) 2023\.  Electricity Map.  https://www.electricitymap.org/map.
  * war (2023) 2023\.  War of the Currents.  https://en.wikipedia.org/wiki/War_of_the_currents.
  * Acun et al. (2023) Bilge Acun, Benjamin Lee, Fiodar Kazhamiaka, Kiwan Maeng, Udit Gupta, Manoj Chakkaravarthy, David Brooks, and Carole-Jean Wu. 2023\.  Carbon Explorer: A Holistic Framework for Designing Carbon Aware Datacenters. In _Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_.
  * Amdahl (1967) Gene M Amdahl. 1967\.  Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities. In _Proceedings of the Spring Joint Computer Conference_.
  * Bangalore et al. (2023) Srini Bangalore, Arjita Bhan, Andrea Del Miglio, Pankaj Sachdeva, Vijay Sarma, Raman Sharma, and Bhargs Srivathsan. 2023.  Investing in the Rising Data Center Economy.  https://www.mckinsey.com/industries/technology-media-and-telecommunications/our-insights/investing-in-the-rising-data-center-economy.
  * Bashir et al. (2023) Noman Bashir, David Irwin, and Prashant Shenoy. 2023\.  On the Promise and Pitfalls of Optimizing Embodied Carbon. In _Proceedings of the 2nd Workshop on Sustainable Computer Systems (HotCarbon)_.
  * Bashir et al. (2022) Noman Bashir, David Irwin, Prashant Shenoy, and Abel Souza. 2022.  Sustainable Computing – Without the Hot Air. In _Proceedings of the First Workshop on Sustainable Computer Systems Design and Implementation (HotCarbon)_.
  * Chien (2021) A. Chien. 2021.  Driving the Cloud to True Zero Carbon.  _CACM_ 64, 2 (February 2021).
  * Dodge et al. (2022) Jesse Dodge, Taylor Prewitt, Remi Tachet des Combes, Erika Odmark, Roy Schwartz, Emma Strubell, Alexandra Sasha Luccioni, Noah A. Smith, Nicole DeCario, and Will Buchanan. 2022\.  Measuring the Carbon Intensity of AI in Cloud Instances. In _2022 ACM Conference on Fairness, Accountability, and Transparency_ _(FAccT ’22)_.
  * Gupta et al. (2022) Udit Gupta, Mariam Elgamal, Gage Hills, Gu-Yeon Wei, Hsien-Hsin S. Lee, David Brooks, and Carole-Jean Wu. 2022.  ACT: Designing Sustainable Computer Systems with an Architectural Carbon Modeling Tool. In _ISCA_.
  * Gupta et al. (2021) Udit Gupta, Young Geun Kim, Sylvia Lee, Jordan Tse, Hsien-Hsin S Lee, Gu-Yeon Wei, David Brooks, and Carole-Jean Wu. 2021\.  Chasing Carbon: The Elusive Environmental Footprint of Computing. In _2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. IEEE.
  * Hanafy et al. (2023) Walid A Hanafy, Qianlin Liang, Noman Bashir, David Irwin, and Prashant Shenoy. 2023.  CarbonScaler: Leveraging Cloud Workload Elasticity for Optimizing Carbon-Efficiency.  _arXiv preprint arXiv:2302.08681_ (2023).
  * Krzywda et al. (2018) Jakub Krzywda, Ahmed Ali-Eldin, Trevor E Carlson, Per-Olov Östberg, and Erik Elmroth. 2018\.  Power-Performance Tradeoffs in Data Center Servers: DVFS, CPU Pinning, Horizontal, and Vertical scaling.  _Future Generation Computer Systems_ (2018).
  * Le Sueur and Heiser (2010) Etienne Le Sueur and Gernot Heiser. 2010.  Dynamic Voltage and Frequency Scaling: The Laws of Diminishing Returns. In _Proceedings of the 2010 International Conference on Power Aware Computing and Systems_.
  * Lechowicz et al. (2023) Adam Lechowicz, Nicolas Christianson, Jinhang Zuo, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, and Prashant Shenoy. 2023.  The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting.  _arXiv preprint arXiv:2303.17551_ (2023).
  * Lemay et al. (2012) Mathieu Lemay, Kim-Khoa Nguyen, Bill St. Arnaud, and Mohamed Cheriet. 2012.  Toward a Zero-Carbon Network: Converging Cloud Computing and Network Virtualization.  _IEEE Internet Computing_ (2012).
  * Lo et al. (2015) David Lo, Liqun Cheng, Rama Govindaraju, Parthasarathy Ranganathan, and Christos Kozyrakis. 2015\.  Heracles: Improving Resource Efficiency at Scale. In _2015 ACM/IEEE 42nd Annual International Symposium on Computer Architecture (ISCA)_.
  * Masanet et al. (2020) Eric Masanet, Arman Shehabi, Nuoa Lei, Sarah Smith, and Jonathan Koomey. 2020.  Recalibrating Global Data Center Energy-use Estimates.  _Science_ (2020).
  * Patterson et al. (2022) David Patterson, Joseph Gonzalez, Urs Hölzle, Quoc Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. 2022\.  _The Carbon Footprint of Machine Learning Training Will Plateau, Then Shrink_.  Technical Report. Google Inc.
  * Patterson et al. (2021) David Patterson, Joseph Gonzalez, Quoc Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. 2021.  _Carbon Emissions and Large Neural Network Training_.  Technical Report. arXiv.
  * Qi et al. (2017) Hang Qi, Evan R. Sparks, and Ameet Talwalkar. 2017.  Paleo: A Performance Model for Deep Neural Networks. In _Proceedings of the International Conference on Learning Representations_.
  * Radovanović et al. (2023) Ana Radovanović, Ross Koningstein, Ian Schneider, Bokan Chen, Alexandre Duarte, Binz Roy, Diyue Xiao, Maya Haridasan, Patrick Hung, Nick Care, Saurav Talukdar, Eric Mullen, Kendal Smith, MariEllen Cottman, and Walfredo Cirne. 2023.  Carbon-Aware Computing for Datacenters.  _IEEE Transactions on Power Systems_ (2023).
  * Sharma et al. (2016) Prateek Sharma, Tian Guo, Xin He, David Irwin, and Prashant Shenoy. 2016.  Flint: Batch-Interactive Data-Intensive Processing for Transient Servers. In _ACM European Conference on Computer Systems (EuroSys)_.
  * Shen et al. (2016) Zhiming Shen, Qin Jia, Gur-Eyal Sela, Ben Rainero, Weijia Song, Robbert van Renesse, and Hakim Weatherspoon. 2016.  Follow the Sun through the Clouds: Application Migration for Geographically Shifting Workloads. In _Proceedings of the Seventh ACM Symposium on Cloud Computing_.
  * Souza et al. (2023) Abel Souza, Noman Bashir, Jorge Murillo, Walid Hanafy, Qianlin Liang, David Irwin, and Prashant Shenoy. 2023.  Ecovisor: a Virtual Energy System for Carbon-Efficient Applications. In _Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_.
  * Sukprasert et al. (2023) Thanathorn Sukprasert, Abel Souza, Noman Bashir, David Irwin, and Prashant Shenoy. 2023\.  Quantifying the Benefits of Carbon-Aware Temporal and Spatial Workload Shifting in the Cloud.  arXiv:2306.06502 [cs.DC]
  * Switzer et al. (2023) Jennifer Switzer, Gabriel Marcano, Ryan Kastner, and Pat Pannuto. 2023.  Junkyard Computing: Repurposing Discarded Smartphones to Minimize Carbon. In _ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)_.
  * Weiser et al. (1996) Mark Weiser, Brent Welch, Alan Demers, and Scott Shenker. 1996\.  Scheduling for Reduced CPU Energy.  _Mobile Computing_.
  * Wiesner et al. (2021) Philipp Wiesner, Ilja Behnke, Dominik Scheinert, Kordian Gontarska, and Lauritz Thamsen. 2021\.  Let’s Wait Awhile: How Temporal Workload Shifting Can Reduce Carbon Emissions in the Cloud. In _Proceedings of the 22nd International Middleware Conference (Middleware)_.
  * Wood et al. (2011) Timothy Wood, K.K. Ramakrishnan, Prashant Shenoy, and Jacobus Van der Merwe. 2011.  CloudNet: Dynamic Pooling of Cloud Resources by Live WAN Migration of Virtual Machines. In _International Conference on Virtual Execution Environments (VEE)_.
  * Zhang et al. (2021) Chaojie Zhang, Alok Kumbhare, Ioannis Manousakis, Deli Zhang, Pulkit Misra, Rod Assis, Kyle Woolcock, Nithish Mahalingam, Brijesh Warrier, David Gauthier, Lalu Kunnath, Steve Solomon, Osvaldo Morales, Marcus Fontoura, and Ricardo Bianchini. 2021.  Flex: High-Availability Datacenters With Zero Reserved Power. In _Proceedings of the International Symposium on Computer Architecture (ISCA)_.