# Communication Pattern Models: An Extension of Action Models for Dynamic-
Network Distributed Systems

Diego A. Velázquez Diego A. Velázquez is a doctoral student at the Programa de
Doctorado en Ciencia e Ingeniería de la Computación, Universidad Nacional
Autónoma de México, and is the receipient of a fellowship from CONACyT.
<EMAIL_ADDRESS>Armando Castañeda Armando Castañeda was
supported by PAPIIT project IN108720<EMAIL_ADDRESS>David A.
Rosenblueth<EMAIL_ADDRESS>Universidad Nacional Autónoma de México

###### Abstract

Halpern and Moses were the first to recognize, in 1984, the importance of a
formal treatment of knowledge in distributed computing. Many works in
distributed computing, however, still employ informal notions of knowledge.
Hence, it is critical to further study such formalizations. Action models, a
significant approach to modeling dynamic epistemic logic, have only recently
been applied to distributed computing, for instance, by Goubault, Ledent, and
Rajsbaum. Using action models for analyzing distributed-computing
environments, as proposed by these authors, has drawbacks, however. In
particular, a direct use of action models may cause such models to grow
exponentially as the computation of the distributed system evolves. Hence, our
motivation is finding compact action models for distributed systems. We
introduce _communication pattern models_ as an extension of both ordinary
action models and their update operator. We give a systematic construction of
communication pattern models for a large variety of distributed-computing
models called _dynamic-network models_. For a proper subclass of dynamic-
network models called _oblivious_ , the communication pattern model remains
the same throughout the computation.

##  1 Introduction

A formal treatment of the concept of _knowledge_ is important yet little
studied in the distributed-computing literature. Authors in distributed
computing often refer to the knowledge of the different agents or processes,
but typically do so only _informally_. Hence, a formal basis of knowledge in
distributed computing would increase the power to prove formal results. The
first step in this direction was taken by Halpern and Moses [12]. A
topological approach [13] to distributed computing resulted in a further
connection [11] with epistemic logic. Such a connection uses epistemic “action
models” [2, 9] to capture communication between agents. We observe, however,
that the action models proposed in [11] for the _Iterated Immediate Shapshot_
(IIS) computing model [5, 6] not only vary at each communication round, but
each action model itself is structurally isomorphic to the resulting epistemic
model, which paradoxically, requires knowing the desired result beforehand.
Our objective is to develop a different connection between _dynamic-network
models_ [8, 15, 17] (which include the IIS model), and _Dynamic Epistemic
Logic_ (DEL) [2, 9], more appropriate for computing knowledge change in these
systems.

#### Context.

In a distributed system, communication is typically performed either by
sending and receiving messages, or by writing to, and reading from, a shared
memory. The communication patterns (i.e., who communicated with whom) that can
occur may change from model to model. When designing and analyzing distributed
systems, it is often the case that authors informally refer to what an agent
“knows” after an agent performs some action. There is indeed a formal
connection between distributed systems and epistemic logic: this connection
was initiated by Halpern and Moses in 1984 [12], showing that distributed
systems can be rigorously studied from an epistemic-logic viewpoint. Roughly,
a distributed protocol is studied through an _epistemic model_ with each of
its states representing a possible _configuration_ of the protocol. Since its
discovery, the epistemic-based approach to distributed systems has been
fruitful, as shown in the book by Fagin, Halpern, Moses, and Vardi [10].

An important connection between distributed computing and topology was
discovered in three independent papers by Borowsky and Gafni [4], Herlihy and
Shavit [14], and Saks and Zaharoglou [19] in 1993, and since then this
approach has provided useful techniques to show a number of important results
in this field. The book by Herlihy, Kozlov, and Rajsbaum [13] provides a
comprehensive description of this connection.

Recently, Goubault, Ledent, and Rajsbaum have shown [11] that the epistemic-
based approach can be directly connected to the topology-based approach to
distributed systems. The topological approach studies a distributed protocol
through its topological representation: a geometric object, called _simplicial
complex_ , where each of its faces is associated with a _configuration_ of the
protocol. In essence, Goubault, Ledent, and Rajsbaum established [11] a
correspondence between the topological description of distributed protocols
and epistemic models.

A second interesting result of these authors is that the communication
patterns allowed in the IIS distributed model can also be described using
epistemic-logic tools from DEL: the communication in a distributed model can
be modeled with an action model capturing the communication events that can
occur, and the _restricted modal product_ operator shows how knowledge evolves
after agents exchange information in a _communication round_. (A more thorough
summary of [11] appears in Section 6.)

We observe that the action models of [11] describing communication in the IIS
model have drawbacks: First, such action models are different for each
communication round (an ideal representation of communication would not depend
on the communication rounds that have been executed so far). In addition, the
size of such action models grows exponentially as the computation develops.
Moreover, such action models are structurally isomorphic to the epistemic
models we wish to compute. The action models of [11], therefore, not only are
not useful for computing the epistemic model resulting from a communication
event, but are not a succinct representation of the communication that can
happen in the IIS model. This phenomenon is opposite to the description of
communication in the topological approach, where we have a geometric and
compact description of the communication in the IIS model: the communication
is clearly described as a subdivision [13, Chapter 11]. 111Informally, a
subdivision results from dividing the faces of a geometrical object into more
faces preserving its shape.

#### Contributions.

We are interested in the following question: in the spirit of the action-model
approach to DEL, is it possible to describe the communication in a distributed
model in a compact manner? As a first step, we try to salvage the approach of
[11], by attempting to find an action model applicable to every communication
round for _two_ agents with binary inputs in the IIS model. We exhibit a
family of action models with a constant number of events, although each event
is labeled with a precondition formula whose size does increase at each
communication round. For obtaining these action models, it was crucial to know
_in advance_ the epistemic model after a communication round. We have not been
able to find a similar family for _three or more_ agents yet. The case of
$m$-ary inputs for $m\geq 3$ would be even harder to analyze.

The drawbacks of the action models proposed in [11], together with our
unsuccessful efforts to find action models for IIS of small size, are
motivations for investigating a different approach. We hence consider an
extension of action models that allows us to easily derive models of small
size. Moreover, we study not only the IIS model but also a larger class of
message-passing models called _dynamic-network models_ [8, 15, 17]. Roughly
speaking, in a dynamic-network model, the agents execute infinite sequences of
communication rounds. In each round, the agents communicate according to a
_communication pattern_ that specifies who communicates with whom in that
round. A proper subclass of dynamic-network models are those known as
_oblivious_ that are specified with a set of communication patterns that can
occur in any round, regardless of the communication patterns that have
occurred so far in the execution. The IIS model can be defined as an oblivious
dynamic-network model.

Our main contribution is a simple but powerful extension to the existing
action models and its restricted modal product. For every dynamic-network
model, we systematically define an infinite sequence of _communication pattern
models_ that represent how knowledge changes when agents communicate in the
_full-information protocol_ , hence making our approach amenable to be
extended to automated formal verification of distributed systems. For the case
of oblivious models, the communication pattern model remains the same all
through the execution. Hence, we are able to model communication of oblivious
dynamic-network models in constant space.

#### Structure of this paper.

The rest of this paper is structured as follows. Section 2 gives an overview
of drawbacks arising from a straightforward use of action models in some
contexts in multi-agent systems and outlines our solution to overcome such
shortcomings. After establishing notation and definitions in Section 3, we
explain, in Section 4, an attempt to improve on [11] within the IIS model.
Section 5 presents communication pattern models, our modification of action
models. Comparison with existing work appears in Section 6, and Section 7
concludes this paper.

##  2 An Overview of Our Proposal

We first motivate our proposal by pointing out a limitation of action models
and the restricted modal product that arises in some contexts when modeling
the communication that can happen in a multi-agent system. Roughly speaking,
sometimes it is impossible to have action models of “small size”. Our
discussion here is informal as we are interested in high-level ideas at the
moment, hence delaying formal definitions for the next sections.

#### The issue.

Let us consider the well-known _coordinated attack_ problem where two agents
$a$ and $b$ wish to schedule an attack. Agent $a$ has two possible preferences
for scheduling the attack, n for noon or d for dawn, while agent $b$ has no
initial preference and wishes to learn $a$’s. Communication is unreliable:
whenever an agent sends a message, such a message can get lost. The epistemic
model $\mathit{M}$ modeling the initial situation before any communication
occurs has two worlds, one in which $a$ prefers to attack at dawn and another
one in which $a$ prefers to attack at noon; $b$ cannot distinguish between
these two worlds. See model $\mathit{M}$ in Fig. 1.

An action model is a generalization of an epistemic model, where vertices,
called _events_ , are labeled with arbitrary formulas (as opposed to sets of
propositional variables) called _preconditions_. The restricted modal product
of an epistemic model $\mathit{M}$ and an action model $\mathit{A}$, denoted
$\mathit{M}\otimes\mathit{A}$, is an epistemic model where each world is a
pair $(w,e)$, such that $w$ is a world in $M$, $e$ is an event in
$\mathit{A}$, and the precondition of $e$ holds in $w$. Worlds $(w,e)$ and
$(w^{\prime},e^{\prime})$ are connected with each other for agent $a$ if both
$w$ and $w^{\prime}$ are connected in $\mathit{M}$ for $a$, and $e$ and
$e^{\prime}$ are connected in $\mathit{A}$ for $a$. World $(w,e)$ is labeled
with the same label as that of $w$. (Formal definitions of action model and
restricted modal product appear in Subsect. 4.2.)

A simple action model $\mathit{A}$ modeling that $a$ sends its preference to
$b$ has three events: one for each preference $p\in\\{{\sf d,n}\\}$ modeling
that $b$ successfully receives the preference, $p$, of $a$, with a
precondition specifying that the event can happen only if $p$ is the
preference of $a$, and a third event, modeling that $a$’s message gets lost,
with precondition $\top$. Agent $b$ can distinguish between all events since
it either receives $a$’s message or not, but $a$ cannot distinguish between
events because messages can get lost. See action model $\mathit{A}$ in Fig. 1.
The restricted modal product $\mathit{M}\otimes\mathit{A}$ contains four
worlds, one for each combination of $a$’s initial preference and
successful/unsuccessful communication.

Figure 1: A smaller action model for the coordinated attack problem using our
approach.

We observe that the action model $\mathit{A}$ has the following inconvenience.
If $a$ has $x>2$ preferences to schedule the attack instead of only two, a
natural generalization of $\mathit{A}$ has $x+1$ events: $\mathit{A}$ is akin
to a star with a “central” event modeling that $a$’s message gets lost, and
one event for each of the possible preferences of $a$. Thus, the size of the
action model is proportional to the size of $a$’s _input space_.

Can we design a smaller action model for this situation? Can we design an
action model with only two events, one corresponding to the case that $a$’s
message gets lost and another corresponding to the case that $a$’s message
(with distinct contents, either $\sf d$ or $\sf n$) reaches $b$? The answer is
no. It is easy to see that if we have an action model $\mathit{A}^{\prime}$
with only one event $h$ corresponding to $a$’s successful communication, and
unavoidably with precondition ${\sf d}\vee{\sf n}={\top}$ (see
$\mathit{A}^{\prime}$ in Fig. 1, discarding for the moment the set
$\overline{N}(h,b)=\\{a\\}$), then $\mathit{M}\otimes\mathit{A}^{\prime}$ has
again four worlds but now $b$ cannot distinguish between the worlds $(w,h)$
and $(w^{\prime},h)$ corresponding to the cases where the communication was
successful (which is incorrect). A similar situation happens if $a$ has more
than two preferences: it is impossible to have an action model with an event
that models the case that $a$’s communication is successful. We cannot get any
smaller action model in this situation (it might be possible, however, to do
so in further rounds) because the action models are designed to deal with
“interpreted” events, namely, an event includes the information of the message
encoded in its precondition, hence it has a limited ability to represent that
_some_ information is sent from one agent to another.

This property of action models is a problem in some contexts. Specifically,
when studying computability in a given distributed model, it is often the case
that the analysis is performed on _protocols_ in which agents proceed in a
sequence of _rounds_ of communication, and in each round every agent sends
_all_ the information it has collected so far to all other agents; these
protocols are called _full-information_ in the distributed-computing
literature. To be able to reason in the style of DEL, we would like to have an
action model modeling the communication events that can happen in a round, and
update the epistemic model with the help of the restricted modal product in
each round. Drawbacks of the approach in [11] are that the size of the action
models proposed there grows exponentially in the number of round and that such
action models are structurally isomorphic to the resulting epistemic models.
As we will see later, for the case of two agents, we have been able to find a
family of action models with a constant number of actions (although the
preconditions of the action model do change from round to round) but it is
unclear how to find action models with this property for other cases.

#### A glimpse of our solution.

Coming back to our initial example, how do we “fix” the problem in
$M\otimes{\mathit{A}^{\prime}}$, i.e., that $b$ cannot distinguish between
worlds $(w,h)$ and $(w^{\prime},h)$? Our solution is based on the following
observation: $b$ must be able to distinguish between the two worlds because
(1) it receives a message from $a$ in the event $h$ of $\mathit{A}^{\prime}$,
and (2) $a$ can distinguish between the $w$ and $w^{\prime}$ in $M$.
Therefore, $a$ must send information that makes $b$ able to distinguish
between the two worlds in $M\otimes\mathit{A}^{\prime}$.

We define an extension to the action model formalism, which equips an action
model with an additional function $\overline{N}$ that maps every pair $(e,a)$
to a set of agents. Intuitively, $\overline{N}(e,a)$ contains the agents that
$a$ receives messages from when the event $e$ happens. The restricted modal
product is modified by adding two conditions when updating the accessibility
relation of an epistemic model. Such conditions say that an agent $a$ cannot
distinguish between two worlds $(w,e)$ and $(w^{\prime},e^{\prime})$ if and
only if $a$ receives messages from the same set of agents in $e$ and
$e^{\prime}$ (i.e., $\overline{N}(e,a)=\overline{N}(e^{\prime},a)$) and each
of these agents cannot distinguish between $w$ and $w^{\prime}$ (namely,
$\forall a^{\prime}\in\overline{N}(e,a),w\sim_{a^{\prime}}w^{\prime}$). The
idea is that if those agents sending information to $a$ cannot distinguish
between $w$ and $w^{\prime}$, then there is no information they send to $a$
making $(w,e)$ and $(w^{\prime},e^{\prime})$ distinguishable to $a$. The new
product is denoted $\odot$. Using this formalism, for the coordinated attack
problem, we are able to define a _communication pattern model_ $A^{\prime}$
with a _single_ event (called communication pattern in our context) $h$
corresponding to the case in which $a$’s message reaches $b$. In $A^{\prime}$,
$\overline{N}(h,b)$ is set to $\\{a\\}$, and $\overline{N}$ is set to
$\emptyset$ in any other case. Figure 1 shows the model $A^{\prime}$.
Furthermore, the action model is correct regardless of the size of $a$’s input
space, meaning that the very same action model produces the desired epistemic
model if $M$ represents the situation that $a$ has $x>2$ initial preferences.

##  3 Analyzing distributed computing models

In this section, we give some introductory definitions and fix the notation.
We assume some familiarity with basic epistemic logic. We refer to the
language of multiagent epistemic logic as $\mathcal{L}_{K}$. Additionally, we
consider a non-empty finite set of agents
$\mathit{Ag}=\\{a_{1},\dots,a_{n}\\}$ and a non-empty finite set of
propositions $\mathit{Props}$, unless specified otherwise.

#### Our models of interest.

We are interested in _dynamic-network models_ [8, 15, 17], in which a set of
$n\geq 2$ failure-free agents proceed in an infinite sequence of _synchronous_
rounds of communication. Each agent is a _state machine_. In each round, the
communication is specified with a _communication graph_ , namely a directed
graph whose vertex set is $\mathit{Ag}$, with each edge $(a_{i},a_{j})$
indicating that a message from $a_{i}$ to $a_{j}$ is successfully delivered in
that round. The _in-neighborhood_ of an agent $a_{i}$ in a communication graph
$G$, namely the set of agents $a_{j}$ such that $(a_{j},a_{i})$ is an arrow in
$G$, is denoted $N^{-}_{G}(a_{i})$. Let $CP_{\mathit{Ag}}$ denote the set with
all communication graphs with vertex set $Ag$. Thus, a dynamic-network model
$\mathit{Adv}$ is specified with a set of infinite sequences of graphs of
$CP_{\mathit{Ag}}$, that we call _adversary_. Intuitively, we say that an
adversary $Adv$ is _oblivious_ if in every round, any communication graph in a
given set can happen, regardless of the communication graphs that have
happened in previous rounds. This is formalized as follows. We say that a
finite sequence $S$ of communication graphs is a _prefix_ of $\mathit{Adv}$ if
$S$ is a prefix of a sequence in $\mathit{Adv}$. An adversary $\mathit{Adv}$
is oblivious if there exists a non-empty subset $X\subseteq CP_{\mathit{Ag}}$
such that the graphs in $X$ are the prefixes of $\mathit{Adv}$ of length one,
and for every finite sequence $S$ that is a prefix of $\mathit{Adv}$, it holds
that $S\cdot G$ is a prefix of $\mathit{Adv}$, for every graph $G\in X$. Thus,
an oblivious adversary is simply specified through the set $X$ of
communication graphs; we will say that $Adv=X$.

#### Protocols.

Each agent locally executes a _protocol_ that specifies the messages that the
agent sends in a round, depending on the local state of the agent at the
beginning of the round. Each agent starts the computation with a private
input, which is the state of the agent at the beginning of the first round.
Since we are interested in modeling how knowledge can evolve through the
computation, we assume that in every round every agent attempts to communicate
to everybody all it knows so far. Formally, every agent locally executes the
_full-information_ protocol, namely, in every round an agent sends to all
other agents all the information such an agent has collected so far.
Therefore, the full-information protocol captures all that an agent can know
in an execution. The full-information protocol is an important tool in
distributed-computing computability research.

#### Executions and configurations.

An _execution_ $E$ of an adversary $\mathit{Adv}$ is a pair $(I,S^{\infty})$,
where $I=(v_{1},v_{2},\dots,v_{n})$ is an _input vector_ denoting that agent
$a_{i}$ starts with input $v_{i}$, with $v_{i}$ belonging to an _input space_
, denoted $In$, and $S^{\infty}$ is a sequence of $\mathit{Adv}$. An _$r$
-execution_ of $\mathit{Adv}$ is a pair $(I,S)$, where $I$ is an input vector
and $S$ is a prefix of $Adv$ with $|S|=r$. A configuration $C$ is an $n$-tuple
whose $i$-th position is a local state of agent $a_{i}$ (thus input vectors
are configurations). We say that $a_{i}$ _does not distinguish_ between
configurations $C$ and $C^{\prime}$ if and only if $C(i)=C^{\prime}(i)$. An
$r$-execution $(I,S)$ _ends_ at a configuration $C$ if each agent $a_{i}$ has
the local state $C(i)$ after the execution of the sequence of communication
rounds described by $S$ with the inputs stated by $I$; alternatively, we say
that $C$ is the configuration at the _end_ of $(I,S)$. Note that for the empty
sequence, denoted $[\,]$, $I$ is the configuration at the end of the
$0$-execution $(I,[\,])$, for every input vector $I$.

#### Our representation.

$\mathit{in}_{a,0},$$\mathit{in}_{b,1}$$(0\mathit{,}1)$$\mathit{in}_{a,1},$$\mathit{in}_{b,1}$$(1\mathit{,}1)$$\mathit{in}_{a,0},$$\mathit{in}_{b,0}$$(0\mathit{,}0)$$\mathit{in}_{a,1},$$\mathit{in}_{b,0}$$(1\mathit{,}0)$$b$$a$$a$$b$
Figure 2: Model $M^{0}$ for agents $a$ and $b$ with binary inputs.

We use _epistemic models_ , that we name $M^{r}$, for representing the
$r$-executions of a given adversary $\mathit{Adv}$. An _epistemic model_ for
$\mathit{Ag}$ and a set of propositions $\mathit{Props}$ is a triple $M=$
$(W,\sim,L)$, where $W$ is a finite set of worlds,
$\sim\;:\mathit{Ag}\rightarrow\wp(W\times W)$ assigns an equivalence relation
to each agent, and $L:W\rightarrow\wp({\it Props})$ assigns a set of true-
valued propositions to each world. Each world in $M^{r}$ represents an
$r$-execution and the accessibility relations represent the
indistinguishability relations over the configurations at the end of the
$r$-executions of $\mathit{Adv}$.

#### The initial epistemic model ($M^{0}$).

We build the initial epistemic model $M^{0}=(W^{0},\sim^{0},L^{0})$ for
$\mathit{Ag}$ and $\mathit{In}$ with $\mathit{Props}=\\{in_{a,v}\mid
a\in\mathit{Ag}\land v\in\mathit{In}\\}$ so that $W^{0}=\\{I\mid I\textrm{ is
an input vector for $\mathit{Ag}$ and $\mathit{In}$}\\}$,
$I\sim^{0}_{\mathit{a}_{i}}I^{\prime}$ if and only if $I(i)=I^{\prime}(i)$,
and $L(I)=\\{in_{a_{i},v}\in\mathit{Props}\mid I(i)=v\\}$. The epistemic model
$M^{0}$ for the agents $\mathit{Ag}=\\{a,b\\}$ and binary inputs
$\mathit{In}=\\{0,1\\}$ is depicted in Fig. 2.

##  4 Action models and the IIS model

In this section, we first present the IIS model. Next, we give the definition
of action models. Finally, we exhibit our best action-model solution of
modeling IIS for agents $a$ and $b$ with binary inputs.

###  4.1 Iterated Immediate Snapshot distributed-computing model

$\mathit{in}_{a,0},$$\mathit{in}_{b,0}$$(0\mathit{,}\\{b\\}\\{a\\})$$\mathit{in}_{a,0},$$\mathit{in}_{b,0}$$(0\mathit{,}\\{a\mathit{,}b\\})$$\mathit{in}_{a,0},$$\mathit{in}_{b,0}$$(0\mathit{,}\\{a\\}\\{b\\})$$\mathit{in}_{a,0},$$\mathit{in}_{b,1}$$(1\mathit{,}\\{a\\}\\{b\\})$$\mathit{in}_{a,0},$$\mathit{in}_{b,1}$$(1\mathit{,}\\{a\mathit{,}b\\})$$\mathit{in}_{a,0},$$\mathit{in}_{b,1}$$(1\mathit{,}\\{b\\}\\{a\\})$$\mathit{in}_{a,1},$$\mathit{in}_{b,1}$$(3\mathit{,}\\{b\\}\\{a\\})$$\mathit{in}_{a,1},$$\mathit{in}_{b,1}$$(3\mathit{,}\\{a\mathit{,}b\\})$$\mathit{in}_{a,1},$$\mathit{in}_{b,1}$$(3\mathit{,}\\{a\\}\\{b\\})$$\mathit{in}_{a,1},$$\mathit{in}_{b,0}$$(2\mathit{,}\\{a\\}\\{b\\})$$\mathit{in}_{a,1},$$\mathit{in}_{b,0}$$(2\mathit{,}\\{a\mathit{,}b\\})$$\mathit{in}_{a,1},$$\mathit{in}_{b,0}$$(2\mathit{,}\\{b\\}\\{a\\})$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$b$
Figure 3: Epistemic model $M_{\mathrm{IIS}}^{1}$ that represents the
configurations at the end of the first round of the full-information protocol
for two agents $a$ and $b$ with binary inputs in the IIS model.

The IIS model [6] is a fundamental model that fully captures what can be
solved in asynchronous wait-free shared-memory systems with process-crash
failures. We can define IIS as a (failure-free) synchronous oblivious dynamic-
network adversary. The set describing the adversary is as follows. For every
sequence of non-empty subsets of $\mathit{Ag}$, $S=[C_{1},C_{2},\dots,C_{k}]$,
satisfying that $Ag=\bigcup C_{i}$ and $C_{i}\cap C_{j}=\emptyset$ whenever
$i\neq j$, the adversary has the communication graph with a directed edge
$(a,b)$ for every pair of agents $a\in C_{i},b\in C_{j}$ with $1\leq i\leq
j\leq k$. We say that $C_{i}$ is a _concurrency class_. In Fig. 3, we show the
epistemic model $M_{\mathrm{IIS}}^{1}$ that represents the configurations at
the end of the first round of the full-information protocol for processes $a$
and $b$ with binary input in the IIS model.

###  4.2 Action models

Action models were introduced in [2] as a general way to model dynamics of
knowledge via events.

######  Definition 1 (Action model).

An _action model_ $\mathit{A}$ is a triple $\mathit{(E,R,Pre)}$, where
$\mathit{E}$ is a non-empty finite set of events,
$\mathit{R:P\rightarrow\wp(E\times E)}$ is a function that associates each
agent with a relation over the set of events, and
$\mathit{Pre:E\rightarrow\mathcal{L}_{K}}$ is a function that associates each
event with a precondition.

######  Definition 2 (Syntax).

Let $\mathit{A}\mathit{=(E,R,Pre)}$ be an action model over $\mathit{Ag}$ and
$\mathit{Props}$. The language $\mathcal{L}_{\otimes}$ is given by the
following BNF
$\varphi::=p\mid\lnot\varphi\mid~{}\varphi\land\varphi~{}|~{}K_{a}\varphi~{}|~{}[(\mathit{A},\mathit{e})]\varphi$,
where $a\in\mathit{Ag}$, and $p\in\mathit{Props}$, $\mathit{e}\in\mathit{E}$
and $(\mathit{A},\mathit{e})$ is an update.

######  Definition 3 (Restricted modal product).

Let $\mathit{M}=(W,\sim,L)$ be an epistemic model over $\mathit{Ag}$ and
$\mathit{Props}$. Let $\mathit{A}\mathit{=(E,R,Pre)}$ be an action model.
$\mathit{M}^{\prime}=\mathit{(W^{\prime},\sim^{\prime},L^{\prime})}=\mathit{M}\otimes\mathit{A}$
is defined as follows:

  * •

$\mathit{W}^{\prime}=\\{(\mathit{w},\mathit{e})\in\mathit{W}\times\mathit{E}\mid
M,w\models\mathit{Pre(e)}\\}$

  * •

$\sim^{\prime}_{a}\;=\\{((\mathit{w},\mathit{e}),(\mathit{w}^{\prime},\mathit{e}^{\prime}))\in\mathit{W}^{\prime}\times\mathit{W}^{\prime}\mid
w\sim_{a}w^{\prime}\;\land\;e\;R_{a}\;e^{\prime}\\}$

  * •

$\mathit{L}^{\prime}((w,e))=\mathit{L}(w)$

######  Definition 4 (Semantics).

Let $M=(W,R,L)$ be an epistemic model over $\mathit{Ag}$ and $\mathit{Props}$.
Let $\mathit{A}\mathit{=(E,R,\mathit{Pre})}$ be an action model. Let
$p\in\mathit{Props}$ be a proposition. Let $w,w^{\prime}\in W$ be worlds. Let
$a\in\mathit{Ag}$ be an agent. Let $\mathit{e\in E}$ be an event. Let
$\varphi,\psi\in\mathcal{L}_{\otimes}$ be formulas.

$\displaystyle M,w$ $\displaystyle\models p$ iff $\displaystyle~{}p\in L(w)$
$\displaystyle M,w$ $\displaystyle\models\lnot\varphi$ iff $\displaystyle
M,w\not\models\varphi$ $\displaystyle M,w$
$\displaystyle\models\varphi\land\psi$ iff $\displaystyle
M,w\models\varphi~{}\textrm{and}~{}M,w\models\psi$ $\displaystyle M,w$
$\displaystyle\models K_{p}\varphi$ iff $\displaystyle
M,w^{\prime}\models\varphi~{}\textrm{for~{}all~{}$w^{\prime}$~{}such~{}that
}~{}w\;R(p)\;w^{\prime}$ $\displaystyle M,w$
$\displaystyle\models[(\mathit{A},\mathit{e})]\varphi$ iff $\displaystyle
M,w\models\mathit{Pre}(e)\textrm{~{}implies~{}}M\otimes\mathit{A},(\mathit{w},\mathit{e})\models\varphi$

###  4.3 Our best action-model solution for IIS

$\\{a\\}\\{b\\}$
---
$a$$b$
$\\{b\\}\\{a\\}$
$a$$b$
$\\{a,b\\}$
$a$$b$
Figure 4: Communication graphs for two-agent IIS.

We now present our best action-model approach of modeling IIS for agents $a$
and $b$ with binary inputs. We exploit the fact that for two-agent IIS, _the
epistemic models will always be bipartite graphs_. We can hence partition the
set of worlds in $M^{i}$ into two sets $W_{1}^{i}$ and $W_{2}^{i}$ so that any
pair of distinct worlds in the same set can be distinguished by both agents.
For each set $W^{i}_{j}$, we use three events to represent the different
sequences of concurrency classes that can happen in a round: $\\{a\\}\\{b\\}$,
$\\{a,b\\}$, and $\\{b\\}\\{a\\}$ (see Fig. 4). Thus we have six events: three
for operating with the worlds in $W^{i}_{1}$, and three for operating with the
worlds in $W^{i}_{2}$. The sketch of the action model is shown in Fig. 5. In
such a sketch, the preconditions, $\phi_{1}$ and $\phi_{2}$, change from round
to round. $\phi_{j}$ is a disjunction of formulas identifying the worlds in
$W^{i}_{j}$. A formula identifying a world is a conjunction of the formulas
describing the local state of each agent. In Appendix A, we define functions
that compute an epistemic logic formula that describes the local state of an
agent. For the first round, if we consider $W_{1}^{0}=\\{(0,0),(1,1)\\}$ and
$W_{2}^{0}=\\{(0,1),(1,0)\\}$, the preconditions are:
$\phi_{1}=(\mathit{in}_{a,0}\land\mathit{in}_{b,0})\lor(\mathit{in}_{a,1}\land\mathit{in}_{b,1})$,
and
$\phi_{2}=(\mathit{in}_{a,0}\land\mathit{in}_{b,1})\lor(\mathit{in}_{a,1}\land\mathit{in}_{b,0}).$

This approach appears to be a succinct representation of the full-information
execution dynamics. There are, however, still issues. We would like to
represent communication defined by an oblivious model _just once_ because the
allowed communication patterns are the same regardless of the round. All
correct action models we have been able to find have preconditions that change
from round to round. Moreover, the size of the formulas we get from the
$\varphi$ functions grows exponentially in the number of rounds. This suggests
that in certain cases, a straightforward application of action models might
not be ideal.

$\phi_{2}$$\\{a\\}\\{b\\}_{2}$$\phi_{2}$$\\{a\mathit{,}b\\}_{2}$$\phi_{2}$$\\{b\\}\\{a\\}_{2}$$\phi_{1}$$\\{b\\}\\{a\\}_{1}$$\phi_{1}$$\\{a\mathit{,}b\\}_{1}$$\phi_{1}$$\\{a\\}\\{b\\}_{1}$$b$$a$$b$$a$$b$$a$
Figure 5: Sketch of the action model for two-agent IIS with binary inputs.

We have not been able to find a similar family of action models for three
agents. We would need to analyze if the corresponding epistemic models are
always $n$-partite, and how we could join all the needed events. Finding
action models for the case of $m$-ary inputs for $m\geq 3$ would be even
harder. Making things worse, the analysis might be different in distinct
models: we would need to study each model to take advantage of its own
characteristics. All these facts motivated us to look for a different and more
appropriate approach.

##  5 Communication pattern models

Intuitively, a communication pattern model can be viewed as a non-directed
graph whose vertices have two labels: a formula and a communication graph.

###  5.1 Definition of communication pattern models

First, we define our _communication pattern models_. Then, we define the
syntax of our language. After that, we define our restricted modal product.
Finally, we define our language semantics.

######  Definition 5 (Communication pattern model).

$\mathcal{P}$ is a tuple $\mathit{(CP,R,Pre,\overline{N})}$, where
$\mathit{CP}$ is a non-empty finite set whose elements are called
_communication patterns_ , $\mathit{R:\mathit{Ag}\rightarrow\wp(CP\times CP)}$
is a function that associates each agent with an equivalence relation over the
set of communication patterns, $\mathit{Pre:CP\rightarrow\mathcal{L}_{K}}$ is
a function that associates each communication pattern with a precondition, and
$\mathit{\overline{N}:CP\times\mathit{Ag}\rightarrow\wp(\mathit{Ag})}$ is a
function that associates a (communication pattern,agent)-pair with a subset of
$\mathit{Ag}$.

We can think of communication patterns $\mathit{cp}\in\mathit{CP}$ as
communication events. The $\mathit{\overline{N}}$ function describes the
communication graph associated with a communication pattern:
$\mathit{\overline{N}(cp,\mathit{a})}$ is the in-neighborhood of $a$ in such a
communication graph.

######  Definition 6 (Syntax).

Let $\mathcal{P}$ be a communication pattern model over $\mathit{Ag}$ and
$\mathit{Props}$. The language $\mathcal{L}_{\odot}$ is given by the following
BNF:

$\varphi::=p\mid\lnot\varphi\mid~{}\varphi\land\varphi~{}|~{}K_{a}\varphi~{}|~{}[(\mathcal{P},\mathit{cp})]\varphi$

where $p\in Props$, $a\in\mathit{Ag}$, $\mathit{cp\in CP}$ and
$(\mathcal{P},\mathit{cp})$ is an update.

######  Definition 7 (Restricted modal product).

Let $\mathit{M}=(W,\sim,L)$ be an epistemic model over $\mathit{Ag}$ and
$\mathit{Props}$. Let $\mathcal{P}\mathit{=(CP,R,Pre,\overline{N})}$ a
communication pattern model. Let $a\in\mathit{Ag}$ an agent.
$(W^{\prime},\sim^{\prime},L^{\prime})=\mathit{M}^{\prime}=\mathit{M}\odot\mathcal{P}$
is defined as follows:

  * •

$W^{\prime}=\\{(w,\mathit{cp})\in W\times\mathit{CP}\mid w\in
W\,\land\,\mathit{cp\in CP}\,\land\,M,w\models\mathit{Pre}(\mathit{cp})\\}$

  * •

$\sim^{\prime}_{a}=\\{((w,\mathit{cp}),(w^{\prime},\mathit{cp^{\prime}}))\in
W^{\prime}\times W^{\prime}\mid
w\sim_{a}w^{\prime}\,\land\,\mathit{cp}\;R_{a}\;\mathit{cp}^{\prime}\;\land$
$\underline{\mathit{\overline{N}}(\mathit{cp},a)=\mathit{\overline{N}}(\mathit{cp^{\prime}},a)}\,\land$
$\underline{w\sim_{a^{\prime}}w^{\prime}~{}\forall
a^{\prime}\in\mathit{\overline{N}}(\mathit{cp},a)}\\}$

  * •

$L^{\prime}((w,\mathit{cp}))=L(w)$

Intuitively, the first underlined condition requires agent $a$ to receive
information from the same set of processes in both $\mathit{cp}$ and
$\mathit{cp}^{\prime}$, and the second one requires all processes in such a
set to send the same information since such processes are required not to
distinguish between $w$ and $w^{\prime}$.

######  Definition 8 (Semantics).

Let $\mathit{M}=(W,\sim,L)$ be an epistemic model over $\mathit{Ag}$ and
$\mathit{Props}$. Let $w,w^{\prime}\in W$ be worlds. Let $a\in\mathit{Ag}$ be
an agent. Let $\mathcal{P}=\mathit{(CP,R,Pre,\overline{N})}$ be a
communication pattern model. Let $\mathit{cp}\in\mathit{CP}$ be a
communication pattern. Let $\varphi,\psi\in\mathcal{L}_{\odot}$ be formulas.

$\displaystyle M,w$ $\displaystyle\models p$ iff $\displaystyle~{}p\in L(w)$
$\displaystyle M,w$ $\displaystyle\models\lnot\varphi$ iff $\displaystyle
M,w\not\models\varphi$ $\displaystyle M,w$
$\displaystyle\models\varphi\land\psi$ iff $\displaystyle
M,w\models\varphi~{}\textrm{and}~{}M,w\models\psi$ $\displaystyle M,w$
$\displaystyle\models K_{a}\varphi$ iff $\displaystyle
M,w^{\prime}\models\varphi~{}\textrm{for all $w^{\prime}$ such that
}~{}w\sim_{a}w^{\prime}$ $\displaystyle M,w$
$\displaystyle\models[(\mathcal{P},\mathit{cp})]\varphi$ iff $\displaystyle
M,w\models\mathit{Pre}(\mathit{cp})\textrm{ implies
}M\odot\mathcal{P},(w,\mathit{cp})\models\varphi$

#### Action models and communication pattern models.

Communication pattern models are at least as general as action models. Notice
that we can build a _degenerate_ communication pattern model given an action
model. Let $\mathit{A}\mathit{=(E,R,Pre)}$ be an action model. We build a
communication pattern model
$\mathcal{P}\mathit{=(\mathit{E,R,Pre},\mathit{\overline{N}})}$ so that
$\mathit{\overline{N}}(e,a)=\emptyset~{}\forall(e,a)\in\mathit{E}\times\mathit{Ag}$.
It is easy to see that
$\mathit{M}\otimes\mathit{A}=\mathit{M}\odot\mathcal{P}$ holds.

###  5.2 Communication pattern models for arbitrary adversaries

Consider any adversary $Adv$ and the initial model $M^{0}$ defined in Section
3. Here we define an infinite sequence
$\mathcal{P}^{1},\mathcal{P}^{2},\ldots$ of communication pattern models that
succinctly model the evolution of knowledge in the executions of $Adv$. More
precisely, Theorem 1 in the next section will show that the epistemic model
$\mathit{M}^{r}=(W^{r},\sim^{r},L^{r})=\mathit{M}^{0}\odot\mathcal{P}^{1}\odot\mathcal{P}^{2}\odot\dots\odot\mathcal{P}^{r}$
captures how knowledge changes after $r$ rounds of communication.

For every $i\geq 1$, the communication pattern model
$\mathcal{P}^{i}=\mathit{(CP^{i},R^{i},Pre^{i},\overline{N}^{i})}$ is defined
as follows:

  * •

$CP^{i}=\\{\mathit{cp}\in CP_{\mathit{Ag}}\,|\hbox{ $\exists$ an $i$-execution
$(I,S\cdot\mathit{cp})$ of $Adv$}\\}$.

  * •

For every $a\in Ag$,
$\mathit{R}^{i}_{a}=\\{\mathit{(cp,cp^{\prime})}\in\mathit{CP}^{i}\times\mathit{CP}^{i}\mid
N^{-}_{\mathit{cp}}(a)=N^{-}_{\mathit{cp}^{\prime}}(a)\\}$.

  * •

For every $(\mathit{cp},a)\in\mathit{CP}^{i}\times\mathit{Ag}$,
$\mathit{\overline{N}^{i}}(\mathit{cp},a)=N^{-}_{\mathit{cp}}(a)$.

  * •

For every $\mathit{cp}\in CP^{i}$, let
$\mathit{\mathcal{W}^{i-1}_{cp}}=\\{(I,S)|\hbox{ $\exists$ an $i$-execution
$(I,S\cdot\mathit{cp})$ of $Adv$}\\}$. Thus,
$\mathit{Pre}^{i}(\mathit{cp})=\bigvee_{(I,S)\in\mathcal{W}^{i-1}_{\mathit{cp}}}\varphi(I,S),$
where $\varphi(I,S)=\bigvee_{0\leq i\leq n}\varphi_{i}(a_{i},C(i)).$ See
Appendix A for the definition of $\varphi_{i}$.

#### The case of oblivious dynamic-network models.

$\top$$\\{a\\}\\{b\\}$$\top$$\\{a\mathit{,}b\\}$$\top$$\\{b\\}\\{a\\}$$b$$a$
Figure 6: Communication pattern model $\mathcal{P}_{\hbox{two-IIS}}$ for two-
agent IIS.

Following the definition of $\mathit{CP}^{i}$, we can see that, for any
oblivious adversary $Adv$, $CP^{i}=Adv$, for each $i\geq 1$. Thus, all
$\mathcal{P}^{i}$ have the same set of communication patterns. Moreover, for
each $\mathit{cp}\in\mathit{CP}^{i}$, $\mathcal{W}^{i-1}_{\mathit{cp}}$
contains _all_ $(i-1)$-executions of $Adv$, and hence
$\mathit{Pre}^{i}(\mathit{cp})$ can be set to $\top$. Therefore,
$\mathcal{P}^{1}=\mathcal{P}^{2}=\ldots$ The communication pattern model
representing dynamics for IIS with agents $a$ and $b$ is depicted in Fig. 6.
For clarity, the function $\overline{N}$ is not depicted; however, it can be
obtained from the in-neighborhoods of the communication graphs in Fig. 4. It
is worth observing that the communication pattern in Fig. 6, omitting
$\overline{N}$, and the usual modal product $\otimes$ do not model IIS for two
agents, not even for the first round. Namely,
$M^{1}=M^{0}\otimes\mathcal{P}_{\hbox{two-IIS}}$ has “undesirable” pairs in
agent relations which make $M^{1}$ structurally different from a 12-cycle,
which is the structure of the epistemic model for two processes with binary
inputs after one round of communication in IIS (see Fig. 3).

###  5.3 The $\odot$ product reflects the change in local states through
rounds

The dynamic epistemic logic that we present is focused on reasoning about
computations. In particular, we are interested in modeling how
_configurations_ change in the full-information protocol. A key point is that
when updating an epistemic model with our modal product, the resulting
epistemic model models how the local states of agents change. Theorem 1 below
states that our communication pattern models do model knowledge dynamics. The
theorem formalizes this claim using the following notion.

Let $\mathit{Adv}$ be an adversary. For every $i\geq 0$, we define the set
$\mathcal{C}_{\mathit{Adv}}^{i}=\\{C\mid\textrm{there is an $i$-execution
$(I,S)$ of }$ $\textrm{$\mathit{Adv}$ that ends in the configuration }C\\}.$
Let $\mathcal{P}^{1},\mathcal{P}^{2},\ldots\,$ be an infinite sequence of
communication pattern models. We say that the sequence
$\mathcal{P}^{1},\mathcal{P}^{2},\ldots\,$ _reflects_ the adversary
$\mathit{Adv}$ if for each $r\geq 1$, there is a bijection
$f^{r}:W^{r}\rightarrow\mathcal{C}_{\mathit{Adv}}^{r}$ such that
$w\sim_{a_{i}}w^{\prime}$ if and only if $a_{i}$ does not distinguish between
$f^{r}(w)$ and $f^{r}(w^{\prime})$, where $M^{0}$ is the initial epistemic
model and
$M^{r}=(W^{r},\sim^{r},L^{r})=M^{0}\odot\mathcal{P}^{1}\odot\mathcal{P}^{2}\odot\dots\odot\mathcal{P}^{r}$.
If $\mathcal{P}^{1}=\mathcal{P}^{2}=\ldots\,$, we simply say that
$\mathcal{P}^{1}$ reflects $\mathit{Adv}$.

######  Theorem 1 (Main result).

Let $\mathit{Adv}$ be an adversary and
$\mathcal{P}^{1},\mathcal{P}^{2},\ldots\,$ be the communication pattern models
built from $\mathit{Adv}$, as described in Subsection 5.2. Then,
$\mathcal{P}^{1},\mathcal{P}^{2},\ldots\,$ reflects $\mathit{Adv}$.

Let $\mathcal{E}_{\mathit{Adv}}^{r}$ be the set of all $r$-executions of
$\mathit{Adv}$. Let $I,I^{\prime}$ be two input vectors for $\mathit{Ag}$ and
$\mathit{In}$. The proof of Theorem 1 will be as follows. First, we will
present two lemmas whose proof we omit because of space restrictions. Then, we
will prove by induction that $w_{r}\sim_{a_{i}}w_{r}^{\prime}$ if and only if
$a_{i}$ does not distinguish between $f^{r}(w_{r})$ and
$f^{r}(w_{r}^{\prime})$.

Consider
$E_{r+1}=(I,[\mathit{cp}_{1},\mathit{cp}_{2},\dots,\mathit{cp}_{r},\mathit{cp}_{r+1}])\in\mathcal{E}_{\mathit{Adv}}^{r+1}$,
and
$E_{r}=(I,[\mathit{cp}_{1},\mathit{cp}_{2},\dots,\mathit{cp}_{r}])\in\mathcal{E}_{\mathit{Adv}}^{r}$.
We define
$g^{r}:\mathcal{E}_{\mathit{Adv}}^{r}\rightarrow\mathcal{C}_{\mathit{Adv}}^{r}$
as follows:

$g^{0}((I,[\,]))=I.$

$g^{r+1}(E_{r+1})=C_{r+1}=(C_{r+1}(1),C_{r+1}(2),\dots,C_{r+1}(n))$

where

$C_{r+1}(i)(j)=\begin{cases}g^{r}(E_{r})(j)&\textrm{if
}a_{j}\in{N}^{-}_{\mathit{cp}_{r+1}}(a_{i})\cup\\{a_{i}\\}\\\
\bot&\textrm{otherwise}\end{cases}.$

######  Lemma 1.

$g^{r}$ is a bijection.

Consider
$w_{r}=(\dots((I,\mathit{cp}_{1}),\mathit{cp}_{2})\dots,\mathit{cp}_{r})\in
W^{r}$. We define $h^{r}:W^{r}\rightarrow\mathcal{E}_{\mathit{Adv}}^{r}$ as
follows:

$h^{r}(w_{r})=(I,[\mathit{cp}_{1},\mathit{cp}_{2},\dots,\mathit{cp}_{r}]).$

######  Lemma 2.

$h^{r}$ is a bijection.

Now, we start with the proof of Theorem 1.

###### Proof.

We define

$f^{r}:W^{r}\rightarrow\mathcal{C}^{r}=g^{r}\circ h^{r}.$

Since $g^{r}$ and $h^{r}$ are bijective, $f^{r}$ is bijective.

Now we prove, by induction on the round number $r$, that the epistemic model
$\mathit{M}^{r}$ reflects indistinguishability between configurations.

Base case.

Consider $I,I^{\prime}\in W^{0}$, $C_{I}=f^{0}(I)=(I(1),I(2),\dots,I(n))$, and
$C_{I^{\prime}}=f^{0}(I^{\prime}=(I^{\prime}(1),I^{\prime}(2),\dots,I^{\prime}(n))$.
By construction of $\sim^{0}$, $I\sim^{0}_{a_{i}}I^{\prime}$ if and only if
$I(i)=I^{\prime}(i)$ holds. Since $\mathit{a}_{i}$ does not distinguish
between $C_{I}$ and $C_{I^{\prime}}$ if and only if $I(i)=I^{\prime}(i)$
holds, $I\sim^{0}_{a_{i}}I^{\prime}$ if and only if $\mathit{a}_{i}$ does not
distinguish between $C_{I}$ and $C_{I^{\prime}}$ holds.

Inductive hypothesis.

Consider
$\mathit{M}^{r}=(W^{r},\sim^{r},L^{r})=\mathit{M}^{0}\odot\mathcal{P}^{1}\odot\mathcal{P}^{2}\odot\dots\odot\mathcal{P}^{r}$,
and $w_{r},w_{r}^{\prime}\in W^{r}$. We assume that
$f_{r}:W^{r}\rightarrow\mathcal{C}_{\mathit{Adv}}^{r}$ satisfies that
$w_{r}\sim^{r}_{a_{i}}w_{r}^{\prime}$ if and only if $\mathit{a}_{i}$ does not
distinguish between $f^{r}(w_{r})$ and $f^{r}(w_{r}^{\prime})$.

Inductive step.

Consider
$w_{r+1}=(w_{r},cp_{r+1}),w_{r+1}^{\prime}=(w_{r}^{\prime},cp_{r+1}^{\prime})\in
W^{r+1}$. We need to prove that $w_{r+1}\sim^{r+1}_{a_{i}}w_{r+1}^{\prime}$ if
and only if $a_{i}$ does not distinguish between $f^{r+1}(w_{r+1})$ and
$f_{r+1}(w_{r+1}^{\prime})$.

Consider $w_{r+1},w_{r+1}^{\prime}\in W^{r+1}$. By definition of $f^{r+1}$, we
know that

$f^{r+1}(w_{r+1})=C_{r+1}=(C_{r+1}(1),C_{r+1}(2),\dots,C_{r+1}(n))$

where

$C_{r+1}(i)(j)=\begin{cases}f^{r}(w_{r})(j)&\textrm{if
}a_{j}\in\overline{N}^{r+1}(\mathit{cp}_{r+1},\mathit{a}_{i})\cup\\{a_{i}\\}\\\
\bot&\textrm{otherwise}\end{cases}$

and

$f^{r+1}(w_{r+1}^{\prime})=C_{r+1}\,^{\prime}=(C_{r+1}^{\prime}(1),C_{r+1}^{\prime}(2),\dots,C_{r+1}^{\prime}(n))$

where

$C_{r+1}^{\prime}(i)(j)=\begin{cases}f^{r}(w_{r}^{\prime})(j)&\textrm{if
}a_{j}\in\overline{N}^{r+1}(\mathit{cp}_{r+1}^{\prime},\mathit{a}_{i})\cup\\{a_{i}\\}\\\
\bot&\textrm{otherwise}\end{cases}.$

By the definition of $\odot$,
$w_{r+1}\sim^{r+1}_{\mathit{a}_{i}}w_{r+1}^{\prime}$ if and only if
$w_{r}\sim^{r}_{\mathit{a}_{i}}w_{r}^{\prime}$,
$\mathit{cp}_{r+1}\;R^{r+1}_{\mathit{a}_{i}}\;\mathit{cp}_{r+1}^{\prime}$,
$\overline{N}^{r+1}(\mathit{cp}_{r+1},\mathit{a}_{i})=\overline{N}^{r+1}(\mathit{cp}_{r+1}^{\prime},\mathit{a}_{i})$,
and
$w_{r}\sim^{r}_{\mathit{a}_{j}}w_{r}^{\prime}\;\forall\mathit{a}_{j}\in\overline{\mathit{N}}^{r+1}(cp_{r+1},\mathit{a}_{i})$.

$C_{r+1}(i)(j)=\bot$ if and only if $C_{r+1}^{\prime}=\bot$ holds because by
construction of $\mathcal{P}^{r+1}$,
$cp_{r+1}\;R^{r+1}_{\mathit{a}_{i}}\;cp_{r+1}^{\prime}$ if and only if
$\overline{N}^{r+1}(cp_{r+1},\mathit{a}_{i})=\overline{N}^{r+1}(cp_{r+1},\mathit{a}_{i})$
holds. Then, $C_{r+1}(i)(j)=C_{r+1}(i)(j)$ holds if and only if
$f^{r}(w_{r})(j)=f^{r}(w_{r}^{\prime})(j)$ holds for all agents in
$\overline{N}^{r+1}(cp_{r+1},\mathit{a}_{i})$. By the inductive hypothesis, we
have that $f^{r}(w_{r})(j)=f^{r}(w_{r}^{\prime})(j)\;\forall
a_{j}\in\overline{N}^{r+1}(cp_{r+1},\mathit{a}_{i})$ holds. Then,
$w_{r+1}\;\sim^{r+1}_{\mathit{a}_{i}}\;w_{r+1}^{\prime}$ holds if and only if
$C_{r+1}(i)(j)=C_{r+1}^{\prime}(i)(j)$. $C_{r+1}(i)(j)=C_{r+1}^{\prime}(i)(j)$
holds if and only if $C_{r+1}(i)=C_{r+1}^{\prime}(i)$ holds. Hence,
$C_{r+1}(i)=C_{r+1}^{\prime}(i)$ holds if and only if $a_{i}$ does not
distinguish between $C_{r+1}$ and $C_{r+1}^{\prime}$.

∎

######  Corollary 1 (Constant space).

Modeling an oblivious adversary $\mathit{Adv}$ with communication pattern
models require constant space.

###### Proof.

Let $\mathcal{P}$ be the communication pattern model for $\mathit{Adv}$ built
as described in Subsection 5.2. By Theorem 1, $\mathcal{P}$ reflects
$\mathit{Adv}$. Moreover, $\mathcal{P}$ remains the same in all rounds. ∎

##  6 Related work

The formal treatment of knowledge in distributed computing was pioneered by
Halpern and Moses in [12]. Perhaps their most important result is having
proved that common knowledge amounts to simultaneity. The book by Fagin,
Halpern, Moses, and Vardi [10] was pivotal, as it summarized numerous results
and compared different approaches to studying many aspects of knowledge in a
system of agents.

Action models first appeared in [2]. Such a formalism, however, was only
considered for modeling evolution of knowledge in distributed systems, as far
as we know, in [11], by Goubault, Ledent, and Rajsbaum and in [18], by Pfleger
and Schmid.

Closer to our work is [11], where the authors exhibit a tight connection
between the topological approach [13] to distributed processing and Kripke
models. A second contribution of [11] is employing the _restricted modal
product_ operator of action models to model knowledge change between agents
after a round. A third important result is employing action models to
represent “tasks”. A task is the equivalent of a function in distributed
computability. The task defines the possible inputs to the agents, and for
each set of inputs, it specifies the set of outputs that the agents may
produce. By representing the task itself, the possibility of solving a task
amounts to the existence of a certain simplicial map.

The objective of [18], which uses action models as well, is that of obtaining
lower limits on the number of bits necessary for implementing a protocol that
is specified with an initial epistemic model and an infinite sequence of
action models that describe how the epistemic model is updated through an
infinite sequence of communication rounds. Like us, [18] uses dynamic-network
models. Unlike us, [18] assumes that the action model are given. As a result,
[18] does not build an action model and is not concerned with the size of the
action models.

The work in [3] exhibits drawbacks similar to the ones we found when using the
action model framework in other contexts. The authors propose an extension of
epistemic models adding a function and an update mechanism. Adding such a
function decreases the number of events needed to represent certain problems.
Our proposal, however, can be directly applied to the context of distributed
systems by the communication between agents.

##  7 Concluding Remarks

The formalization of knowledge in the distributed-computing literature has
still to have a more significant impact. The evidence is that many papers in
distributed computing refer to knowledge informally.

At the same time, in the epistemic-logic literature, the formalism of action
models has emerged as an important mechanism for modeling the evolution of
knowledge. Hence, the works by Goubault, Ledent, and Rajsbaum [11],
establishing a connection between action models and a topological approach to
distributed systems, and by Pfleger and Schmid [18], modeling a dynamic-
network protocol by an initial epistemic model and an infinite sequence of
action models, are relevant.

The approach of [11] operates an action model with an epistemic model
capturing knowledge at a certain point in time, to obtain a new epistemic
model for knowledge after one round of communication. We observed however,
that the action models proposed in [11] for IIS have certain inconveniences.
Such action models are structurally isomorphic to the desired epistemic model,
hence the number of events grows exponentially in the round number.

We proposed a family of action models with six events, for the case of two
agents with binary inputs, whose preconditions change from round to round. For
obtaining such a family however, we needed to know in advance the structure of
the epistemic models in further rounds. Furthermore, the analysis for more
agents or even more inputs seems to be more difficult. Hence, a generalization
of such a family is unclear for IIS. Moreover, the analysis would depend on
how the epistemic models change in different distributed-computing models.

To overcome these disadvantages, we proposed an extension of action models for
dealing with communication patterns, called _communication pattern models_.
Our models work for a large variety of distributed-computing models, called
dynamic-network models. Using our extension, we were able define communication
pattern models systematically for every round of execution in the full-
information protocol. In the case of oblivious models, which includes IIS, the
communication pattern model remains the same all through the computation. In
either case, our approach can be applied in automated distributed-systems
verification. We emphasize the fact that communication pattern models as
presented in this work are designed to deal with the full-information
protocol. We plan to analyze modifying definitions to deal with arbitrary
protocols.

Communication pattern models were presented as an extension of action models.
It is possible, however, to present the same idea with a set of communication
graphs. When analyzing arbitrary dynamic-network models, there should be a
precondition for each communication pattern. When analyzing oblivious models
there is no need of such precondition because it is always true. An advantage
of presenting communication pattern models as an extension of action models is
that of studying how an action model can be seen in an agent-communication
perspective.

An alternative approach to modeling distributed systems epistemically is by
the use of _interpreted_ systems, as in [12], or in the more recent papers by
Castañeda, Gonczarowski, and Moses [7], as well as Moses [16]. In these works,
protocols are modeled explicitly, and indistinguishability is generated
directly from the local states; consequently there is no need for a
communication pattern model (or an action model) that models the dynamics of
the system. Since we use epistemic models and communication pattern models, we
need to show that the indistinguishability relation that they generate
coincides with the one based on local states in the corresponding model, which
is shown in Theorem 1. A benefit of our approach, however, is that the
communication pattern models that we compute are arguably a succinct
representation of the communication that can occur in a model.

##  8 Acknowledgment

We should like to thank Hans van Ditmarsch for his insightful comments.

## References

  * [1]
  * [2] Alexandru Baltag, Lawrence S. Moss & Slawomir Solecki (1998): _The logic of public announcements, common knowledge, and private suspicions_.  In: Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 1998), pp. 43–56.  Available at http://dl.acm.org/citation.cfm?id=645876.671885.
  * [3] Adam Bjorndahl & Will Nalls (2021): _Endogenizing Epistemic Actions_.  Studia Logica, 10.1007/s11225-020-09937-8.
  * [4] Elizabeth Borowsky & Eli Gafni (1993): _Generalized FLP impossibility result for $t$-resilient asynchronous computations_.  In: Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC 1993), pp. 91–100, 10.1145/167088.167119.
  * [5] Elizabeth Borowsky & Eli Gafni (1993): _Immediate atomic snapshots and fast renaming (extended abstract)_.  In: Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing (PODC 1993), pp. 41–51, 10.1145/164051.164056.
  * [6] Elizabeth Borowsky & Eli Gafni (1997): _A simple algorithmically reasoned characterization of wait-free computation (extended abstract)_.  In: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing (PODC 1997), ACM, pp. 189–198, 10.1145/259380.259439.
  * [7] Armando Castañeda, Yannai A. Gonczarowski & Yoram Moses (2014): _Unbeatable Consensus_.  In Fabian Kuhn, editor: Distributed Computing, Springer Berlin Heidelberg, p. 91–106, 10.1007/978-3-662-45174-8_7.
  * [8] Bernadette Charron-Bost & André Schiper (2009): _The Heard-Of Model: Computing in Distributed Systems with Benign Faults_.  Distributed Comput. 22(1), pp. 49–71, 10.1007/s00446-009-0084-6.
  * [9] Hans van Ditmarsch, Wiebe van der Hoek & Barteld Kooi (2008): _Dynamic Epistemic Logic_.  Springer, 10.1007/978-1-4020-5839-4.
  * [10] Ronald Fagin, Joseph Y. Halpern, Yoram Moses & Moshe Y. Vardi (1995): _Reasoning about Knowledge_.  MIT Press, 10.7551/mitpress/5803.001.0001.
  * [11] Eric Goubault, Jérémy Ledent & Sergio Rajsbaum (2018): _A simplicial complex model for dynamic epistemic logic to study distributed task computability_.  In: Proceedings of the Ninth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2018), pp. 73–87, 10.4204/EPTCS.277.6.
  * [12] Joseph Y. Halpern & Yoram Moses (1984): _Knowledge and common knowledge in a distributed environment_.  In: Proceedings of the Third ACM Symposium on Principles of Distributed Computing (PODC 1984), pp. 50–61, 10.1145/79147.79161.
  * [13] Maurice Herlihy, Dmitry Kozlov & Sergio Rajsbaum (2014): _Distributed Computing Through Combinatorial Topology_.  Morgan-Kaufmann, 10.1016/C2011-0-07032-1.
  * [14] Maurice Herlihy & Nir Shavit (1993): _The asynchronous computability theorem for $t$-resilient tasks_.  In: Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC 1993), pp. 111–120, 10.1145/167088.167125.
  * [15] Fabian Kuhn & Rotem Oshman (2011): _Dynamic networks: models and algorithms_.  SIGACT News 42(1), pp. 82–96, 10.1145/1959045.1959064.
  * [16] Yoram Moses (2016): _Relating Knowledge and Coordinated Action: The Knowledge of Preconditions Principle_.  Electronic Proceedings in Theoretical Computer Science 215, p. 231–245, 10.4204/eptcs.215.17.
  * [17] Thomas Nowak, Ulrich Schmid & Kyrill Winkler (2019): _Topological Characterization of Consensus under General Message Adversaries_.  In Peter Robinson & Faith Ellen, editors: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), ACM, pp. 218–227, 10.1145/3293611.3331624.
  * [18] Daniel Pfleger & Ulrich Schmid (2018): _On knowledge and communication complexity in distributed systems_.  In: International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018), Springer, pp. 312–330, 10.1007/978-3-030-01325-7_27.
  * [19] Michael Zacks & Fotios Zaharoglou (1993): _Wait-free $k$-set agreement is impossible: the topology of public knowledge_.  In: Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC 1993), pp. 101–110, 10.1145/167088.167122.

##  Appendix A Views and epistemic formulas

Here, we first show a way of thinking about local states in distributed
computing called _views_. We then give a formal way of representing such views
with an epistemic-logic formula.

In the distributing-computing literature, it is common to regard the local
states of the agents as their views. We can think of a view of an agent as a
single variable whose value changes from round to round. Such a view takes
different values depending on the round.

######  Definition 9 (View).

Consider $S_{k}=[\mathit{cp}_{1},\mathit{cp}_{2},\dots,\mathit{cp}_{k}]$, and
$S_{k+1}$ = $S_{k}\cdot\mathit{cp}_{k+1}$ so that $(I,S_{k+1})$ is a
$k+1$-execution. The $\mathit{view}$ of an agent $a_{i}$ in a execution
$(I,S)$, $\mathit{view}(a_{i},(I,S))$ for short, in the full-information
protocol is defined inductively as follows:

$\mathit{view}(a_{i},(I,[\,]))=I(i).$
$\mathit{view}(a_{i},(I,S_{k+1}))=[\mathit{view}[1],\mathit{view}[2],\dots,\mathit{view}[n]]$

where

$\mathit{view}[j]=\begin{cases}\mathit{view}(a_{j},(I,S_{k}))&\textrm{if~{}}a_{j}\in
N^{-}_{\mathit{cp}_{k+1}}\cup\\{a_{i}\\}\\\
\bot&\textrm{otherwise}\end{cases}$

In the full-information protocol, each agent tries to communicate its whole
local state to the other agents. If $a_{i}$ receives a message from $a_{j}$,
$a_{i}$ will know all that $a_{j}$ knew in the previous round, otherwise
$a_{i}$ will not be able to know what $a_{j}$ could know.

Now, we formalize the notion of views building an epistemic logic formula for
the view of $a_{i}$.

######  Definition 10.

Let $\mathit{Views}^{k}$ be the set of all possible views of the agents in
$\mathit{Ag}$ at the end of the $k$-th round. Let $\mathit{Views}^{k}_{i}$ be
the set of all possible views of the agent $a_{i}$ at the end of the $k$-th
round. Consider
$\mathit{view}=[\mathit{view}[1],\mathit{view}[2],\dots,\mathit{view}[n]]\in\mathit{Views}^{k+1}$.
We define the functions
$\varphi_{k}:P\times\mathit{Views}^{k}\rightarrow\mathcal{L}_{K}$, for all
$k\in\mathbb{N}\cup\\{0\\}$ as follows:

$\varphi_{0}(a_{i},v)=in_{a_{i},v}.$

where $v\in\mathit{In}$.

$\varphi_{k+1}(a_{i},view)=\bigwedge\limits_{j=1}^{n}\begin{cases}K_{a_{i}}(\varphi_{k}(a_{j},\mathit{view}[j]))&\textrm{if}~{}\mathit{view}[j]\neq\bot\\\
\bigwedge\limits_{\mathit{view}^{\prime}\in\mathit{Views}^{k}_{j}}\lnot
K_{a_{i}}(\varphi_{k}(a_{j},\mathit{view}^{\prime}))&\textrm{otherwise}\end{cases}$


# Upper bounds for the blow-up time of a system of fractional differential
equations with Caputo derivatives and a numerical scheme for the solution of
the system

José Villa-Morales<EMAIL_ADDRESS>Departamento de Matemáticas y Física,
Universidad Autónoma de Aguascalientes, Av. Universidad 940, C.P. 20131
Aguascalientes, Ags., México

###### Abstract

The article provides upper bounds for the blow-up time of a system of
fractional differential equations in the Caputo sense. Furthermore, concrete
examples of blow-up time estimation are given using a numerical algorithm of
the predictor-corrector type.

###### keywords:

Blow-up time, upper bounds, Caputo’s fractional differential equations,
predictor-corrector.

###### MSC:

26A33, 34A08, 65R20, 34A40

##  1 Introduction

The study of fractional differential equations is a current topic in pure and
applied mathematics, this is due in large part to the need for new techniques
for their analysis and the multiple applications that this mathematical entity
has (see for example Kilbas et al. (2006), Zhan et al. (2014), Villa-Morales
et al. (2022) and the references it contains). Quite concisely, we can say
that the theoretical study of fractional differential equations has focused
primarily on proving existence and uniqueness theorems (see Zhou and Chua
(2012), Bai and Qiu (2009), Sun et al. (2012), Furati and Tatar (2004),
Messaoudi et al. (2007), Aldawish and Samet (2022)) or in giving criteria for
the non-existence of solutions (see Kirane et al. (2014), Laskri and Tatar
(2010), Kerbal (2010), Jleli et al. (2019)). Something similar occurs in the
context of fractional partial differential equations (see Kirane et al.
(2005), Cabral-García and Villa-Morales (2019)). This work is related to the
second topic, that is, criteria for the non-existence of global solutions.

Let us assume that $\alpha\in(0,1)$ and $q_{1}$, $q_{2}$, $p_{11}$, $p_{12}$,
$p_{21}$, $p_{22}$ are non-negative real numbers. In the paper, we will
consider the system of Caputo’s fractional differential equations,

${}^{C}D_{0+}^{\alpha}x(t)$ $\displaystyle=$ $\displaystyle
t^{q_{1}}x^{p_{11}}(t)y^{p_{12}}(t),\ \ t>0,$ (1.1)
${}^{C}D_{0+}^{\alpha}y(t)$ $\displaystyle=$ $\displaystyle
t^{q_{2}}y^{p_{21}}(t)x^{p_{22}}(t),\ \ t>0,$ (1.2)

with initial conditions

$x(0)>0,\ \ y(0)>0.$ (1.3)

We will say that the solution $(x(t),y(t))$ of the system (1.1)-(1.3) blows-up
(or explodes) in finite time if there is a positive real-number $\tau_{xy}$
such that the conditions (1.1)-(1.3) are satisfied for all $0\leq t<\tau_{xy}$
and

$\lim_{t\uparrow t_{xy}}\,\sup\\{|x(s)|+|y(s)|:s\in[0,t]\\}=\infty.$ (1.4)

The time $\tau_{xy}$ is called blow-up (or explosion) time. The objective of
this work is to give some conditions on the parameters of the system
(1.1)-(1.2) in order to obtain upper bounds of the explosion time $\tau_{xy}$,
as a consequence conditions under which the system has no global solution are
obtained, see Theorem 3.2.

It should be noted that, although it is a bit tedious, when $\alpha=1$ and
$q_{1}=q_{2}$ the explosion time of the system of ordinary differential
equations (1.1-(1.2) can be given explicitly. To the best of our knowledge,
there are no non-trivial fractional differential equations for which their
explosion time is explicitly known. In addition, it is convenient to point out
that there are practical applications of modeling with fractional differential
equations where the explosions occurs in a finite time. For example, this
occurs in the study of the fracture of materials or in the study of the
combustion of gases, see for example Zhan et al. (2014) or Bebernes and Eberly
(1989); in these cases, abrupt changes occur in the phenomenon under
consideration. Due to this, when modeling, it is convenient to have numerical
and mathematical methods that allow us to bound the blow-up time of a system
of interest.

Roughly speaking, it can be said that the difficulty of finding upper bounds
for the blow-up time of the system $(x(t),y(t))$, solution of (1.1)-(1.2),
consists of comparing the growth of the components of the system, that is,
verifying that, for example, after a certain time the component $x(t)$ is
greater than or equal to the component $y(t)$. When this occurs, the problem
is reduced, in a sense, to the study of a single fractional inequality, see
Proposition 3.1. In our case, we have overcome this difficulty by introducing
a new inequality related to the difference of the components of the system, so
we can determine if it is positive or negative, therefore we can compare the
components where the system has a solution, see the inequality (3.20). As far
as we know, there are no comparison theorems for the solutions of a system of
fractional differential equations that can be applied to this type of system;
for this reason, the technique for studying the blow-up time, as well as the
upper bounds obtained, seem new to us.

Since, in general, it is rare to obtain explicit solutions to a system of
differential equations, it is necessary to consider a numerical scheme to give
an idea of its solution. In our case, we adapt a numerical scheme that is a
modification of the fractional Euler method that considers a corrective term.
Using this numerical algorithm, it is possible to graphically estimate the
blow-up time of the system (1.1)-(1.2). Three illustrative numerical examples
are discussed.

The article is organized as follows. We present some definitions and certain
preliminary results in Section 2, here it is worth highlighting the important
Jensen’s type inequality (2.3). In Section 3, we study a fractional inequality
and prove the main result. Finally, in Section 4, we give a numerical
algorithm for solving a system of general fractional differential equations
and consider three illustrative numerical examples.

##  2 Preliminaries

In what follows we will assume that $\alpha\in(0,1)$ and $a$ will be a real
number. We will begin by recalling some definitions and basic properties that
will be useful to us. If $u(t)$ is an absolutely continuous function, then the
Caputo left hand-side fractional derivative is defined as

${}^{C}D_{a+}^{\alpha}u(t)=\frac{1}{\Gamma(1-\alpha)}\int_{a}^{t}\frac{u^{\prime}(s)ds}{(t-s)^{\alpha}},\
\ t>a,$ (2.1)

where $\Gamma$ is the usual gamma function.

On the other hand, the Riemann-Liouville right hand-side fractional derivative
of a function $u(t)$ is defined as

${}^{RL}D_{a-}^{\alpha}u(t)=-\frac{1}{\Gamma(1-\alpha)}\frac{d}{dt}\int_{t}^{a}\frac{u(s)ds}{(s-t)^{\alpha}},\
\ t<a.$

Another concept that we will use is the following, the Riemann-Liouville left-
side fractional integral of a function $u(t)$ is defined as

$I^{\alpha}_{a+}u(t)=\frac{1}{\Gamma(\alpha)}\int_{a}^{t}\frac{u(s)ds}{(t-s)^{1-\alpha}},\
\ t>a.$ (2.2)

We compile some basic properties in the next result.

######  Lemma 2.1.

Let $\beta$ be a real number, then

$\displaystyle\left({}^{RL}D_{a-}^{\alpha}(a-s)^{\beta-1}\right)(t)$
$\displaystyle=$ $\displaystyle\begin{cases}0,&\beta=\alpha,\\\
\frac{\Gamma(\beta)}{\Gamma(\beta-\alpha)}(a-t)^{\beta-\alpha-1},&\beta\neq\alpha.\end{cases}$
(2.3)

If the function $u(t)$ is continuous, then

$(I^{\alpha}_{a+}\,{}^{C}D_{a+}^{\alpha}u)(t)=u(t)-u(a),\ \ t>a.$ (2.4)

###### Proof.

The derivative (2.3) is formulae (2.1.19) and (2.1.20) in Kilbas et al.
(2006). On the other hand, Lemma 2.22 of Kilbas et al. (2006) contains formula
(2.4). ∎

For $\alpha>0$ and $\beta\in\mathbb{R}$ the Mittag-Leffler function
$E_{\alpha,\beta}$ is defined by

$E_{\alpha,\beta}(t)=\sum_{k=0}^{\infty}\frac{t^{k}}{\Gamma(\alpha k+\beta)},\
\ t\in\mathbb{R}.$ (2.5)

In particular, $E_{\alpha,1}$ will be denoted by $E_{\alpha}$.

We have the following elementary result.

######  Lemma 2.2.

Let us assume that $\lambda$ and $a$ are two real numbers and set

$e_{\alpha}^{\lambda(a-t)}:=(a-t)^{\alpha-1}E_{\alpha,\alpha}[\lambda(a-t)^{\alpha}],\
\ t<a.$ (2.6)

If $0<\alpha\leq 1$, then the function $e_{\alpha}^{\lambda(a-t)}$ is positive
and

${}^{RL}D_{a-}^{\alpha}e_{\alpha}^{\lambda(a-t)}-\lambda
e_{\alpha}^{\lambda(a-t)}=0,\ \ t<a.$ (2.7)

###### Proof.

To verify that $e_{\alpha}^{\lambda(a-t)}$ is positive it suffices to prove
that $E_{\alpha,\alpha}$ is positive. It is clear that
$E_{\alpha,\alpha}(t)>0$ if $t\geq 0$. On the other hand, the function
$E_{\alpha}(-t)$, with $t\geq 0$, is completely monotonic, namely

$E_{\alpha}(-t)=\int_{0}^{\infty}e^{-ts}dF_{\alpha}(s),$

where $F_{\alpha}(s)$ is a bounded function and $F^{\prime}_{\alpha}(s)\geq 0$
(moreover, an explicit expression for $F^{\prime}_{\alpha}(s)$ can be find in
Pollard (1948)). With this we deduce

$E_{\alpha,\alpha}(-t)=-\alpha\frac{d}{dt}E_{\alpha}(-t)=\alpha\int_{0}^{\infty}se^{-ts}dF_{\alpha}(s)>0.$

The equation (2.7) is easily established using the property (2.3) and the
linearity of the fractional derivative. ∎

######  Proposition 2.3.

Let $\gamma\geq 2$ and $u(t)$ be an absolutely continuous function on $(a,b)$.
If

$u(t)\geq u(0)\geq 0,\ \ t\in(a,b),$ (2.8)

then

${}^{C}D_{a+}^{\alpha}u^{\gamma}(t)\leq\gamma
u^{\gamma-1}(t)\,^{C}D_{a+}^{\alpha}u(t),\ \ t\in(a,b).$ (2.9)

###### Proof.

The Definition $(\ref{Capudef})$ and the use of Fubini’s theorem imply

$\displaystyle
u^{\gamma-1}(t)\,^{C}D_{a+}^{\alpha}u(t)-\frac{1}{\gamma}\,^{C}D_{a+}^{\alpha}u^{\gamma}(t)$
$\displaystyle=$
$\displaystyle\frac{1}{\Gamma(1-\alpha)}\int_{a}^{t}\frac{1}{(t-r)^{\alpha}}\left[u^{\gamma-1}(t)u^{\prime}(r)-u^{\gamma-1}(r)u^{\prime}(r)\right]dr$
$\displaystyle=$
$\displaystyle\frac{1}{\Gamma(1-\alpha)}\int_{a}^{t}\frac{u^{\prime}(r)}{(t-r)^{\alpha}}\int_{r}^{t}\frac{du^{\gamma-1}}{ds}(s)dsdr$
$\displaystyle=$
$\displaystyle\frac{1}{\Gamma(1-\alpha)}\int_{a}^{t}(\gamma-1)u^{\gamma-2}(s)u^{\prime}(s)\int_{a}^{s}\frac{u^{\prime}(r)}{(t-r)^{\alpha}}drds.$

Inasmuch as

$\frac{\partial}{\partial
s}\left(\int_{a}^{s}\frac{u^{\prime}(r)}{(t-r)^{\alpha}}dr\right)^{2}=\frac{2u^{\prime}(s)}{(t-s)^{\alpha}}\int_{a}^{s}\frac{u^{\prime}(r)}{(t-r)^{\alpha}}dr,$

then

$\displaystyle
u^{\gamma-1}(t)\,^{C}D_{a+}^{\alpha}u(t)-\frac{1}{\gamma}\,^{C}D_{a+}^{\alpha}u^{\gamma}(t)$
$\displaystyle=$
$\displaystyle\frac{\gamma-1}{2\Gamma(1-\alpha)}\int_{a}^{t}u^{\gamma-2}(s)(t-s)^{\alpha}\frac{\partial}{\partial
s}\left(\int_{a}^{s}\frac{u^{\prime}(r)}{(t-r)^{\alpha}}dr\right)^{2}ds.$

In this way, the usual integration by parts and the inequality (2.8) yield

$\displaystyle
u^{\gamma-1}(t)\,^{C}D_{a+}^{\alpha}u(t)-\frac{1}{\gamma}\,^{C}D_{a+}^{\alpha}u^{\gamma}(t)$
$\displaystyle\geq$
$\displaystyle\frac{(\gamma-1)u^{\gamma-2}(0)}{2\Gamma(1-\alpha)}\int_{a}^{t}(t-s)^{\alpha}\frac{\partial}{\partial
s}\left(\int_{a}^{s}\frac{u^{\prime}(r)}{(t-r)^{\alpha}}dr\right)^{2}ds$
$\displaystyle=$
$\displaystyle\frac{\alpha(\gamma-1)u^{\gamma-2}(0)}{2\Gamma(1-\alpha)}\int_{a}^{t}(t-s)^{\alpha-1}\left(\int_{a}^{s}\frac{u^{\prime}(r)}{(t-r)^{\alpha}}dr\right)^{2}ds.$

From here, the result evidently follows. ∎

The hypothesis $(\ref{desjen})$ in Proposition 2.3 is not necessary when
$\gamma=2$. In this case, the following references Alikhanov (2010) or Aguila-
Camacho et al. (2014) could be consulted.

##  3 Proof of the main result

Next, our first step will be to give an estimate of the blow-up time for a
fractional inequality. As is common, for $p\geq 1$ we denote by
$\tilde{p}\in(1,\infty]$ the conjugate index of $p$ defined by means of

$\frac{1}{p}+\frac{1}{\tilde{p}}=1.$

######  Proposition 3.1.

Let $K>0$, $q\geq 0$ and $p\geq 1$. Let $u(t)$ be a non-negative solution of
the following Caputo’s fractional inequality

${{}^{C}}D^{\alpha}_{0+}u(t)\geq Kt^{q}u^{p}(t),\ \ t>0,$ (3.1)

with initial condition

$u(0)=u_{0}>0.$

If $q+1>q\tilde{p}$, then $u(t)$ blows-up in finite time; moreover, the blow-
up time $\tau_{u}$ is less than or equal to

$\tau(u_{0},q,p):=\left(\frac{\Gamma(q(1-\tilde{p})+1)}{(u_{0})^{p}\Gamma(q+1)}B(\lambda_{m})\right)^{1/(\tilde{p}(\alpha+q))},$
(3.2)

where $B(\lambda_{m})=\min\\{B(\lambda):\lambda>\alpha\tilde{p}-1\\}$ with

$B(\lambda):=\frac{\Gamma(\lambda+1)^{\tilde{p}-1}\,\Gamma(\lambda+1-\alpha\tilde{p})\,\Gamma(q+\lambda+2)}{\Gamma(\lambda+1-\alpha)^{\tilde{p}}\,\Gamma(q+\lambda+2-\tilde{p}(q+\alpha))}.$
(3.3)

###### Proof.

We will use the well known capacity method, see for example Kassim et al.
(2017). Let us assume that the solution $u(t)$ of the inequality (3.1) is
defined in $[0,s]$, for some

$s>\tau(u_{0},q,p).$ (3.4)

For $\lambda>\alpha\tilde{p}-1$ let us introduce the test function

$\varphi_{s}(t):=\frac{(s-t)^{\lambda}}{s^{\lambda}},\ \ t\in(0,s).$ (3.5)

Multiplying the inequality (3.1) by $\varphi_{s}$ and integrating from $0$ to
$s$ gives

$\int_{0}^{s}\varphi_{s}(t)Kt^{q}u^{p}(t)dt\leq\int_{0}^{s}\varphi_{s}(t)\,^{C}D_{0+}^{\alpha}u(t)dt.$
(3.6)

Using the integration by parts formula for the Caputo fractional derivative
(see Agrawal (2007) or Kassim et al. (2017)) we have

$\int_{0}^{s}\varphi_{s}(t)\,^{C}D_{0+}^{\alpha}u(t)dt=\int_{0}^{s}u(t)\,^{RL}D_{s-}^{\alpha}\varphi_{s}(t)dt-\frac{\Gamma(\lambda+1)}{\Gamma(\lambda-\alpha+2)}s^{1-\alpha}u(0).$
(3.7)

Using the formula

$\,{}^{RL}D^{\alpha}_{s-}\varphi_{s}(t)$ $\displaystyle=$
$\displaystyle\frac{\Gamma(\lambda+1)}{\Gamma(\lambda+1-\alpha)}\cdot\frac{\varphi_{s}(t)}{(s-t)^{\alpha}},\
\ 0\leq t<s,$ (3.8)

and $u(0)\geq 0$, we obtain

$\displaystyle\int_{0}^{s}\varphi_{s}(t)Kt^{q}u^{p}(t)dt$ $\displaystyle\leq$
$\displaystyle\frac{\Gamma(\lambda+1)K}{\Gamma(\lambda+1-\alpha)}\int_{0}^{s}u(t)\frac{\varphi_{s}(t)}{(s-t)^{\alpha}}dt$
$\displaystyle=$
$\displaystyle\frac{\Gamma(\lambda+1)K}{\Gamma(\lambda+1-\alpha)}\int_{0}^{s}\varphi_{s}(t)^{\frac{1}{p}}t^{\frac{q}{p}}u(t)\cdot\frac{\varphi_{s}(t)^{1-\frac{1}{p}}t^{-\frac{q}{p}}}{(s-t)^{\alpha}}dt.$

Employing the epsilon Young inequality, with
$\varepsilon\in(0,\Gamma(\lambda+1-\alpha)/\Gamma(\lambda+1)]$, see Appendix B
in Evans (2010), we get

$\displaystyle\int_{0}^{s}\varphi_{s}(t)Kt^{q}u^{p}(t)dt$ $\displaystyle\leq$
$\displaystyle\frac{\Gamma(\lambda+1)K}{\Gamma(\lambda+1-\alpha)}\left\\{\varepsilon\int_{0}^{s}\varphi_{s}(t)t^{q}u(t)^{p}dt+C(\varepsilon)\int_{0}^{s}\frac{\varphi_{s}(t)^{\tilde{p}\left(1-\frac{1}{p}\right)}t^{-\frac{q\tilde{p}}{p}}}{(s-t)^{\alpha\tilde{p}}}dt\right\\},$

where

$C(\varepsilon)=\frac{1}{(\varepsilon p)^{\tilde{p}/p}\,\tilde{p}}.$ (3.9)

An elementary algebraic manipulation leads us to the inequality

$\displaystyle\int_{0}^{s}\varphi_{s}(t)Kt^{q}u^{p}(t)dt\left(1-\frac{\varepsilon\Gamma(\lambda+1)}{\Gamma(\lambda+1-\alpha)}\right)$
$\displaystyle\leq$
$\displaystyle\frac{C(\varepsilon)\Gamma(\lambda+1)K}{\Gamma(\lambda+1-\alpha)}\int_{0}^{s}\frac{\varphi_{s}(t)t^{q(1-\tilde{p})}}{(s-t)^{\alpha\tilde{p}}}dt$
(3.10) $\displaystyle=$
$\displaystyle\frac{C(\varepsilon)\Gamma(\lambda+1)K}{\Gamma(\lambda+1-\alpha)}\cdot
B(\lambda+1-\alpha\tilde{p},q(1-\tilde{p})+1)$ $\displaystyle\cdot\
s^{1-\alpha\tilde{p}+q(1-\tilde{p})}.$

Otherwise, applying the operator $I^{\alpha}_{0+}$ to the inequality (3.1) we
get, by (2.4),

$u(t)\geq u(0)+I^{\alpha}_{0+}(Kt^{q}u(t)^{p})\geq u_{0},\ \ 0<t<s,$ (3.11)

then

$\displaystyle\int_{0}^{s}\varphi_{s}(t)Kt^{q}u^{p}(t)dt$ $\displaystyle\geq$
$\displaystyle(u_{0})^{p}K\int_{0}^{s}\varphi_{s}(t)t^{q}dt$ $\displaystyle=$
$\displaystyle(u_{0})^{p}KB(q+1,\lambda+1)\,s^{1+q}.$

This inequality and (3.10) imply

$\displaystyle s^{\tilde{p}(\alpha+q)}$ $\displaystyle\leq$
$\displaystyle\frac{C(\varepsilon)\Gamma(\lambda+1)}{\Gamma(\lambda+1-\alpha)-\varepsilon\Gamma(\lambda+1)}\cdot\frac{B(\lambda+1-\alpha\tilde{p},q(1-\tilde{p})+1)}{u(0)^{p}B(q+1,\lambda+1)}$
(3.12) $\displaystyle=$
$\displaystyle\frac{\Gamma(q(1-\tilde{p})+1)}{u(0)^{p}\Gamma(q+1)}\cdot\frac{\Gamma(\lambda+1-\alpha\tilde{p})\Gamma(q+\lambda+2)}{\Gamma(q+\lambda+2-\tilde{p}(q+\alpha))}\cdot
H(\varepsilon),$

where

$H(\varepsilon):=\frac{C(\varepsilon)}{\Gamma(\lambda+1-\alpha)-\varepsilon\Gamma(\lambda+1)}.$

Since the right hand side of inequality (3.12) is valid for any
$0<\varepsilon<\Gamma(\lambda+1-\alpha)/\Gamma(\lambda+1)$, then we use the
identity (3.9) to minimize the function $H(\varepsilon)$ to get

$\displaystyle s$ $\displaystyle\leq$
$\displaystyle\left(\frac{\Gamma(q(1-\tilde{p})+1)}{(u_{0})^{p}\Gamma(q+1)}\cdot
B(\lambda)\right)^{1/(\tilde{p}(\alpha+q))},\ \ \lambda>\alpha\tilde{p}-1,$
(3.13)

where $B(\lambda)$ is defined in (3.3). Taking the infimum over $\lambda$ in
the above inequality we deduce that $s\leq\tau(u_{0},q,p)$, contradicting the
inequality (3.4). In this way, the desired result is achieved. ∎

We are now in a position to state and prove our main result.

######  Theorem 3.2.

Let $\alpha\in(0,1)$ and $q_{1}$, $q_{2}$, $p_{11}$, $p_{12}$, $p_{21}$,
$p_{22}$ be non-negative real numbers. We will consider the system of Caputo’s
fractional differential equations,

${}^{C}D_{0+}^{\alpha}x(t)$ $\displaystyle=$ $\displaystyle
t^{q_{1}}x^{p_{11}}(t)y^{p_{12}}(t),\ \ t>0,$ (3.14)
${}^{C}D_{0+}^{\alpha}y(t)$ $\displaystyle=$ $\displaystyle
t^{q_{2}}y^{p_{21}}(t)x^{p_{22}}(t),\ \ t>0,$ (3.15)

with initial conditions

$x(0)=x_{0}>0,\ \ y(0)=y_{0}>0.$

Case $q_{1}\neq q_{2}$:

Let us set $q_{i}:=\min\\{q_{1},q_{2}\\}$, $j:=3-i$ and

$p_{j}:=p_{ji}+p_{jj}\gamma_{j},$

where

$\gamma_{j}:=\frac{p_{ij}+1-p_{ji}}{2}.$

If

$p_{ij}\geq 3+p_{ji},\ \ p_{ii}+1\geq p_{jj},\ \ q_{j}+1>q_{j}\tilde{p}_{j},$
(3.16)

then the solution of system (3.14)-(3.15) blows-up in finite time. Moreover,
the blow-up time, $\tau_{xy}$, is less than or equal to
$\tau(u_{j},q_{j},p_{j})$, where $\tau(u_{0},p,q)$ is defined in (3.2) and

$\displaystyle u_{j}$ $\displaystyle=$
$\displaystyle\begin{cases}x_{0},&j=1,\\\ y_{0},&j=2.\end{cases}$

Case $q_{1}=q_{2}$:

In this case, if

$p_{22}\geq 3+p_{11},\ \ p_{21}+1\geq p_{12},\ \ q_{1}+1>q_{1}\tilde{p}_{1},$
(3.17)

then the solution of system (3.14)-(3.15) blows-up in finite time and the
blow-up time $\tau_{xy}$ is less than or equal to $\tau(x_{0},q_{1},p_{1})$,
where

$p_{1}:=p_{11}+p_{12}\gamma_{1},\ \ \gamma_{1}:=\frac{p_{22}+1-p_{11}}{2}.$

Or, if

$p_{12}\geq 3+p_{21},\ \ p_{11}+1\geq p_{22},\ \ q_{2}+1>q_{2}\tilde{p}_{2},$
(3.18)

then the solution of system (3.14)-(3.15) blows-up in finite time and the
blow-up time $\tau_{xy}$ is less than or equal to $\tau(y_{0},q_{2},p_{2})$,
where

$p_{2}:=p_{21}+p_{22}\gamma_{2},\ \ \gamma_{2}:=\frac{p_{12}+1-p_{21}}{2}.$

###### Proof.

The local existence of a positive solution $(x(t),y(t))$ of system
(3.14)-(3.15) is obtained by proceeding as in the classical case (i.e., the
non-fractional one). Indeed, instead of treating the system of fractional
differential equations, the associated system of integral equations is studied
(see formula (3.5.4) in (Kilbas et al., 2006)). A first step consists of
applying a version of Banach’s contraction principle to a mapping, determined
by the system of integral equations, in order to find a positive solution
$(x(t),y(t))$ in a certain interval $[0,\delta)$, that is, we obtain a local
solution (see Theorem 3.25 in (Kilbas et al., 2006), for example). For the
second step, let $[0,t_{\max})$ be the maximum interval of existence of the
solution $(x(t),y(t))$. If $t_{\max}<\infty$, then $\lim_{t\uparrow
t_{\max}}\,\sup\\{x(s)+y(s):s\in[0,t]\\}=\infty$. If such a limit were finite,
then we can proceed as in the first step and deduce that we can extend the
solution to the time interval $[0,t_{\max}+\delta)$, which is absurd (see, for
example, the proof of Theorem $1.4$ in Chapter $6$ of Pazy (1983)). Therefore,
the maximum time of existence of the solution is precisely the blow-up
(explosion) time.

Now, we will concentrate on finding upper bounds for the blow-up time
$\tau_{xy}$ of the system (3.14)-(3.15). Without loss of generality, we will
suppose that we have $q_{2}\geq q_{1}$, $p_{12}\geq 3+p_{21}$, $p_{11}+1\geq
p_{22}$ and $q_{2}+1>q_{2}\tilde{p}_{2}$; in the other cases the procedure is
similar, therefore we omit them. We will see that the blow-up time $\tau_{xy}$
of the system is less than or equal to $\tau(y_{0},q_{2},p_{2})$. We proceed
by contradiction, that is, $\tau(y_{0},q_{2},p_{2})<\tau_{xy}$, then the
system (3.14)-(3.15) has a solution $(x(s),y(s))$ in $[0,t]$, for some

$\tau(y_{0},q_{2},p_{2})<t<\tau_{xy}.\ \ $ (3.19)

Under this assumption it makes sense to introduce the following function

$J(s)=Mx(s)-y^{\gamma_{2}}(s),\ \ 0\leq s\leq t,$

where $M$ is a positive constant that will be fixed letter. Observe that the
hypotheses imply $\gamma_{2}\geq 2$ and this is a condition necessary to apply
Proposition 2.3. Using the linearity of the Caputo’s fractional derivative,
(2.9), (3.14) and (3.15) we obtain

${}^{C}D_{0+}^{\alpha}J(s)$ $\displaystyle=$ $\displaystyle
M\,^{C}D_{0+}^{\alpha}x(s)-\,^{C}D_{0+}^{\alpha}y^{\gamma_{2}}(s)$
$\displaystyle\geq$ $\displaystyle
M\,^{C}D_{0+}^{\alpha}x(s)-\gamma_{2}\,y^{\gamma_{2}-1}(s)\,^{C}D_{0+}^{\alpha}y(s)$
$\displaystyle=$ $\displaystyle
Ms^{q_{1}}x^{p_{11}}(s)y^{p_{12}}(s)-\gamma_{2}\,s^{q_{2}}x^{p_{22}}(s)y^{\gamma_{2}-1+p_{21}}(s).$

Setting

$h(s):=s^{q_{2}}x^{p_{11}}(s)y^{\gamma_{2}-1+p_{21}}(s),\ \ 0\leq s\leq t,$

the above inequality implies

${}^{C}D_{0+}^{\alpha}J(s)+h(s)J(s)$ $\displaystyle\geq$ $\displaystyle
x^{p_{11}}(s)y^{p_{12}}(s)(Ms^{q_{1}}-s^{q_{2}})$ $\displaystyle+\
s^{q_{2}}y^{\gamma_{2}-1+p_{21}}(s)(Mx^{p_{11}+1}(s)-\gamma_{2}\,x^{p_{22}}(s)).$

Proceeding as in the proof of (3.11) we can verify that

$x(s)\geq x_{0}>0,\ \ 0\leq s\leq t.$

If we take

$\displaystyle M$ $\displaystyle>$
$\displaystyle\max\left\\{s^{q_{2}-q_{1}},\gamma_{2}\,x^{p_{22}-p_{11}-1}(s):0\leq
s\leq t\right\\}$ $\displaystyle=$
$\displaystyle\max\left\\{t^{q_{2}-q_{1}},\gamma_{2}\,(x_{0})^{p_{22}-p_{11}-1}\right\\},$

then

${}^{C}D_{0+}^{\alpha}J(s)+h(s)J(s)>0,\ \ 0\leq s\leq t.$

Furthermore, if we take $M>(y_{0})^{\gamma_{2}}(x_{0})^{-1}$, then $J(0)>0$.

Let us set

$A:=\\{r\in[0,t]:J(s)>0,\ \text{for all}\ s\in[0,r]\\}.$

Notice that $0\in A$. Let us suppose that $a:=\sup A<t$. This implies

${}^{C}D_{0+}^{\alpha}J(s)+||h||J(s)>0,\ \ 0\leq s<a,$ (3.20)

where $||h||:=\sup\\{|h(s)|:0\leq s\leq t\\}$. We will consider the function
$e_{\alpha}^{-||h||(a-s)}>0$ defined in (2.6). Multiplying by
$e_{\alpha}^{-||h||(a-s)}$ on both sides of the inequality (3.20) and
integrating with respect to $s$ we obtain

$\displaystyle 0$ $\displaystyle<$
$\displaystyle\int_{0}^{a}e_{\alpha}^{-||h||(a-s)}\,\left[{}^{C}D_{0+}^{\alpha}J(s)+||h||J(s)\right]ds$
$\displaystyle=$
$\displaystyle\int_{0}^{a}e_{\alpha}^{-||h||(a-s)}\,{}^{C}D_{0+}^{\alpha}J(s)ds+\int_{0}^{a}e_{\alpha}^{-||h||(a-s)}||h||J(s)ds$
$\displaystyle\leq$
$\displaystyle\int_{0}^{a}J(s)\,^{RL}D_{a-}^{\alpha}e_{\alpha}^{-||h||(a-s)}\,ds+\int_{0}^{a}J(s)||h||e_{\alpha}^{-||h||(a-s)}\,ds$
$\displaystyle=$
$\displaystyle\int_{0}^{a}J(s)\,\left[{}^{RL}D_{a-}^{\alpha}e_{\alpha}^{-||h||(a-s)}+||h||\,e_{\alpha}^{-||h||(a-s)}\right]ds=0.$

This contradiction yields $a=t$, then $J(s)\geq 0$, $0\leq s\leq t$, namely

$x(s)\geq\frac{1}{M}\,y^{\gamma_{2}}(s),\ \ 0\leq s\leq t.$

From the above inequality and (3.15) we arrive at

${}^{C}D_{0+}^{\alpha}y(s)\geq\frac{1}{M^{p_{22}}}\,s^{q_{2}}y^{p_{21}+p_{22}\gamma_{2}}(s),\
\ 0\leq s\leq t.$

If we take $K=M^{-p_{22}}$, $q=q_{2}$, $p=p_{21}+p_{22}\gamma_{2}$ and
$u_{0}=y_{0}$ in Proposition 3.1 we conclude that the system (3.14)-(3.15) can
not have a solution on $[0,t]$, otherwise we have the inequality,
$t\leq\tau(u_{0},q,p)=\tau(y_{0},q_{2},p_{2})$. But this contradicts (3.19),
as expected. ∎

##  4 Numerical experiments

To find the solution of the system (3.14)-(3.15), in this section we are going
to consider a numerical scheme. We will use the predictor-corrector approach
introduced in Diethelm et al. (2002) to find numerical solutions. In fact, in
such paper it is also included a code that is very simple to implement. It is
convenient to point out that in Diethelm et al. (2002) the algorithm is
introduced to find the solution of a single fractional differential equation,
in our case, we adapt their algorithm for systems of fractional equations. In
addition, we present the algorithm for a more general system than the one
considered in Section $3$, since we believe that it may be of interest to a
broader audience.

We are going to consider a numerical scheme for the system of fractional
differential equations in Caputo’s sense,

${}^{C}D_{0+}^{\alpha}x(t)$ $\displaystyle=$ $\displaystyle f(t,x(t),y(t)),\ \
t>0,$ (4.1) ${}^{C}D_{0+}^{\alpha}y(t)$ $\displaystyle=$ $\displaystyle
g(t,x(t),y(t)),\ \ t>0,$ (4.2)

where $f(t,x,y)$ and $g(t,x,y)$ are given functions together with the initial
data

$x(0)=x_{0},\ \ y(0)=y_{0}.$ (4.3)

Let us look at a numerical solution in the time interval $[0,T]$. We denote by
$N$ the number of divisions of $[0,T]$ and let $t_{n}:=nh$, $n=0,1,...,N$, be
the corresponding regular partition, where $h:=T/N$. By $(x_{n+1},y_{n+1})$,
we set the numeric approximation of the solution $(x(t),y(t))$ of the system
(4.1)-(4.2) at time $t=t_{n+1}$. For $j=0,1,...,n+1$, we will set

$\displaystyle
x_{n+1}=x_{0}+\frac{h^{\alpha}}{\Gamma(\alpha+2)}\sum_{j=0}^{n}a_{j,n+1}f(t_{j},x_{j},y_{j})+\frac{h^{\alpha}}{\Gamma(\alpha+2)}f(t_{n+1},p_{n+1},q_{n+1}),$
$\displaystyle
y_{n+1}=y_{0}+\frac{h^{\alpha}}{\Gamma(\alpha+2)}\sum_{j=0}^{n}a_{j,n+1}g(t_{j},x_{j},y_{j})+\frac{h^{\alpha}}{\Gamma(\alpha+2)}g(t_{n+1},p_{n+1},q_{n+1}),$

where

$\displaystyle a_{j,n+1}$ $\displaystyle=$
$\displaystyle\begin{cases}n^{\alpha+1}-(n-\alpha)(n+1)^{\alpha},&j=0,\\\
(n-j+2)^{\alpha+1}+(n-j)^{\alpha+1}-2(n-j+1)^{\alpha+1},&1\leq j\leq
n,\end{cases}$

and

$\displaystyle
p_{n+1}=x_{0}+\frac{1}{\Gamma(\alpha)}\sum_{j=0}^{n}b_{j,n+1}f(t_{j},x_{j},y_{j}),$
$\displaystyle
q_{n+1}=y_{0}+\frac{1}{\Gamma(\alpha)}\sum_{j=0}^{n}b_{j,n+1}g(t_{j},x_{j},y_{j}),$

here

$b_{j,n+1}=\frac{h^{\alpha}}{\alpha}\left((n+1-j)^{\alpha}-(n-j)^{\alpha}\right).$

The blow-up time that will be obtained from the numerical scheme is denoted by
$t_{\text{num}}$. More precisely, such time is deduced from the graph of the
numerical solution of the system of interest. It should be noted that the
objective of this work is not to design a numerical scheme to determine the
blow-up time, this is a wide topic of study, see for example Pérez and Villa-
Morales (2022) and the references there in. Our objective here is to show that
the explosion time obtained in Theorem 3.2, which we will denote by
$\tau_{ub}$, is an upper bound for the numerical blow-up time,
$t_{\text{num}}$.

We are going to consider three examples, which correspond to the three
possible cases that can occur in Theorem 3.2.

[0cm]

Example 1.

Let us examine the system of fractional differential equations

${}^{C}D_{0+}^{\alpha}x(t)$ $\displaystyle=$ $\displaystyle
t^{0.5}x^{1.5}(t)y^{3.6}(t),\ \ t>0,$ (4.4) ${}^{C}D_{0+}^{\alpha}y(t)$
$\displaystyle=$ $\displaystyle t^{1.5}y^{0.5}(t)x^{2.4}(t),\ \ t>0,$ (4.5)

with initial conditions

$x(0)=1,\ \ y(0)=1.2.$

We apply the predictor-corrector algorithm to system (4.4)-(4.5) to obtain the
graph of its solution, which can be seen in Figure 1. From the graphical
representation we obtain an estimate of the numerical explosion time
$t_{\text{num}}$, for the fractional index $\alpha=0.1,0.4,0.6,0.9$.

(a) $\alpha=0.1$, $t_{\text{num}}=0.85$.

(b) $\alpha=0.4$, $t_{\text{num}}=0.28$.

(c) $\alpha=0.6$, $t_{\text{num}}=0.44$.

(d) $\alpha=0.9$, $t_{\text{num}}=0.67$.

Figure 1: Graphs of the solutions of system (4.4)-(4.5).

On the other hand, the parameters

$q_{1}=0.5,\ \ p_{11}=1.5,\ \ p_{12}=3.6,\ \ q_{2}=1.5,\ \ p_{21}=0.5,\ \
p_{22}=2.4,$

satisfy the conditions of (3.16), so we can apply Theorem 3.2. In order to do
this, we need to know the minimum value of the function $B$, defined in (3.3).
Because such a function is quite complicated, it is not obvious that a minimum
value exists. Fortunately, when graphing the function $B$, see Figure 2, we
note that this function is convex, for each value of $\alpha$, therefore the
existence of the value sought follows. The function $B$ has a similar
behaviour in the following two examples, so we will omit its graph. With the
minimum value of $B$, we get the upper bound $t_{ub}$ of the blow-up time
$\tau_{xy}$.

(a) $\alpha=0.1$, $\lambda_{m}=-0.802...$

(b) $\alpha=0.4$, $\lambda_{m}=-0.358...$

(c) $\alpha=0.6$, $\lambda_{m}=-0.083...$

(d) $\alpha=0.9$, $\lambda_{m}=0.315...$

Figure 2: Graphs of $B$ given in Example $1$.

We concentrate this information in the following table:

$\alpha$ | $0.1$ | $0.4$ | $0.6$ | $0.9$
---|---|---|---|---
$\lambda_{m}$ | $-0.802...$ | $-0.358...$ | $-0.083...$ | $0.315...$
$t_{\text{num}}$ | $0.085$ | $0.28$ | $0.44$ | $0.66$
$\tau_{ub}$ | $0.720...$ | $0.998...$ | $1.169...$ | $1.415...$

From this, we clearly appreciate that upper bounds have been obtained for the
blow-up (explosion) time. In graph (d) of Figure 1 it can be seen that the
function $y(t)$ begins to grow; in fact, if it is graphed separately, it can
be seen that it also explodes in finite time. Its blow-up time is
approximately $0.69$.

Example 2.

Now let us consider the system of fractional differential equations

${}^{C}D_{0+}^{\alpha}x(t)$ $\displaystyle=$ $\displaystyle y^{3.2}(t),\ \
t>0,$ (4.6) ${}^{C}D_{0+}^{\alpha}y(t)$ $\displaystyle=$ $\displaystyle
y^{0.2}(t)x^{0.5}(t),\ \ t>0,$ (4.7)

with initial conditions

$x(0)=0.5,\ \ y(0)=0.5.$

Applying the predictor-corrector algorithm, the graphs of the solutions of
system (4.6)-(4.7), for the parameter $\alpha=0.1,0.4,0.6,0.9$, are obtained,
and they appear in Figure 3. From here we estimate the numerical value of the
explosion time, $t_{\text{num}}$.

(a) $\alpha=0.1$, $t_{\text{num}}=0.35$.

(b) $\alpha=0.4$, $t_{\text{num}}=3.8$.

(c) $\alpha=0.6$, $t_{\text{num}}=5.1$.

(d) $\alpha=0.9$, $t_{\text{num}}=6.9$.

Figure 3: Graphs of the solutions of system (4.6)-(4.7).

We observe that the parameters

$q_{1}=0,\ \ p_{11}=0,\ \ p_{12}=3.2,\ \ q_{2}=0,p_{21}=0.2,\ \ p_{22}=0.5,$

of the system of equations (4.6)-(4.7) meet, in this case, conditions (3.17),
therefore we can apply Theorem 3.2 to obtain an estimate $\tau_{ub}$ from
above the blow-up time $\tau_{xy}$ of this system. We summarize the results in
the following table:

$\alpha$ | $0.1$ | $0.4$ | $0.6$ | $0.9$
---|---|---|---|---
$t_{\text{num}}$ | $0.35$ | $3.8$ | $5.1$ | $6.9$
$\tau_{ub}$ | $8.899...$ | $6.333...$ | $7.297...$ | $8.948...$

As a result, we can conclude that $\tau_{ub}$ is an upper bound for the
numerical blow-up time, $t_{\text{num}}$. As in the previous case, if we graph
the function $y(t)$ separately we can determine its explosion time, which in
this case is approximately $8.7$. Remember that the explosion time of a system
is the minimum of the explosion times of each component.

Example 3.

Here we deal with the system of fractional differential equations

${}^{C}D_{0+}^{\alpha}x(t)$ $\displaystyle=$ $\displaystyle
t^{0.5}x(t)y^{3}(t),\ \ t>0,$ (4.8) ${}^{C}D_{0+}^{\alpha}y(t)$
$\displaystyle=$ $\displaystyle t^{0.5}y^{2}(t)x^{4}(t),\ \ t>0,$ (4.9)

with initial conditions

$x(0)=1,\ \ y(0)=1.$

As in the previous cases, we apply the predictor-corrector algorithm to obtain
the graphical solutions of system (4.8)-(4.9); we present them in Figure 4.
Numerical estimates for time $t_{\text{num}}$ are obtained from them.

(a) $\alpha=0.1$, $t_{\text{num}}=0.019$.

(b) $\alpha=0.4$, $t_{\text{num}}=0.11$.

(c) $\alpha=0.6$, $t_{\text{num}}=0.21$.

(d) $\alpha=0.9$, $t_{\text{num}}=0.42$.

Figure 4: Graphs of the solutions of system (4.8)-(4.9).

The parameters of the system (4.8)-(4.9) are

$q_{1}=0.5,\ \ p_{11}=01,\ \ p_{12}=3,\ \ q_{2}=0.5,p_{21}=2,\ \ p_{22}=4,$

and they meet the conditions imposed in (3.18), therefore we can apply Theorem
3.2 to obtain $\tau_{ub}$, which provides us with an upper bound for the
numerical time explosion, $t_{\text{num}}$. We put this information together
in the following table:

$\alpha$ | $0.1$ | $0.4$ | $0.6$ | $0.9$
---|---|---|---|---
$t_{\text{num}}$ | $0.019$ | $0.11$ | $0.21$ | $0.42$
$\tau_{ub}$ | $1.228...$ | $1.551...$ | $1.726...$ | $1.967...$

Here we again see that $\tau_{ub}$ is an upper bound for $t_{\text{num}}$. In
this case, both components have approximately the same explosion time.

##  5 Conclusions

In the present work, upper bounds have been obtained for the blow-up time of a
system of fractional differential equations in the Caputo sense (1.1)-(1.2).
As a consequence of this, sufficient conditions have been derived so the
system of fractional differential equations does not have a global solution.
Furthermore, based on the predictor-corrector algorithm, a numerical scheme
has been proposed to solve systems of fractional differential equations in
general. Using this numerical method, three illustrative examples have been
presented that correspond to each of the cases of the Theorem 3.2.

Acknowledgment: The author was partially supported by the grant PIM22-1 of
Universidad Autónoma de Aguascalientes. Thanks to José Miguel Villa-Ocampo for
his help in the implementation of the numerical algorithm in R.

## References

  * Agrawal (2007) Agrawal, O. P., 2007. Fractional variational calculus in terms of Riesz fractional derivatives. J. Phys. A 40 (24), 6287–6303.
  * Aguila-Camacho et al. (2014) Aguila-Camacho, N., Duarte-Mermoud, M. A., Gallegos, J. A., 2014. Lyapunov functions for fractional order systems. Commun Nonliner Sci Numer Simulat 19, 2951–2957.
  * Aldawish and Samet (2022) Aldawish, I., Samet, B., 2022. Necessary conditions for the existence of global solutions to nonlinear fractional differential inequalities and systems. J. Function Spaces 2022, 1–9.
  * Alikhanov (2010) Alikhanov, A. A., 2010. A priori estimates for solutions of boundary value problems for fractional-order equations. Differential Equations 46, 660–666.
  * Bai and Qiu (2009) Bai, Z., Qiu, T., 2009. Existence of positive solution for singular fractional differential equation. Applied Mathematics and Computation 215 (7), 2761–2767.
  * Bebernes and Eberly (1989) Bebernes, J., Eberly, D., 1989. Mathematical problems from combustion theory. Vol. 83. Springer-Verlag, New York.
  * Cabral-García and Villa-Morales (2019) Cabral-García, G. J., Villa-Morales, J., 2019. Blowup at space infinity for solutions of a system of nonautonomous semilinear heat equations. Mathematical Methods in the Applied Sciences 43 (2), 903–919.
  * Diethelm et al. (2002) Diethelm, K., Ford, N. J., Freed, A. D., 2002. A predictor-corrector approach for the numerical solution of fractional differential equations. Nonlinear Dynamics 29, 3–22.
  * Evans (2010) Evans, L. C., 2010. Partial differential equations. American Mathematical Society, Providence, Rhode Island.
  * Furati and Tatar (2004) Furati, K. M., Tatar, N.-E., 2004. An existence result for a nonlocal fractional differential problem. J. Fract. Calc. 26, 43–51.
  * Jleli et al. (2019) Jleli, M., Kirane, M., Samet, B., 2019. Absence of global solutions for a fractional in time and space shallow-water system. Mathematics 7, 1–11.
  * Kassim et al. (2017) Kassim, M. D., Furati, K. M., Tatar, N.-E., 2017. Nonexistence of global solutions for a fractional differential problem. J. Comput. Appl. Math. 314, 61–68.
  * Kerbal (2010) Kerbal, S., 2010. Non-existence of global solutions to systems of non-autonomous nonlinear parabolic equations. Communications in Applied Analysis 14 (2), 203–212.
  * Kilbas et al. (2006) Kilbas, A. A., Srivastava, H. M., Trujillo, J. J., 2006. Theory and applications fractional differential equations. Vol. 204. Elsevier, London.
  * Kirane et al. (2014) Kirane, M., Ahmad, B., Alsaedi, A., Al-Yami, M., 2014. Non-existence of global solutions to a system of fractional diffusion equations. Acta Applicandae Mathematicae 133, 235–248.
  * Kirane et al. (2005) Kirane, M., Laskri, Y., Tatar, N.-E., 2005. Critical exponents of fujita type for certain evolution equations and systems with spatio-temporal fractional derivatives. J. Math. Anal. Appl. 312 (2), 488–501.
  * Laskri and Tatar (2010) Laskri, Y., Tatar, N.-E., 2010. The critical exponent for an ordinary fractional differential problem. Comput. Math. Appl. 59, 1266–1270.
  * Messaoudi et al. (2007) Messaoudi, S. A., Said-Houari, B., Tatar, N.-E., 2007. Global existence and asymptotic behaviour for a fractional differential equation. Appl. Math. Comput. 188, 1955–1962.
  * Pazy (1983) Pazy, A., 1983. Semigoups of linear operators and applications to partial differential equations. Springer, New York.
  * Pérez and Villa-Morales (2022) Pérez, A., Villa-Morales, J., 2022. A numerical scheme for the blow-up time of solutions of a system of nonlinear ordinary differential equations. Applied Numerical Mathematics 171, 442–452.
  * Pollard (1948) Pollard, H., 1948. The completely monotonic character of the mittag-leffler function $e_{\alpha}(-x)$. Bull. Amer. Math. Soc. 54, 1115–1116.
  * Sun et al. (2012) Sun, S., Zhao, Y., Zhenlai, Li, Y., 2012. The existence of solutions for boundary value problem of fractional hybrid differential equations. Communications in Nonlinear Science and Numerical Simulation 17 (12), 4961–4967.
  * Villa-Morales et al. (2022) Villa-Morales, J., Rodríguez-Esparza, L. J., Ramírez-Aranda, M., 2022. Deflection of beams modeled by fractional differential equations. Fractal Fract. 6 (11), 1–18.
  * Zhan et al. (2014) Zhan, R.-T., Li, Z.-X., Wang, L., 2014. A fractional differential constitutive model for dynamic stress intensity factors of an anti-plane crack in viscoelastic materials. Acta Mechanica Sinica 30, 403–409.
  * Zhou and Chua (2012) Zhou, W.-X., Chua, Y.-D., 2012. Existence of solutions for fractional differential equations with multi-point boundary conditions. Communications in Nonlinear Science and Numerical Simulation 17 (3), 1142–1148.