]Emeritus Professor, Physics, Westminster College, Salt Lake City, UT,
<EMAIL_ADDRESS>
# Spawning Nodes Generate Deterministic Scale-Free Networks

Peter R. Conwell  [  Kaushik Chakram  Valeria J. Villegas-Medina

(5/25/2013)

###### Abstract

In this paper we present a deterministic vertex spawning model that yields a
scale-free network. The model specifies that a parent vertex produces a child
vertex in a time interval approximately proportional to the current time and
inversely proportional to the number of edges currently connected to the
parent. Spawned offspring maintain an undirected edge with its parent. No
information about the network as a whole is required to obtain scale-invariant
behavior. Although the algorithm is deterministic, the number of nodes
spawning in a small time interval quickly becomes randomized. We show
theoretically and with simulations that such a spawned network will have a
degree distribution obeying a power law with exponent 2.5. Simulations show
that the distribution matches a Zipf distribution.

##  I Introduction

Viewed through a certain lens almost any aggregate object, physical or
abstract, can be seen as a network of simple nodes (vertices) and the
connections between them (edges). Such a network perspective can be a
propitious tool to describe generalized topology, growth, and aggregation of
disparate entities ranging from the organization of the internet to social
interactions. Indeed, network research has become a discipline in and of
itself. Barabasi2016NetworkScience ,dorogovtsev2013evolution ,mej2010networks

Albert-László Barabási and Réka Albert seemingly initiated a phase transition
in network research with their 1999 $Science$ article barabasi1999emergence .
They re-discovered that networks evolving with new nodes attaching
preferentially to existing nodes obey a power law distribution

$p_{k}=Ck^{-\alpha},$ (1)

where $p_{k}$ is the probability of a node having $k$ connections, $C$ is a
normalization constant, and $\alpha=3$. Networks that have a power law
distribution are said to be scale-free or scale-invariant. The key feature of
a scale-free network is the long tail of the distribution. This means that
there are nodes, albeit sparse, that have a large number of connections. In
general, scale-invariance implies that there exists a fundamental relation
that doesn’t change when some independent variable is multiplied by constant.
This is evident in equation 1: if $k$ is scaled by an arbitrary constant, the
only factor that changes is the normalization constant $C$. Scale invariance
is a symmetry. Like any symmetry, it simplifies the attendant model of any
physical systems it represents.

Barabási and Albert’s Science article, with its emphasis on the scale-
invariant symmetry of power law distributions, struck a chord with physicists
primed by the simplicity of scale-invariant symmetries wilson1979problems .
They found that the scale-free property emerged from two biases. First, nodes
are linked to existing nodes, consequently older nodes receive more
connections. This first bias is a natural consequence of any evolving network
where the growth consists of a steady addition of new nodes and their
subsequent connections. Second, the new connections are attached to existing
nodes with a probability proportional to the number of connections preexisting
on a potential target. This latter bias they dubbed preferential-linking. As
preferential linking is probabilistically dependent on the degree of
connections of the existing nodes, it implies that global knowledge is
available and utilized in order to make new attachments.

Barabási and Albert were not the first to recognize the applicability of power
law distributions to a wide assortment of natural phenomenon. In fact,
Barabási discusses the history of the mathematics and applications of power
law distributions that preceded the 1999 paper in (Barabasi2016NetworkScience
pp. 116, 189). Particularly relevant are Herbert Simon’s investigations of
distributions, like power laws, that have long tailssimon1955class . Derek de
Solla Price was perhaps the first to utilize preferential-linking in a network
model (price1965networks ,price1976general ) of scientific citations, and he
highlighted the power law behavior. Mark Newman presented a cogent and
detailed re-examination of the Price model, in (mej2010networks  pp 487-513).

Vázquez PhysRevE.67.056104  and Nather, et al. nather2009hierarchy  have
presented models of evolving networks with local rules. In nather2009hierarchy
Nather et al demonstrate a model that is scale-free and yields hierarchical
clustering. Similarly, in the model by Vázquez, nodes are connected to
previous nodes in the neighborhood of the new node. The networks generated are
also scale-free and demonstrate a natural clustering hierarchy. In both of
these models connections are made probabilistically to nearby nodes.
Consequently they require knowledge of their neighborhood. In contrast, our
intent is to eliminate $any$ requirement for knowledge of external topology.
The only local connections in our network are the connection from the parent
to a child and vice versa.

Here we present a local, deterministic, scale-invariant growth model that is
neither probabilistic in how connections are made nor one that require global
knowledge of the connection degree of any other nodes. This new model
satisfies a different sort of preferential attachment. Nodes are spawned by
existing nodes at a rate approximately proportional to the number of
connections possessed by the parent and inversely proportional to time elapsed
since the initial birth of the first node. Nodes with more connections spawn
faster. Our intent with this scheme was to eliminate any requirement for
knowledge of external topology and still obtain scale-invariant symmetry. In
particular, we were drawn to the idea that offspring could offer positive
reproductive feedback. The only local connections in our network are the
parent to child and vice versa. Consequently, if the connection to an
offspring provided additional reproductive energy, a parent’s fecundity
increases. Figure 1 shows such a constructed network of one hundred nodes.

This idea of rapid unlimited nodal growth by nodes giving birth to new nodes
was inspired by inflation models of the early universe. From an energy
perspective, the $fuel$ for the enhanced growth in our model has to come from
some infinitely large $nutrient$ rich environment. Similarly, In inflationary
models, the energy density is fixed by a scalar field which provides the fuel
for the expansion. This runs contrary to the usual conception that density is
inversely proportional to volume. For a pedestrian view see
(guth1998inflationary, , p. 170))

Figure 1: A spawned network of one hundred nodes. The node with the most
connections, roughly centered in the figure, is node 1, the seed node. The
node just to its right is node 2.

Ours is not the only scale-free deterministic model. In
barabasi2001deterministic , Barabási et al. demonstrate a clever copying
scheme. As the network grows, patches of the network are copied and attached
to the existing network.The resulting network has a degree exponent of
$\alpha=\frac{\log(3)}{\log(2)}$. Obviously, this scheme requires knowledge of
previous parts of the current network.

In the next section we present the model details and simulations. In section
III, we discuss the theoretical underpinnings, in IV we show the results of
the simulations and compare them with theoretical predictions of the degree
distributions, and in V we offer conclusions and a review.

##  II  model simulation

We simulated the model using the methods outlined by Newman in mej2010networks
(pp. 282-290). The simulation software maintains the network by labeling every
new node with an integer and notes whenever that node spawns. At time $t=1$ we
assume that node 1 simply exists and is a starting seed for the network.
Further, we assume that node 1 birthed node 2 at $t=2$, and they are connected
with an undirected link. Thus, the simulation begins at $t=3$ with the two
connected nodes. Node 1 is initialized to spawn at $t=3$; node 2 at $t=4$. At
each subsequent time step all existing nodes are examined to see if they are
ready to spawn. Every node has an internal countdown timer. When a node is
examined, and its timer is zero, the following occurs: 1) a node spawns a new
node, 2) the parent’s timer is reset to be current time divided by the number
of connections of the parent minus one. 3) As it has no previous connections,
the child’s count-down timer is set to be proportional to the current time
minus one. 4) an undirected edge is established between the parent node and
offspring. 5) During this examination of all nodes, nodes that don’t spawn
have their timers decremented by one. After all the nodes are examined for the
possibility of spawning, external time is incremented by one.

For example, consider the timeline of node 2 just after it spawns at time
$t=4$. It has one prior connection—the connection from node 1. Therefore node
2’s timer is set to $4/1-1=3$. It will spawn again when its timer decrements
to zero. Misleadingly, because the simulation is serialized, it requires four
time steps until it spawns again. On the third subsequent time increment, at
$t=7$, the timer steps down to zero. However, it is not discovered until the
clock ticks one more time, and all nodes are examined to see if their timer is
zero. So, node 2 will spawn again when $t=8$.

Figure 2 shows the raw result of a simulation in the form of a log-log plot of
the number of connections verses the node label. The simulation generated a
total 1 million nodes. Since many nodes can be produced in a single external
time step, only about 30,000 such steps are required to produce a network of
this size.

Figure 2: Log-Log Plot of Number of Connections vs. Node Label. The 1st, 2nd,
and 3rd nodes are highlighted in red.

The deterministic nature of the model is evident by examining the spawning
times of individual nodes. Let $T(n)$ be the time of a node spawning for the
$n_{th}$ time. Since a node acquires another connection when it spawns, $n$ is
also equal to the number of connections. Following the description of model,
the relation between the time of the $n_{th}$ spawning and the previous
spawning time is given by the recursion relation

$T(n)=T(n-1)+\frac{T(n-1)}{n-1}.$ (2)

With the specification of the first spawning time, we can use Eq.(2) to find
the time of spawning of any offspring of any node. As an example we can
compute the $4_{th}$ spawning time of the second node. The initial spawning
time of node 2 is 4, so $T(1)=4$. Applying Eq(2) once gives the second
spawning time 8, twice gives 12, and three times 16, thus $T(4)=16$. In fact,
if $T(1)=T_{0}$ is the first spawning time of a node, then it is readily seen
that $T(n)=nT_{0}$ is the $n_{th}$ spawning time.

##  III Theory

In this section, we leverage the theory behind the model developed by Derek de
Solla Price in the 1970s price1976general  and in Newman’s master equation
alternative analysis to the Price model in $Networks$ (mej2010networks  pp.
487-495). Price’s picturesque analogy of negatively decaying atoms mirrors our
spawning nodes. We also leaned on Newman’s analysis of the Yule process in
Newman2006Power-Laws .

Let $n$ be the total number of nodes in the network at the current time. In
the usual way we separate the overall collection of nodes into non-overlapping
sets. Every node in a set has the same number of connections. Different sets
have nodes with a different number of connections, $q$. By the nodes spawning,
the set with $q$ connections feeds the set of nodes with $q+1$ connections,
while gaining nodes from the set with $q-1$. Whenever any node spawns in any
of the sets, the child enters the set of $q=1$. This $q=1$ set loses members
to the $q=2$ set whenever any of its members spawn. Because it contains all
the most recent offspring, this set will always have the most members.
Subsequently, we will develop an expression of the $degree$ $distribution$:
the fraction of all nodes in each set. Let $p_{q}(n)$ be that distribution.

Consider the case when a single node in any set spawns. First note that the
population of the entire network increases by one. Second, a spawning parent
automatically receives a connection from its offspring. Consequently, a parent
node will move from a set of nodes with $q$ connections to the set of nodes
with $q+1$. As we discussed in the previous section, the time interval before
the next spawning is approximately proportional to the current time divided by
the number of connections. Therefore, the $spawning$ $rate$, the inverse of
that time interval, will be approximately proportional to the number of
connections divided by the current time. Any node with the same number of
connections is equally likely to spawn in some short time interval. The more
connections a node has, the higher the likelihood of it spawning. However, the
probability of a node spawning cannot be strictly proportional to the number
of connections. (This issue is discussed at length in mej2010networks  and in
price1976general .) The probability of a spawning must be proportional to the
number of connections plus some additive constant: $q+a$. In our case $a=1$.)
To normalize the probability of a node spawning, we divide by the sum over all
the nodes in the network plus one. Thus, the probability of a node spawning is

$\frac{q+1}{\sum_{i}^{n}(q_{i}+1)}=\frac{q+1}{\sum_{i}^{n}q_{i}+\sum_{i}^{n}1}.$
(3)

We can simplify this result by utilizing the average number of connections per
node. Let $Q$ be the total number of connections for all nodes. From our
simulations, with $N=1,000,000$, we have $Q=\sum_{i=1}^{N}q_{i}=1,999,998$.
So, $<q>=2$. Eq.(3) then becomes

$\frac{q+1}{2n+n}.$ (4)

The denominator of Eq.(4) then becomes $3n$ and the probability of a node
spawning is

$\frac{q+1}{3n}.$ (5)

If the average number of connections per node is two, then the anticipated
number of new connections due to nodes spawning is

$2\frac{q+1}{3n}.$ (6)

From the definition of $p_{q}(n)$ as the fraction of nodes that have q
connections, we see that there are $np_{q}(n)$ nodes within a set of nodes
with q connections. Consequently, the assumed number of spawnings within some
small time interval for nodes with $q$ connections is

$np_{q}(n)2\frac{(q+1)}{3n}=\frac{2(q+1)}{3}p_{q}(n).$ (7)

Reiterating: when parent nodes with $q-1$ connections spawn they move from the
set of nodes with $q-1$ connections to the set of nodes with $q$ connections.
Therefore, the expected number of nodes that make this jump and add to the set
of q connections is

$\frac{2}{3}qp_{q-1}(n).$ (8)

Similarly, the expected number of nodes in the set with $q$ connections that
will be lost will be

$\frac{2(q+1)}{3}p_{q}(n).$ (9)

The change in the number of nodes for the set with nodes of $q$ connection is
then the number of nodes that jump into the set minus the number of nodes that
jump out of the set:

$(n+1)p_{q}(n+1)-np_{q}=\frac{2}{3}qp_{q-1}(n)-\frac{2(q+1)}{3}p_{q}(n).$ (10)

Eq.(10) is the master equation for our spawning process. It is valid for all
values of $q$ greater than 1. By first letting
$n\rightarrow\nolinebreak\infty$, we iterate Eq.(10) with an appropriate
initial value for $p_{1}$ to generate an asymptotic form of $p_{q}$.
(Notionally we will indicate this transition to large $n$ by simply writing
$p_{q}$ instead of $p_{q}(n)$.)

For the initial case of $q=1$, we gain a child node when any node in the
network spawns, thus the first term on the right in Eq.(10) is simply one. The
initial condition is then

$p_{1}=1-\frac{4}{3}p_{1},$ (11)

or

$p_{1}=\frac{3}{7}.$ (12)

We can also rearrange and simplify Eq.(10) to get

$p_{q}=\frac{q}{\frac{5}{2}+q}p_{q-1}$ (13)

We iterate Eq(13) starting with $p_{1}=\frac{3}{7}$. Two constants,
$\mu=\frac{7}{2}$ and $\delta=\frac{3}{7}$, facilitates recognizing and
simplifying patterns. The resulting expression after iterating is:

$p_{q}=\frac{\delta(1+1)(1+2)(1+3)\cdots(1+(q-1))}{\frac{1}{\mu}(\mu+1)(\mu+2)(\mu+3)\cdots(\mu+(q-1)}.$
(14)

Gamma functions with integer arguments are often associated with expression
like that in Eq.(14). For example, we can use the identity below, Eq.(15) (see
abramowitz1965handbook  pg. 256),

$x(x+1)(x+2)\cdots(x+n-1)=\frac{\Gamma(x+n)}{\Gamma(x)},$ (15)

to transform and simplify Eq.(14) into expressions involving gamma functions.
With this identity equation 14 becomes

$\mu\>\delta\>\frac{\Gamma(1+q)\Gamma(\mu)}{\Gamma(\mu+q)},$ (16)

where we have used $\Gamma(1)=1.$

The asymptotic form we seek is easier to find if we convert some of the gamma
functions to beta functions using the identity,

$\Gamma(x+y)=\frac{\Gamma(x)\Gamma(y)}{\mathrm{B}(x,y)}.$ (17)

Applying Eq.(17) to Eq.(16) yields,

$\mu\>\delta\>\frac{\mathrm{B}(\mu,q)}{\mathrm{B}(1,q)}.$ (18)

When $x$ is large and $y$ is fixed, the asymptotic form of the beta function
is $\mathrm{B}(x,y)\sim\Gamma(y)x^{-y}$ . Using this result in Eq.(18) with
$q$ large, we get

$\mu\>\delta\>\Gamma(\mu)\>q^{1-\mu}.$ (19)

Substituting the values of the constants, and
$\Gamma(\frac{7}{2})=\frac{15\sqrt{\pi}}{8}$ into Eq.(19), we obtain the
asymptotic form for $p_{q}$,

$p_{q}\sim\frac{45\sqrt{\pi}}{16}\>q^{-\frac{5}{2}}.$ (20)

For large values of $q$ Eq.(20) shows the classic power law behavior with
$\alpha=2.5$.

##  IV  Results

The simulation aggregates nodes with the same number of connections into sets.
Consequently, we can explicitly examine the growth of these sets. In
particular, we study their overall growth rate and how set membership changes
per unit time.The simulation shows that the number of nodes from all sets
increases slowly initially then accelerates obeying the power law,

$y=0.27t^{1.46}.$ (21)

With successively decreasing importance, nodes with the smallest number of
connections dominate overall network growth. For instance, nodes with just one
connection provide about 60% of the nodes out of a total of $1,000,000$. Nodes
with two connections provide 7% of the total. Since the overall network growth
obeys a power law, it is not surprising that the nodal growth of individual
sets of nodes with the same number of connections show similar behavior. For
instance, growth for nodes in the set with two connections obey the power law

$y=0.018t^{1.47}.$ (22)

Even though our model is deterministic, the results can be quasi-random.
Unlike the behavior of some non-linear dynamical systems, where chaotic
behavior is caused by sensitivity to initial conditions, the randomness in our
model is a consequence of the inter-generational mixing of birthing times.
Because nodes are likely to have a different number of connections, the timing
of new births intermingle. For example, four new nodes are born at $t=54$.
Node 1 gives birth to its $18$th offspring, node 94; node 3 gives birth to its
$9$th offspring, node 95; node 9 gives birth to its 4th offspring, node 96;
and node 37 gives birth to its second offspring, node 97. However, at $t=53$
their are no births. Consequently, without the maintenance of a detailed log
of when every node is born and its spawning times, as the computer code
provides, it is difficult to predict when a particular time step has no
births, or 260 births. Figure 4 offers a glimpse of this noise like behavior.
It shows the number of nodes produced during each unit time step over the span
of $t=1000$ to $t=5000$. In this time range the number of nodes produced in a
unit time step vary from 0 to 260. We also generated an empirical
distribution. (An empirical distribution is a non-parametric way of
establishing a distribution-like object based on empirical data.) of the
number of nodes produced in 30,000 time steps—the approximate number of time
steps required to produce $1,000,000$ nodes. The distribution has a mean of 32
and a standard deviation of 440 nodes spawned. Figure 5 shows a histogram of
1000 random deviates taken from the this distribution. Note that histogram
shows a long tail. Unfortunately the distribution is not characterized simply
by known distributions.

Figure 3: Network Growth. Overall network growth shown in dotted blue with
power law curve fit in solid green. Growth of nodes in the set with two
connections is shown in dotted purple with power law curve fit in solid red
line. (The growth of the total number of nodes looks as though it would exceed
1,000,000 nodes in much less time than is actually the case. This is
misleading. For $y=1,000,000$ and solving for time in Eq.(21) yields
$x=31,554$ which is consistent with our simulations.) Figure 4: Number of
nodes spawned per unit time from $t=1000$ to $t=2000$.  Figure 5: Histogram of
the frequency of births of nodes per unit time.

The simulation provides a list of the number of connections for each node.
Recall that each node is labeled in the order it was produced. The older nodes
always have more connections. Therefore the list is automatically sorted by
the decreasing number of connections. This was shown in the log-log graph in
figure 2. The negative sloping straight line of this graph strongly hints that
the network’s degree distribution obeys a power law. We generated another
empirical distribution from this list and took random variates to examine the
resulting degree distribution.

Given this automatic sorting of the most connected nodes to the least
connected, it would seem that the Zipf distribution is a natural choice for
the resulting distribution. The inception of Zipf’s law comes from the
observation by George Zipf that if words in any written language are sorted by
the most frequently used to the least used their ranking follows a power law.
(schroeder2009fractals  pp. 35-37) More formally, the Zipf distribution is a
discrete distribution with a long tail. Equation 23 shows its probability mass
function.

$f(x)=\frac{x^{-(\rho+1})}{\sum_{i=1}^{n}x_{i}^{(\rho+1)}},$ (23)

where $\rho$ is a parameter greater or equal to zero and n is a natural
number.

Assuming the results indicated we had degree distribution with a power law of
the form Eq.(1), we attempted the methods discussed in Clauset2009Power-Law
to identify the value of $\alpha$. These methods require that we omit some of
initial values of the data with a parameter $x_{min}$. However, we found the
methods unstable with respect to any value of this parameter. We also
attempted optimizing the fit of the Zipf distribution parameter to the data
using different statistical methods and even different discrete distributions
with long tails. These methods consistently pointed to a Zipf distribution
with a value for $\rho=1.32$. However, with this value of $\rho$ there was a
clear difference in a simple visual inspection on a log-log plot of one minus
the cumulative probability distribution (CDF) of samples of the Zipf
distribution and $1-CDF$ of samples of the empirical distribution of our
results. We are aware of the problems of relying on visual fits, nevertheless
we believe that the best value of $\rho$ is 1.5. From the probability mass
function Eq.(23) of the Zipf distribution, we see that a value of $\rho=1.5$
implies a power law distribution with an exponent of $\alpha=2.5$. This is
consistent with our results in III where we predicted a power law with
$\alpha=2.5$. The fit it offers we show in Eq.(6). In that figure we also show
the Zipf distribution with a parameter $\rho=1.3$.

Figure 6: Cumulative Distributions of the Spawning Model and the Zipf
Distribution with parameter 1.5.

##  V Conclusion

We have offered a new deterministic scale-invariant description of a unique
birthing process and the resulting network. This is a network formed solely by
undirected connections of parents to their children. It emerges from the
development of long chains of generations of offspring and the children of
those offspring. The older the nodes, the longer the chains, and the larger
the sub-network of offspring. The network develops without information being
shared between nodes. The only requirement is that parents modulate their
fecundity by making the time between births be approximately proportional to
the current time divided by the number of previous births. The power law
aspect of our model results simply from the requirement that nodes with more
previous births spawn more often.

Nodes must be able to maintain an internal clock in order to set their
spawning time. It is likely that the internal timers will need to be
synchronized. However, it is not clear to what extent the various features of
the model breakdown when the internal clocks between nodes deviate
significantly. It is possible that we have introduced unanticipated artifacts
because of the serial nature of the simulation. Conceivably, this could be
addressed by randomizing the inspection of node timers for each time step.
These explorations we save for future work. Also, we attribute the issues we
had with standard statistical methods to estimate the power law exponent to be
due to the unique features of our model. Our hypothesis is twofold. First, we
have a very small number of nodes with many connections. These make the
statistics unreliable for this part of the data. Second, whenever a simulation
is halted, be it for ten thousand nodes or one million nodes it is a hard
stop. There is always a large bolus of nodes on the verge of birthing in the
next time increment. We think this biases the statistics for nodes with few
connections. This too needs to be investigated further.

The authors acknowledge the help of John Hurdle MD,PhD in their preparation of
this document.

## References

  * [1] M. E. J. Newman Aaron Clauset, Cosma Rohilla Shalizi.  Power-law distributions in empirical data.  arXiv:0706.1062v2 physics.data-an, 2009.
  * [2] M Abramowitz.  Handbook of mathematical functions with formulas, graphs, and mathematical tables.  Published by General Publishing Company Ltd, Toronto, Canada, Dover Publications Inc., New York, USA, Card Nr. 65-12253, 1965.
  * [3] Albert-László Barabási.  Network Science.  Cambridge university press, 2016.
  * [4] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  Science, 286(5439):509–512, 1999.
  * [5] Albert-László Barabási, Erzsebet Ravasz, and Tamas Vicsek.  Deterministic scale-free networks.  Physica A: Statistical Mechanics and its Applications, 299(3-4):559–564, 2001.
  * [6] Sergei N Dorogovtsev and José FF Mendes.  Evolution of networks: From biological nets to the Internet and WWW.  OUP Oxford, 2013.
  * [7] Alan H Guth.  The inflationary universe: the quest for a new theory of cosmic origins.  Random House, 1998.
  * [8] Peter Náther, Mária Markošová, and Boris Rudolf.  Hierarchy in the growing scale-free network with local rules.  Physica A: Statistical Mechanics and its Applications, 388(24):5036–5044, 2009.
  * [9] M. E. J. Newman.  Power laws, pareto distributions and zipf’s law.  arXiv:0412004v3 cond-mat.stat-mech, 2006.
  * [10] Mark Newman.  Networks: an introduction.  Oxford University Press, Oxford, 2010.
  * [11] Derek de Solla Price.  A general theory of bibliometric and other cumulative advantage processes.  Journal of the American society for Information science, 27(5):292–306, 1976.
  * [12] Derek J De Solla Price.  Networks of scientific papers: The pattern of bibliographic references indicates the nature of the scientific research front.  Science, 149(3683):510–515, 1965.
  * [13] Manfred Schroeder.  Fractals, chaos, power laws: Minutes from an infinite paradise.  Courier Corporation, 2009.
  * [14] Herbert A Simon.  On a class of skew distribution functions.  Biometrika, 42(3/4):425–440, 1955.
  * [15] Alexei Vázquez.  Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations.  Phys. Rev. E, 67:056104, May 2003.
  * [16] Kenneth G Wilson.  Problems in physics with many scales of length.  Scientific American, 241(2):158–179, 1979.


11institutetext: School of Computer Science, Wuhan University, Wuhan, China
11email<EMAIL_ADDRESS>
22institutetext: Department of Electronics and Informatics, Federico Santa
María Technical University, Concepción, Chile
33institutetext: Faculty of Information Technology, Monash University,
Melbourne, Australia
44institutetext: Faculty of Information Technology, University of Jyvaskyla,
Jyvaskyla, Finland
55institutetext: College of Computer Science and Engineering, University of
Ha’il, Ha’il, Saudi Arabia

# A Decision Model for Selecting Patterns and Strategies to Decompose
Applications into Microservices

Muhammad Waseem1 Peng Liang1∗ Gastón Márquez2
Mojtaba Shahin3 Arif Ali Khan4 Aakash Ahmad5 Muhammad Waseem 11 Peng Liang
1*1* Gastón Márquez
Mojtaba Shahin 2233 Arif Ali Khan 44 Aakash Ahmad 55

###### Abstract

Microservices Architecture (MSA) style is a promising design approach to
develop software applications consisting of multiple small and independently
deployable services. Over the past few years, researchers and practitioners
have proposed many MSA patterns and strategies covering various aspects of
microservices design, such as application decomposition. However, selecting
appropriate patterns and strategies can entail various challenges for
practitioners. To this end, this study proposes a decision model for selecting
patterns and strategies to decompose applications into microservices. We used
peer-reviewed and grey literature to collect the patterns, strategies, and
quality attributes for creating this decision model.

###### Keywords:

Microservices System, Microservices Architecture, Decision Model,
Microservices Pattern, Quality Attribute

##  1 Introduction

Microservices Architecture (MSA) inspired by Service-Oriented Architecture
(SOA) has gained immense popularity in the past few years [1]. With MSA, an
application is designed as a set of business-driven microservices that can be
developed, deployed, tested, and scaled independently [15]. Organizations
adopt MSA due to better availability, scalability, productivity, performance,
fault-tolerance, and cloud support compared with SOA or monolithic
applications. It is argued that MSA can also help build autonomous development
teams [15].

Microservices systems entail a significant degree of complexity at the design
phase and runtime configurations from an architecture perspective [12].
Haselbock et al. [7] identified several design areas for microservices
systems, such as application decomposition, microservices security, and
communication. On the other hand, literature reviews (e.g., [17]), existing
practices (e.g., [19]), and exploratory studies (e.g., [18]) indicate several
challenges related to the design areas mentioned in [7], for instance, clearly
defining the boundaries of microservices, addressing their security concerns,
and managing the communication between a large number of microservices.

Both academia and industry have presented reusable solutions for microservices
systems in the form of patterns and strategies. These patterns and strategies
are currently distributed across different publications (e.g., scientific and
grey literature). The practitioners need to navigate pattern to pattern (and
strategy) until a suitable combination of patterns (and strategies) that can
address the challenges is found. Moreover, the practitioners cannot find a
holistic view of the patterns and strategies for a trade-off analysis (e.g.,
patterns influence Quality Attributes (QAs)). According to the recent studies
(e.g., [17][18][19]), most of the design, development, monitoring and testing
challenges are raised when application is decomposed into microservices. To
this end, we present a decision model that assists practitioners in selecting
appropriate patterns and strategies for decomposing applications into
microservices. Decision models are a structured way of exploring the problem
and solution space to achieve the design goal [10]. The proposed decision
model has been developed based on a mini multivocal literature review through
reviewing the scientific and grey literature.

Paper Organization: Section 2 describes decision models and modeling nations;
Section 3 presents the details of the application decomposition decision
model; Section 4 discusses the threats to validity; Section 5 presents related
work; Section 6 concludes this work with future research directions.

##  2 Modeling Decision Model

The decision models in software architecture are used to map elements of the
problem space to elements of the solution space [10]. The problem space
represents functional and non-functional requirements, whereas the solution
space represents design elements [10]. To create decision models for
microservices systems, we represent the problem space as a set of QAs and the
solution space as a set of microservices patterns and strategies. We developed
the decision model for application decomposition because most of the design,
development, monitoring, testing, and deployment challenges in microservices
systems are rooted in this area ([17][18][19]). We collected required
patterns, strategies, QAs, and impact of patterns on QAs for creating the
decision model based on a mini multivocal literature review.

Fig. 1 presents the notations used in the decision model presented in this
paper. We used Inclusive, Exclusive, and Parallel gateways of Business Process
Model and Notation (BPMN) for indicating the decision flow. An MSA design area
is represented through grey box. A circle is used to denote the start of a
decision process. An Inclusive gateway is used to trigger more than one
outgoing paths within a decision process. An Exclusive gateway is used to
trigger one of the outgoing paths. In contrast, A Parallel gateway represents
the multiple parallel outgoing paths within a decision process. We used
rounded rectangle to represent the patterns and strategies belong to an MSA
design area. A double-headed arrow shows a “complements” relationship between
two patterns or strategies. An octagon and dashed arrow is used to represent
the constraints of each pattern or strategy. Finally, plus (+) and minus (-)
signs indicate the positive and negative impact of each pattern or strategy on
the QAs.

Figure 1: Notations used in the decision models

##  3 Application Decomposition Decision Model

Monolithic applications need to be decomposed into small, independent, and
loosely coupled microservices to achieve the benefits (e.g., improved
scalability, independent deployment). There are several ways to break down an
application into microservices. The patterns and strategies collected are used
to create the application decomposition decision model (see Fig. 2). The
decision process for application decomposition into microservices is based on
the team size and impact of patterns and strategies on QAs. If the application
needs to be decomposed into microservices for the team of 5-9 people to
increase Availability, Scalability, Cohesion, Deployment, Performance, and
Maintainability, we can use one among five illustrated patterns (see Fig. 2).
In the following, we further explain the other conditions, impact on QAs, and
constraints for each pattern.

Table 1: Application decomposition patterns and strategies Name |  Summary
---|---
Decomposed by subdomains [14] [3] |  Define services corresponding to Domain-Driven Design (DDD) subdomains.
Decomposed by business capabilities [14] [3] |  Define services corresponding to business capabilities.
Service per team [14] [3] |  Break down the application into microservices that individual teams can manage.
Decomposed by transactions [3] |  An application typically needs to call multiple microservices to complete one business transaction. To avoid latency issues, services can be defined based on business transactions.
Scenario analysis [16] |  Identify the business capabilities by analyzing the nouns and verbs from given business scenarios.
Graph-based approach [8] |  Identify microservices from the source code of existing monolithic applications by graph clustering and visualization techniques.
Data Flow-Driven (DFD) approach [11] |  Follow a top-down approach in which data flow diagrams contain the business requirements that are later partitioned through a formal algebra algorithm for identifying microservices.

To increase Flexibility, Granularity, Reliability, Reusability, Security,
Functional suitability, and Portability, Decomposed by subdomains pattern can
be used. This pattern guides practitioners in defining each microservice
responsibility, boundaries, and relationships with other microservices. To
successfully implement this pattern, practitioners need to understand the
overall business (see Fig. 2). In contrast, if microservices need to be
defined with respect to business capabilities, Decomposed by business
capabilities pattern can be used. Normally, business capabilities are
organized into a multi-level hierarchy and generate business value. This
pattern improves the Granularity, Performance, and Security of microservices
if the business capabilities are identified by understanding the client
organization’s structure, purposes, and business processes. However, this
pattern reduces Flexibility as the application design is tightly coupled with
the business model. Another option that we can use for decomposing
applications is Service per team pattern. This pattern enables practitioners
to break applications into microservices that individual teams can manage. It
also complements Decomposed by subdomains and Decomposed by business
capabilities patterns. A constraint of Service per team pattern is that only
one small team (e.g., 5-9 people) owns one microservice, meaning that each
team independently develops, tests, deploys, and scales individual
microservice. The teams also interact with other teams to negotiate APIs.
Service per team pattern increases Availability, Scalability, Cohesion,
Deployment, and Performance, and Maintainability. If the project is large and
needs to hire more people, Service per team pattern negatively impacts the
development cost of microservices.

Figure 2: Decision model for application decomposition

Another exclusive pattern option in decomposition patterns is Decompose by
transactions, in which applications are decomposed based on business
transactions. Each business transaction carries one task, and each
microservice has the functionalities for several business transactions (e.g.,
sales, marketing). This pattern allows grouping multiple microservices to
avoid latency issues. Decompose by transactions pattern can help to improve
Response time, Data consistency, and Availability of microservices. Meanwhile,
decomposing applications based on transactions also increases Execution cost
and Coupling of microservices due to multiple functionalities being
implemented in one microservice. Another option to decompose an application is
Scenario-based analysis which consists of several steps, such as developing
scenarios, describing MSA, and evaluating scenarios. During the evaluation
process of scenarios, practitioners identify the microservices and
interactions between them. This pattern is appropriate if practitioners have
enough time to develop and describe the scenarios and MSA, respectively. This
strategy can also be used to identify the business capabilities of systems by
analyzing the nouns and verbs from given business scenarios. The identified
nouns represent the microservices, and the verbs describe the relationship
among them. While this strategy increases Scalability, Performance and
Coupling could be compromised because of the imprecise boundaries of
microservices.

Suppose that the team size is not defined for designing and developing
microservices, and we need to identify the microservices from the code of
legacy applications. In that case, we can choose Graph-based approach. This
approach uses the SArF clustering algorithm to decompose the system for
comprehension [9] and the city metaphor techniques for visualizing the system
structure [8]. Graph-based approach helps to identify microservices from the
source code of existing monolithic applications. The use of this approach
increases the Reusability of the existing code. Graph-based approach also
visualizes the extracted microservices and their relationships along with the
structure of the whole system. Hence, it also increases the Understandability
about the MSA design. Finally, if the team size is not defined and
applications need to be decomposed by using DFDs, in that case, Data flow-
driven approach can be used, which consists of several steps, such as
eliciting and analyzing the business requirements for identifying use cases
and business logic specifications, creating fine-grained DFDs, identifying the
dependencies between processes and datastores, and identifying microservices
by clustering processes and related data stores. Data flow-driven approach
increases Availability, Scalability, and Flexibility. In contrast, it
decreases Performance and Reusability mainly because of complex DFDs.

##  4 Threats to Validity

The threats to construct validity are related to taking correct operational
measures for collecting the data in this study. One potential threat is the
inadequate use of the primary constructs of the decision model (i.e., MSA
patterns and strategies, QAs, impact of the patterns on QAs). To mitigate this
threat, we adopted the following operational measures: (i) we conducted a
pilot search to ensure the correctness and appropriateness of the search
terms, (ii) we used eight databases (i.e., ACM Digital Library, IEEE Explore,
Springer Link, Science Direct, Wiley Online, Engineering Village, Web of
Science, and Google Scholar) in software engineering research for retrieving
the scientific studies, and (iii) we used Google for searching the grey
literature. Additionally, we followed the guidelines [2] to review and extract
data from the scientific and grey literature.

The threats to internal validity represent circumstances that could influence
the results obtained from the research. We tried to mitigate this threat
through collaborative work between the authors of this work. Regarding the
collaborative work, one author proposed the decision model and the rest of the
authors contributed to improving the models based on their knowledge and
expertise.

##  5 Related Work

Decision Models for Architecting Microservices Systems: The study in [6]
examines existing literature and provides guidance models for microservices
discovery and fault tolerance. The study in [5] reports decision guidance
models about generating, processing, and managing monitoring data, and
disseminating monitoring data to stakeholders in the process automation
domain. On the other hand, the study in [4] analyzes the strategies and
provides guidelines to support architects in selecting suitable frontend
architecture(s) for microservices systems.

Practitioners’ Perspectives and Recommendations for Architecting Microservices
Systems: The research in [13] derives a formal architecture decision model
containing 325 elements and relations that can help to reduce the (i) efforts
needed to understand the architectural decisions and (ii) uncertainty in the
design process. An empirical study in [7] interviewed 10 microservices experts
to find out the answers to (i) which design areas are relevant for
microservices, (ii) how important they are, and (iii) why they are important.

Decision Models for Architectural Patterns Selection: The study [7] proposes a
decision model that assists developers and architects in selecting appropriate
patterns for blockchain-based applications. In a similar study [10], the
authors present decision models for cyber-foraging systems that map functional
and non-functional requirements to architectural tactics for designing and
developing cyber-foraging systems.

Conclusive Summary: Our review of the related work suggests that there is a
lack of research on decision models that can leverage patterns and strategies
as reusable knowledge to address specific design area of microservices systems
(i.e., application decomposition). To the best of our knowledge, our proposed
decision model that supports decomposing applications into microservices is
not covered in any existing studies. This decision model also provides an
initial foundation to the research and practice in pattern-based architecting
of microservices systems.

##  6 Conclusions

The paper proposes a decision model for selecting patterns and strategies to
decompose applications into microservices. The proposed model is constructed
by reviewing scientific and grey literature. The decision model provides MSA
patterns, strategies, and their impact on QAs for selecting patterns and
strategies in decomposing applications into microservices. In the next step,
we aim to (1) propose decision models for other design areas, e.g.,
microservices security, communication, and service discovery, (2) validate the
proposed decision models in an industrial setting, and (3) develop a
recommendation system for selecting patterns and strategies for microservices
systems.

## Acknowledgments

This work has been supported by the National Key R&D Program of China under
Grant No. 2018YFB1402800 and the NSFC under Grant No. 62172311.

## References

  * [1] Dragoni, N., Lanese, I., Larsen, S.T., Mazzara, M., Mustafin, R., Safina, L.: Microservices: How to make your application scale. In: Proc. of the 11th PSI. pp. 95–104. Springer LNCS (2017)
  * [2] Garousi, V., Felderer, M., Mäntylä, M.V.: Guidelines for including grey literature and conducting multivocal literature reviews in software engineering. Information and Software Technology 106, 101–121 (2019)
  * [3] Hari, O.P.R., Tabby, W., Dmitry, G.: Decomposing monoliths into microservices- AWS prescriptive (2021), http://alturl.com/5spq4
  * [4] Harms, H., Rogowski, C., Lo Iacono, L.: Guidelines for adopting frontend architectures and patterns in microservices-based systems. In: Proc. of the 11th ESEC/FSE. pp. 902–907. ACM (2017)
  * [5] Haselböck, S., Weinreich, R.: Decision guidance models for microservice monitoring. In: Proc. of the 14th ICSAW. pp. 54–61. IEEE (2017)
  * [6] Haselböck, S., Weinreich, R., Buchgeher, G.: Decision guidance models for microservices: service discovery and fault tolerance. In: Proc. of the 5th ECBS. pp. 1–10. ACM (2017)
  * [7] Haselböck, S., Weinreich, R., Buchgeher, G.: An expert interview study on areas of microservice design. In: Proc. of the 11th SOCA. pp. 137–144. IEEE (2018)
  * [8] Kamimura, M., Yano, K., Hatano, T., Matsuo, A.: Extracting candidates of microservices from monolithic application code. In: Proc. of the 25th APSEC. pp. 571–580. IEEE (2018)
  * [9] Kobayashi, K., Kamimura, M., Yano, K., Kato, K., Matsuo, A.: Sarf map: Visualizing software architecture from feature and layer viewpoints. In: Proc. of the 21st ICPC. pp. 43–52. IEEE (2013)
  * [10] Lewis, G.A., Lago, P., Avgeriou, P.: A decision model for cyber-foraging systems. In: Proc. of the 13th WICSA. pp. 51–60. IEEE (2016)
  * [11] Li, S., Zhang, H., Jia, Z., Li, Z., Zhang, C., Li, J., Gao, Q., Ge, J., Shan, Z.: A dataflow-driven approach to identifying microservices from monolithic applications. Journal of Systems and Software 157, 110380 (2019)
  * [12] Newman, S.: Building Microservices: Designing Fine-Grained Systems. O’Reilly Media, Inc., second edn. (2020)
  * [13] Ntentos, E., Zdun, U., Plakidas, K., Schall, D., Li, F., Meixner, S.: Supporting architectural decision making on data management in microservice architectures. In: Proc. of the 13th ECSA. pp. 20–36. Springer LNCS (2019)
  * [14] Richardson, C.: Microservices Patterns: With Examples in Java. Manning (2018)
  * [15] Taibi, D., Auer, F., Lenarduzzi, V., Felderer, M.: From monolithic systems to microservices: An assessment framework. Information and Software Technology 137, 106600 (2021)
  * [16] Tusjunt, M., Vatanawood, W.: Refactoring orchestrated web services into microservices using decomposition pattern. In: Proc. of the 4th ICCC. pp. 609–613. IEEE (2018)
  * [17] Waseem, M., Liang, P., Shahin, M.: A systematic mapping study on microservices architecture in DevOps. Journal of Systems and Software 170, 110798 (2020)
  * [18] Waseem, M., Liang, P., Shahin, M., Ahmad, A., Nassab, A.R.: On the nature of issues in five open source microservices systems: An empirical study. In: Proc. of the 25th EASE. pp. 201–210. ACM (2021)
  * [19] Waseem, M., Liang, P., Shahin, M., Di Salle, A., Gastón, M.: Design, monitoring, and testing of microservices systems: The practitioners’ perspective. Journal of Systems and Software 182, 111061 (2021)


Applying Corollary 3.3 we see that the r.h.s. of above equation is at most
$\mathrm{C}\exp(-\frac{1}{\mathrm{C}}\mu^{3})$ where the $\mathrm{C}>0$
depends only on $\mathfrak{p}$ and is free of $a$ and $\mu$. As
$a_{n}\in[-1,1]$ for all large enough $n$, this proves (6.17).

##  Appendix A Technical Lemmas

In this section we prove two technical lemmas that were used in the main
sections. The first is Lemma 4.2 which gives a technical estimate related to
Brownian motion. We recall the statement of the result for reader’s
convenience.

######  Lemma A.1 (Lemma 4.2).

There exist universal constants $\mathrm{C}>0$ such that for all $r,s>0$ we
have

$\displaystyle\mathbb{P}\Big{(}\sup_{y\in\mathbb{R},|z|\leq
r}\left[\mathfrak{B}(y)-\mathfrak{B}(z)-\tfrac{(y-z)^{2}}{4}\right]\geq
s\Big{)}\leq(r+1)\cdot\mathrm{C}\exp\big{(}-\tfrac{1}{\mathrm{C}}s^{{3/2}}\big{)}$
(A.1)

where $\mathfrak{B}(x)$ is a two-sided Brownian motion with diffusion
coefficient $2$.

###### Proof.

Fix $k_{1},k_{2}\in\mathbb{Z}$. Define

$\displaystyle
m_{k_{1},k_{2}}:=\inf\limits_{y\in[k_{1},k_{1}+1],z\in[k_{2},k_{2}+1]}|y-z|,\quad\mathsf{A}_{k_{1},k_{2}}$
$\displaystyle:=\Big{\\{}\sup_{y\in[k_{1},k_{1}+1],z\in[k_{2},k_{2}+1]}\big{[}\mathfrak{B}(y)-\mathfrak{B}(z)-\tfrac{(y-z)^{2}}{4}\big{]}\geq
s\Big{\\}}.$

Let us set $2\sup_{x\in[0,1]}\sqrt{x\log\frac{2}{x}}=:\tau<\infty$ We consider
the following events

$\displaystyle\mathsf{B}_{k_{1},k_{2}}$
$\displaystyle:=\Big{\\{}\sup_{y\in[k_{1},k_{1}+1],z\in[k_{2},k_{2}+1]}\big{|}\mathfrak{B}(y)-\mathfrak{B}(z)-\mathfrak{B}({k_{1}})+\mathfrak{B}({k_{2}})\big{|}\geq\tfrac{s}{2}+\tfrac{m_{k_{1},k_{2}}^{2}}{8}\Big{\\}},$
$\displaystyle\mathsf{C}_{k_{1},k_{2}}$
$\displaystyle:=\Big{\\{}|\mathfrak{B}({k_{1}})-\mathfrak{B}({k_{2}})|\geq\tfrac{s}{2}+\tfrac{m_{k_{1},k_{2}}^{2}}{8}\Big{\\}}.$

Define the 2D random process
$\mathfrak{F}(y,z):=\mathfrak{B}(y)-\mathfrak{B}(z)$. Note that by tail
estimates of Brownian motion we have

$\displaystyle\mathbb{P}(|\mathfrak{F}(y,z+h)-\mathfrak{F}(y,z)|\geq
u\sqrt{h})\leq\mathrm{C}e^{-\frac{u^{2}}{\mathrm{C}}},\quad\mathbb{P}(|\mathfrak{F}(y+h,z)-\mathfrak{F}(y,z)|\geq
u\sqrt{h})\leq\mathrm{C}e^{-\frac{u^{2}}{\mathrm{C}}}.$

Thus by Lemma 3.3 in [DV21a], we get that

$\displaystyle\mathbb{P}\Big{(}\sup_{y\in[k_{1},k_{1}+1],z\in[k_{2},k_{2}+1]}\Big{|}\frac{\mathfrak{F}(y,z)-\mathfrak{F}(k_{1},k_{2})}{\sqrt{(z-k_{2})\log\frac{2}{z-k_{2}}}+\sqrt{(y-k_{1})\log\frac{2}{y-k_{1}}}}\Big{|}\geq
u\Big{)}\leq\mathrm{C}e^{-\frac{u^{2}}{\mathrm{C}}}.$

We can set
$u=\frac{1}{\tau}\big{(}\frac{s}{2}+\frac{m_{k_{1},k_{2}}^{2}}{8}\big{)}$ and
adjust the constants to get

$\displaystyle\mathbb{P}\big{(}\mathsf{B}_{k_{1},k_{2}}\big{)}\leq\mathrm{C}\exp\Big{(}-\tfrac{1}{\mathrm{C}}(4s+m_{k_{1},k_{2}}^{2})^{2}\Big{)}.$

On the other hand when $k_{1}=k_{2}$, the event $\mathsf{C}_{k_{1},k_{2}}$ has
probability zero. For $k_{1}\neq k_{2}$ by stationary increment properties of
Brownian motion we have

$\displaystyle\mathbb{P}\Big{(}|\mathfrak{B}({k_{1}})-\mathfrak{B}({k_{2}})|\geq\tfrac{s}{2}+\tfrac{m_{k_{1},k_{2}}^{2}}{8}\Big{)}\leq\mathrm{C}\exp\Big{(}-\tfrac{1}{\mathrm{C}}\frac{(4s+m_{k_{1},k_{2}}^{2})^{2}}{|k_{1}-k_{2}|}\Big{)}.$

Since
$\mathsf{A}_{k_{1},k_{2}}\subset\mathsf{B}_{k_{1},k_{2}}\cup\mathsf{C}_{k_{1},k_{2}}$,
by union bound we get

$\displaystyle\mathbb{P}(\mathsf{A}_{k_{1},k_{2}})\leq\mathrm{C}\exp\big{(}-\tfrac{1}{\mathrm{C}}(4s+m_{k_{1},k_{2}}^{2})^{2}\big{)}+\mathrm{C}\exp\Big{(}-\frac{1}{\mathrm{C}}\frac{(4s+m_{k_{1},k_{2}}^{2})^{2}}{|k_{1}-k_{2}|}\Big{)}\mathbf{1}_{k_{1}\neq
k_{2}}$

Fixing $k_{2}$, we first take the sum over $k_{1}\in\mathbb{Z}$. Since
$m_{k_{1},k_{2}}\geq\frac{1}{2}|k_{1}-k_{2}|$ whenever $|k_{1}-k_{2}|\geq 2$,
the first term sums to $c_{1}\exp(-c_{2}s^{2})$. For the second term we
approximate the sum as an integral. Indeed,

$\displaystyle\sum_{k_{1}\in\mathbb{Z}}\mathrm{C}\exp\Big{(}-\tfrac{1}{\mathrm{C}}\frac{(4s+m_{k_{1},k_{2}}^{2})^{2}}{|k_{1}-k_{2}|}\Big{)}\mathbf{1}_{k_{1}\neq
k_{2}}\leq\mathrm{C}\int_{\mathbb{R}}\exp\left(-\tfrac{1}{\mathrm{C}}\frac{(s+|x|^{2})^{2}}{|x|}\right)\mathrm{d}x\leq\mathrm{C}\exp(-\tfrac{1}{\mathrm{C}}s^{3/2}).$

The last inequality follows by noting that the exponent attains maximum of
$-c_{2}s^{3/2}$ when $|x|=\sqrt{s}$. Thus by union bound again,

$\displaystyle\mbox{l.h.s.~{}of \eqref{eq:b_bb1}}\leq\sum_{k_{2}=-\lceil
r\rceil}^{\lceil
r\rceil}\sum_{k_{1}\in\mathbb{Z}}\mathbb{P}(\mathsf{A}_{k_{1},k_{2}})\leq(r+1)\cdot\mathrm{C}\exp\big{(}-\tfrac{1}{\mathrm{C}}s^{{3/2}}\big{)}.$

This completes the proof. ∎

We next collect an elementary real analysis inequality that is used in
defining permissible pairs in Definition 5.2.

######  Lemma A.2 (Real Analysis Inequality).

For each $\alpha>1$, there exists a constant $\Delta_{\alpha}>0$ such that for
all $\gamma\geq 2$ we have

$\displaystyle\sup_{x\in[0,1]}\left[x^{\frac{1}{2}}\log^{\alpha}\tfrac{1}{x}-\gamma
x^{2}\right]\leq\Delta_{\alpha}\gamma^{-\frac{1}{3}}\log^{4\alpha/3}\gamma.$

###### Proof.

We use $\mathrm{C}>0$ to denote a generic constant dependent only on $\alpha$
changing from line to line. Let $y=x\gamma^{\frac{2}{3}}$ so that

$\displaystyle\sup_{x\in[0,1]}\left[x^{\frac{1}{2}}\log^{\alpha}\tfrac{1}{x}-\gamma
x^{2}\right]=\sup_{y\in[0,\gamma^{\frac{2}{3}}]}\gamma^{-\frac{1}{3}}\left[y^{\frac{1}{2}}\log^{\alpha}\tfrac{\gamma^{2/3}}{y}-y^{2}\right].$

Note that for $y\in[0,1]$,

$\displaystyle y^{\frac{1}{2}}\log^{\alpha}\tfrac{\gamma^{2/3}}{y}\leq
2^{\alpha}\left[y^{\frac{1}{2}}\log^{\alpha}\gamma^{2/3}+y^{\frac{1}{2}}\log^{\alpha}\tfrac{1}{y}\right]\leq\mathrm{C}\log^{\alpha}\gamma.$

For $y\in[1,\gamma^{2/3}]$ we have

$\displaystyle y^{\frac{1}{2}}\log^{\alpha}\tfrac{\gamma^{2/3}}{y}-y^{2}\leq
y^{\frac{1}{2}}\log^{\alpha}\gamma^{2/3}-y^{2}\leq\mathrm{C}\log^{4\alpha/3}\gamma,$

where the last inequality follows from the fact that $\sqrt{y}r-y^{2}$ is
concave in $y$ and attains maximum at $y=(r/4)^{2/3}$. Combining the last two
displays we obtain the required inequality. ∎

## References

  * [Bar01] Y. Baryshnikov.  GUEs and queues.  Probability Theory and Related Fields, 119(2):256–274, 2001.
  * [BFP10] J. Baik, P. L. Ferrari, and S. Péché.  Limit process of stationary tasep near the characteristic line.  Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 63(8):1017–1070, 2010.
  * [BGH19] E. Bates, S. Ganguly, and A. Hammond.  Hausdorff dimensions for shared endpoints of disjoint geodesics in the directed landscape.  arXiv preprint arXiv:1912.04164, 2019.
  * [BGH21] R. Basu, S. Ganguly, and A. Hammond.  Fractal geometry of airy $\\_${$2$} processes coupled via the airy sheet.  Annals of Probability, 49(1):485–505, 2021.
  * [BGHK19] R. Basu, S. Ganguly, M. Hegde, and M. Krishnapur.  Lower deviations in beta-ensembles and law of iterated logarithm in last passage percolation.  arXiv preprint arXiv:1909.01333, 2019.
  * [BR00] J. Baik and E. M. Rains.  Limiting distributions for a polynuclear growth model with external sources.  Journal of Statistical Physics, 100(3):523–541, 2000.
  * [CFS18] S. Chhita, P. L. Ferrari, and H. Spohn.  Limit distributions for KPZ growth models with spatially homogeneous random initial conditions.  The Annals of Applied Probability, 28(3):1573–1603, 2018.
  * [CGH21] I. Corwin, P. Ghosal, and A. Hammond.  KPZ equation correlations in time.  The Annals of Probability, 49(2):832–876, 2021.
  * [CH14] I. Corwin and A. Hammond.  Brownian Gibbs property for Airy line ensembles.  Invent. Math., 195(2):441–508, 2014.
  * [CH16] I. Corwin and A. Hammond.  KPZ line ensemble.  Probability Theory and Related Fields, 166(1):67–185, 2016.
  * [CHHM21] I. Corwin, A. Hammond, M. Hegde, and K. Matetski.  Exceptional times when the KPZ fixed point violates johansson’s conjecture on maximizer uniqueness.  arXiv preprint arXiv:2101.04205, 2021.
  * [Cor12] I. Corwin.  The Kardar–Parisi–Zhang equation and universality class.  Random Matrices: Theory Appl., 1(01):1130001, 2012.
  * [CQR15] I. Corwin, J. Quastel, and D. Remenik.  Renormalization fixed point of the KPZ universality class.  Journal of Statistical Physics, 160(4):815–834, 2015.
  * [Das22] S. Das.  Temporal increments of the KPZ equation with general initial data.  arXiv preprint arXiv:2203.00666, 2022.
  * [Dau22] D. Dauvergne.  Non-uniqueness times for the maximizer of the KPZ fixed point.  arXiv preprint arXiv:2202.01700, 2022.
  * [DG21] S. Das and P. Ghosal.  Law of iterated logarithms and fractal properties of the KPZ equation.  arXiv preprint arXiv:2101.00730, 2021.
  * [DOV18] D. Dauvergne, J. Ortmann, and B. Virág.  The directed landscape.  arXiv preprint arXiv:1812.00309, 2018.
  * [DSV20] D. Dauvergne, S. Sarkar, and B. Virág.  Three-halves variation of geodesics in the directed landscape.  arXiv preprint arXiv:2010.12994, 2020.
  * [DV21a] D. Dauvergne and B. Virág.  Bulk properties of the airy line ensemble.  The Annals of Probability, 49(4):1738–1777, 2021.
  * [DV21b] D. Dauvergne and B. Virág.  The scaling limit of the longest increasing subsequence.  arXiv preprint arXiv:2104.08210, 2021.
  * [FV21] P. L Ferrari and B. Vető.  Upper tail decay of KPZ models with brownian initial conditions.  Electronic Communications in Probability, 26:1–14, 2021.
  * [Gan21] S. Ganguly.  Random metric geometries on the plane and Kardar-Parisi-Zhang universality.  arXiv preprint arXiv:2110.11287, 2021.
  * [GH21] S. Ganguly and M. Hegde.  Local and global comparisons of the airy difference profile to brownian local time.  arXiv preprint arXiv:2103.12029, 2021.
  * [GTW01] J. Gravner, C. A Tracy, and H. Widom.  Limit theorems for height fluctuations in a class of discrete space and time growth models.  Journal of Statistical Physics, 102(5):1085–1132, 2001.
  * [GY21] P. Ghosal and J. Yi.  Fractal geometry of the valleys of the parabolic anderson equation.  arXiv preprint arXiv:2108.03810, 2021.
  * [GZ22] S. Ganguly and L. Zhang.  Fractal geometry of the space-time difference profile in the directed landscape via construction of geodesic local times.  arXiv preprint arXiv:2204.01674, 2022.
  * [HHNT15] Y. Hu, J. Huang, D. Nualart, and S. Tindel.  Stochastic heat equations with general multiplicative Gaussian noises: Hölder continuity and intermittency.  Electron. J. Probab., 20:no. 55, 50, 2015.
  * [KKX17] D. Khoshnevisan, K. Kim, and Y. Xiao.  Intermittency and multifractality: a case study via parabolic stochastic PDEs.  Ann. Probab., 45(6A):3697–3751, 2017.
  * [KKX18] D. Khoshnevisan, K. Kim, and Y. Xiao.  A macroscopic multifractal analysis of parabolic stochastic PDEs.  Comm. Math. Phys., 360(1):307–346, 2018.
  * [KSXZ13] D. Khoshnevisan, J. Swanson, Y. Xiao, and L. Zhang.  Weak existence of a solution to a differential equation driven by a very rough fbm.  arXiv preprint arXiv:1309.3613, 2013.
  * [Led18] M. Ledoux.  A law of the iterated logarithm for directed last passage percolation.  J. Theor. Probab., 31(4):2366–2375, 2018.
  * [MFQR13] G. Moreno Flores, J. Quastel, and D. Remenik.  Endpoint distribution of directed polymers in 1+ 1 dimensions.  Communications in Mathematical Physics, 317(2):363–380, 2013.
  * [MQR21] K. Matetski, J. Quastel, and D. Remenik.  The KPZ fixed point.  Acta Mathematica, 227(1):115–203, 2021.
  * [NQR20] M. Nica, J. Quastel, and D. Remenik.  One-sided reflected brownian motions and the KPZ fixed point.  In Forum of Mathematics, Sigma, volume 8. Cambridge University Press, 2020.
  * [OT74] S. Orey and S. J. Taylor.  How often on a Brownian path does the law of iterated logarithm fail?  Proc. London Math. Soc. (3), 28:174–192, 1974.
  * [Pim14] L. P. R. Pimentel.  On the location of the maximum of a continuous stochastic process.  Journal of Applied Probability, 51(1):152–161, 2014.
  * [Pim21] L. P. R. Pimentel.  Brownian aspects of the KPZ fixed point.  In In and Out of Equilibrium 3: Celebrating Vladas Sidoravicius, pages 711–739. Springer, 2021.
  * [PS02] M. Prähofer and H. Spohn.  Scale invariance of the PNG droplet and the Airy process.  volume 108, pages 1071–1106. 2002.  Dedicated to David Ruelle and Yasha Sinai on the occasion of their 65th birthdays.
  * [PZ17] E. Paquette and O. Zeitouni.  Extremal eigenvalue correlations in the gue minor process and a law of fractional logarithm.  Ann. Probab., 45(6A):4112–4166, 2017.
  * [QR19] J. Quastel and D. Remenik.  How flat is flat in random interface growth?  Transactions of the American Mathematical Society, 371(9):6047–6085, 2019.
  * [QS15] J. Quastel and H. Spohn.  The one-dimensional KPZ equation and its universality class.  J. Stat. Phys., 160(4):965–984, 2015.
  * [Qua11] J. Quastel.  Introduction to KPZ.  Current developments in mathematics, 2011(1), 2011.
  * [RRV11] J. Ramirez, B. Rider, and B. Virág.  Beta ensembles, stochastic airy spectrum, and a diffusion.  Journal of the American Mathematical Society, 24(4):919–944, 2011\.
  * [Sas05] T. Sasamoto.  Spatial correlations of the 1d kpz surface on a flat substrate.  Journal of Physics A: Mathematical and General, 38(33):L549, 2005\.
  * [SV21] S. Sarkar and B. Virág.  Brownian absolute continuity of the KPZ fixed point with arbitrary initial condition.  The Annals of Probability, 49(4):1718–1737, 2021.
  * [Tak18] K. A. Takeuchi.  An appetizer to modern developments on the Kardar–Parisi–Zhang universality class.  Physica A: Statistical Mechanics and its Applications, 504:77–105, 2018.
  * [TW94] C. A. Tracy and H. Widom.  Level-spacing distributions and the airy kernel.  Communications in Mathematical Physics, 159(1):151–174, 1994.
  * [TW96] C. A. Tracy and H. Widom.  On orthogonal and symplectic matrix ensembles.  Communications in Mathematical Physics, 177(3):727–754, 1996.