Universidad Pública de Navarra,
Dpto. EIM, INARBE Institute
Campus Arrosadía. Pamplona, 31006, Spain.
<EMAIL_ADDRESS>
# A new approach on distributed systems: orderings and representability

Asier Estevan Muguerza

###### Abstract

In the present paper we propose a new approach on ‘distributed systems’: the
processes are represented through total orders and the communications are
characterized by means of biorders. The resulting distributed systems capture
situations met in various fields (such as computer science, economics and
decision theory). We investigate questions associated to the numerical
representability of order structures, relating concepts of economics and
computing to each other. The concept of ‘quasi-finite partial orders’ is
introduced as a finite family of chains with a communication between them. The
representability of this kind of structure is studied, achieving a
construction method for a finite (continuous) Richter-Peleg multi-utility
representation.

Keywords:

Distributed systems, partial orders, biorders, representability.

##  1 Introduction and motivation

In the present paper we focus on an ordered structure known as _distributed
system_. Although this concept belongs primarily to the field of computer
science, its mathematical structure is common to many areas.

The representability issue appears too in a wide range of fields, such as
economics and decision making [2, 3, 9, 12, 20, 30, 36, 34], computing [21,
26, 27, 31, 37, 40], mathematical psychology [13, 15, 33, 14], etc. This
interest on the representability of relations is usually due to maximization
problems (in economics and decision making), the need to control non-linear
processes that are being executed (computer science), the convenience of
transform qualitative scales into quantitative ones (mathematical psychology),
etc.

Hence, one of the goals of the present work is to bring to the computer field
knowledge from other areas (order theory and decision theory in mathematics or
economics, for instance) that may be helpful when dealing with distributed
systems. For this purpose, first we redefine the concepts of a distributed
system. For that, we shall use the concept of biorder. This study was started
in [16] for the particular case of distributed systems of two processes.
However, in order to formalize completely the concept of distributed system, a
further study is needed, linking biorders between $n$ totally ordered sets.

The idea of a biorder was studied by Guttman (see _Guttman Scales_ in [24])
and by Riguet under the name of _Ferrers relation_ [39]. However, the concept
was introduced for first time by André Ducamp and Jean-Claude Falmagne in 1969
in [15], and studied in depth in 1984 by Jean-Paul Doignon, André Ducamp and
Jean-Claude Falmagne in [13]. It is defined as follows:

_A biorder $\mathrel{\mathcal{R}}$ from $A$ to $X$ is a binary relation, with
$\mathrel{\mathcal{R}}\subseteq A\times X$, satisfying that for every $a,b\in
A$ and $x,y\in X$ $(a\mathrel{\mathcal{R}}x)\wedge(b\mathrel{\mathcal{R}}y)$
implies $(a\mathrel{\mathcal{R}}y)\vee(b\mathrel{\mathcal{R}}x)$._

The concept of biorder can also be found just as a Ferrers relation [3, 13],
that is, as a relation $\mathrel{\mathcal{R}}$ on a single set $X$ such that
for any $x,y,z,t\in X$ it holds that $x\mathrel{\mathcal{R}}y$ with
$z\mathrel{\mathcal{R}}t$ implies that $x\mathrel{\mathcal{R}}t$ or
$z\mathrel{\mathcal{R}}y$. Other kind of relations such as interval orders [3,
4, 5, 9, 22, 23, 41, 45] (in particular, the more restrictive case of a
semiorder [11, 17, 18, 30]), may be considered particular cases of biorders
[3, 13].

In the present paper we focus on biorders defined between disjoint totally
ordered sets (see Figure1), and we use them in order to redefine the concept
of distributed system [21, 27, 31, 37].

$b\,\bullet$$a\,\bullet$$c\,\bullet$$d\,\bullet$$\bullet\,y$$\bullet\,x$$\bullet\,z$$(A,\precsim_{A})$$(X,\precsim_{X})$

Figure 1:  A biordered pair of totally preodered sets.

In a distributed system, distinct computers are connected to each other in
order to achieve a common goal, this is known as _distributed computing_.

These computers communicate with each other through messages that are sent and
received. Each computer has its own internal (physical) clock, so that it is
possible to assing a number (a time) to each event of the proceess. Thus, from
a mathematical point of view, each computer (or _process_) is a totally
ordered set (i.e., a chain) which can be represented through its local time.
Hence, without a precise clock synchronization it is not possible to capture
the causality relation between events of distinct processes. Moreover, if an
event $b$ holds _later_ (with respect to the time) than $a$, it does not imply
that $a$ causally affects $b$. On the contrary, if $a$ causally affects $b$,
then $b$ must hold _later_ (with respect to an idyllic global time) than $a$.
Finally, in these structures, the property called _causal ordering of
messages_ is usually111Here we say _usually_ since it is a common property
which is not implicit in Definition 1. satisfied: if a computer $i$ sends two
messages $m_{1}$ and then $m_{2}$ (so, such that $m_{1}$ has been sent before
$m_{2}$) to the same computer $j$ ($i\neq j$), then message $m_{1}$ must be
received before message $m_{2}$ (see Figure 2). [27, 26]

$a_{2}$$a_{1}$$b_{2}$$b_{1}$$\bullet$$\bullet$$\bullet$$\bullet$

Figure 2: The vertical arrows represent the sequence of events of each
process, that is, the direction of the time. The dashed arrows represent the
sending of messages, from the sender to the receiver. Here, the causal
ordering of messages is not satisfied.

The concept of a _distributed system_ is usually defined as Lamport did [27]:

######  Definition 1.

An _event_ (illustrated by a point in Figure 1 and Figure 3) is a uniquely
identified runtime instance of an atomic action of interest. It is an
occurrence at a point in time, i.e., a happening at a cut of the timeline,
which itself does not take any time. A _process_ (illustrated by a vertical
line in Figure 1 and Figure 3) is a sequence of totally ordered events, thus,
for any event $a$ and $b$ in a process, either $a$ comes before $b$ or $b$
comes before $a$. A _distributed system_ consists of a collection of distinct
processes which are spatially separated, and which communicate with one
another by exchanging messages (illustrated by red arrows in Figure 1 and wavy
arrows in Figure 3). It is assumed that sending or receiving a message is an
event.

Since each process consists of a sequence of events, each process is a totally
ordered set, and the communication through messages between the processes will
be defined by means of biorders.

Figure 3: Illustration of a distributed system, taken from the paper [27] of
Leslie Lamport.

Moreover, this communication between processes defines a causal relation known
as ‘causal precedence’ or ‘happened before’ relation [21, 27, 31, 37] (common
in causality too [35], but now related to the theory of relativity, see also
[10, 25]). This causal relation was defined by Leslie Lamport in [27] as
follows (see also [26]):

######  Definition 2.

The _causal precedence_ (denoted by $\rightarrow$) on the set of events of a
distributed system is the smallest relation satisfying the following three
conditions:

  1. 1.

If $a$ and $b$ are events in the same process, and $a$ comes before $b$, then
$a\rightarrow b$.

  2. 2.

If $a$ is the sending of a message by one process and $b$ is the receipt of
the same message by another process, then $a\rightarrow b$.

  3. 3.

If $a\rightarrow b$ and $b\rightarrow c$ then $a\rightarrow c$.

If $a\rightarrow b$, then it is said that $a$ _causally precedes_ $b$.

This definition was introduced by Leslie Lamport in 1978 (see [27]) and it has
been used until nowadays. In the present paper we shall introduce a new
definition of the concept through orderings. Graphically, $a\rightarrow b$
implies that there is a path of causality from event $a$ to event $b$ (moving
in the direction of the arrows, see Figure 1 or Figure 3), that is., $b$ is
reachable from $a$.

Two distinct events $a$ and $b$ are _concurrent_ if $a\nrightarrow b$ and
$b\nrightarrow a$, that is, if they in no way can causally affect each other,
so in that case it is not known which event happened first. It is assumed that
$\rightarrow$ is irreflexive ($a\nrightarrow a$ for any event $a$), so, in
case there are no cycles, $\rightarrow$ is a strict partial ordering on the
set of all events in the system.

Finally, we shall focus too on finite Richter-Peleg multi-utility
representations. The construction of these (continuous) representations for a
given preorder may be a hard problem. For this purpose, the study of the
(continuous, in case the sets are endowed with topologies) representability of
biorders defined between totally preordered sets seems a right approach in
order to achieve a (continuous and finite) Richter-Peleg multi-utility
representation of the corresponding causal precedence or happened before
relation. This idea consists in using (continuous) representations of
distributed systems in order to represent (continuously) the corresponding
causal precedence relation.

The structure of the paper goes as follows:

After this introduction, a section of preliminaries is included. Next, in
Section 3 a new definition (and its motivation) of a distributed system is
introduced, so that then the representability problem is studied in Section 4,
achieving an aggregation result for the case of line communications. In this
section it is shown how to construct weak representations of distributed
systems with line communications starting from pairs of functions that
represent each biorder. Finally, in Section 5 we focus on quasi-finite partial
orders as an interesting family of partial orders. For this kind of orderings
we also include a technique in order to construct a finite (and continuous)
Richter-Peleg multi-utility.

##  2 Notation and preliminaries

From now on $A,B$ and $X$ as well as $X_{1},...,X_{n}$ will denote nonempty
(maybe infinite) sets. When we speak of continuity of a real-valued mapping
defined on a set $S$, we assume that some topology $\tau_{S}$ is given on $S$.

######  Definition 3.

A _binary relation_ $\mathrel{\mathcal{R}}$ from $A$ to $X$ is a subset of the
Cartesian product $A\times X$. In particular, in the case that $A=X$, the
binary relation $\mathrel{\mathcal{R}}$ is said to be defined on $X$, and it
is a subset of the Cartesian product $X\times X$. Given two elements $a\in A$
and $x\in X$, we will use notation $a\mathrel{\mathcal{R}}x$ to express that
the pair $(a,y)$ belongs to $\mathcal{R}$. Associated to a binary relation
$\mathrel{\mathcal{R}}$ from $A$ to $X$, its _negation_ is the binary relation
$\mathrel{\mathcal{R}}^{c}$ from $A$ to $X$ given by
$(a,x)\in\mathrel{\mathcal{R}}^{c}\iff(a,x)\notin\mathrel{\mathcal{R}}$ for
every $a\in A$ and $x\in X$.

Given two binary relations $\mathrel{\mathcal{R}}$ and
$\mathrel{\mathcal{R}^{\prime}}$ on a set $X$, it is said that
$\mathrel{\mathcal{R}^{\prime}}$ _extends_ or _refines_
$\mathrel{\mathcal{R}}$ if $x\mathrel{\mathcal{R}}y$ implies
$x\mathrel{\mathcal{R}^{\prime}}y$, that is, if $\mathrel{\mathcal{R}}$ is
contained in $\mathrel{\mathcal{R}^{\prime}}.$

The _transitive closure_ of a binary relation $\mathrel{\mathcal{R}}$ on a set
$X$ is the transitive relation $\mathrel{\mathcal{R}}^{+}$ on set $X$ such
that $\mathrel{\mathcal{R}}^{+}$ contains $\mathrel{\mathcal{R}}$ and
$\mathrel{\mathcal{R}}^{+}$ is minimal.

The _transitive reduction_ of a binary relation $\mathrel{\mathcal{R}}$ on a
set $X$ is, in case it exists, the smallest relation having the transitive
closure of $\mathrel{\mathcal{R}}$ as its transitive closure.

Given a binary relation $\mathrel{\mathcal{R}}$ on $X$, if two elements
$x,y\in X$ cannot be compared, that is, $\neg(x\mathrel{\mathcal{R}}y)$ as
well as $\neg(y\mathrel{\mathcal{R}}x)$, then it is denoted by $x\bowtie y$.
We shall denote $x\mathcal{I}y$ whenever $x\mathcal{R}y$ as well as
$y\mathcal{R}x$.

Sometimes (depending on the ordering or when different relations are mixed)
the standard notation is different. We also include it here.

######  Definition 4.

A _preorder_ $\precsim$ on $X$ is a binary relation on $X$ which is reflexive
and transitive. An antisymmetric preorder is said to be an _order_. A _total
preorder_ $\precsim$ on a set $X$ is a preorder such that if $x,y\in X$ then
$[x\precsim y]\vee[y\precsim x]$. A total order is also called a _linear
order_ , and a totally ordered set $(X,\precsim)$ is also said to be a
_chain_. Usually, an order that fails to be total is also said to be a
_partial order_ and it is also denoted by $\preceq$. A subset $Y$ of a
partially preordered set $(X,\precsim)$ is said to be an _antichain_ if
$x\bowtie y$ for any $x,y\in Y$.

If $\precsim$ is a preorder on $X$, then the associated _asymmetric_ relation
or _strict preorder_ is denoted by $\prec$ and the associated _equivalence_
relation by $\sim$ and these are defined, respectively, by $[x\prec
y\iff(x\precsim y)\wedge\neg(y\precsim x)]$ and $[x\sim y\iff(x\precsim
y)\wedge(y\precsim x)]$. In the case of a finite partial order (also known as
_poset_), it is quite common to denote $\precsim$ by $\sqsubseteq$ and $\prec$
by $\sqsubset$, respectively. The asymmetric part of a linear order
(respectively, of a total preorder) is said to be a _strict linear order_
(respectively, a _strict total preorder_).

######  Definition 5.

A preorder $\precsim$ on $X$ is said to be _near-complete_ if
$width(X,\precsim)$ $=n<\infty$. That is, if all antichains have cardinalities
less or equal than $n$ (for some $n\in\mathbb{N}$) as well as there is –at
least– one antichain which cardinality is $n$.

######  Definition 6.

A binary relation $\prec$ from $A$ to $X$ is a _biorder_ if it is Ferrers,
that is, if for every $a,b\in A$ and $x,y\in X$ the following condition holds:
$(a\prec x)\wedge(b\prec y)\Rightarrow(a\prec y)\vee(b\prec x).$

Related to $\prec$ we shall use the binary relation $\precsim$ from $X$ to $A$
given by $x\precsim a\iff\neg(a\prec x)$, $a\in A,\,x\in X$. It is also common
to use $\succsim$ from $A$ to $X$ given by $a\succsim x\iff\neg(a\prec x)$,
$a\in A,\,x\in X$.

######  Definition 7.

Associated to a biorder $\prec$ defined from $A$ to $X$, we shall consider two
new binary relations [12, 13]. These binary relations are said to be the
_traces_ of $\prec$. They are defined on $A$ and $X$, respectively, and
denoted by $\prec^{*}$, $\prec^{**}$. They are defined as follows:

First, $a\prec^{*}b\iff a\prec z\precsim b\ $ for some $z\in X\ \ (a,b\in A),$
and, similarly, $x\prec^{**}y\iff x\precsim c\prec y\ $ for some $c\in A\ \
(x,y\in X).$

######  Remark 8.

In the case of interval orders (so $A=X$) the binary relations denoted by
$\prec^{*}$ and $\prec^{**}$ coincide with the “ _left trace_ ” and “ _right
trace_ ” of the interval order. The names “ _left trace_ ” and “ _right trace_
” have been used in the case of biorders too [8], and other notations such as
$\prec_{A}$ and $\prec_{X}$ or $\prec^{l}$ and $\prec^{r}$ can be found in
literature [8, 13, 33].

######  Remark 9.

We set $a\precsim^{*}b\iff\neg(b\prec^{*}a)$, $a\sim^{*}b\iff
a\precsim^{*}b\precsim^{*}a$, $x\precsim^{**}y\iff\neg(y\prec^{**}x)$ and
$x\sim^{**}y\iff x\precsim^{**}y\precsim^{**}x$.

These weak relations can be characterized as follows [3, 4, 13]:

$a\precsim^{*}b\iff\\{b\prec x\Rightarrow a\prec x\\},\text{ for any }x\in X.$
$x\precsim^{**}y\iff\\{a\prec x\Rightarrow a\prec y\\},\text{ for any }a\in
A.$

As a matter of fact, both the binary relations $\precsim^{*}$ and
$\precsim^{**}$ are total preorders on $A$ and on $X$, respectively, if and
only if the relation $\prec$ is a biorder [13]. Hence, in that case the
indifference relations $\sim^{*}$ and $\sim^{**}$ are in fact equivalence
relations so, it is possible to define the quotient set $A/\sim^{*}$ and
$X/\sim^{**}$[9, 13].

Next Definition 13 introduces the notion of representability222Other notions
of representability appear for instance in [3, 13, 17, 33]. for total
preorders and biorders. The goal of a representation is to convert a
qualitative preference into a quantitative one, comparing real numbers instead
of elements of a set.

######  Definition 10.

Given a preorder $\precsim$ on $X$, a real function $u\colon X\to\mathbb{R}$
is said to be _isotonic_ or _increasing_ if for every $x,y\in X$ the
implication $x\precsim y\Rightarrow u(x)\leq u(y)$ holds true. In addition, if
it also holds true that $x\prec y$ implies $u(x)<u(y)$, then $u$ is said to be
a _Richter-Peler utility representation_.

A (not necessarily total) preorder $\precsim$ on a set $X$ is said to have a
multi-utility representation [20] if there exists a family $\mathcal{U}$ of
isotonic real functions such that for all points $x,y\in X$ the equivalence
$\\{x\precsim y\Leftrightarrow\forall u\in{\mathcal{U}}\,\,(u(x)\leq u(y))\\}$
holds.

This kind of representation always exists for every preorder $\precsim$ on $X$
(see Proposition 1 in [20]). It is also interesting to search for a continuous
multi-utility representation of a preorder $\precsim$ when the set $X$ is
endowed with a topology $\tau$ (cf., for instance, [2, 20]), as well as for
multi-utility representations through a finite number of functions.

When all the functions of the family $\mathcal{U}$ are order-preserving for
the preorder $\precsim$ (i.e., for all $u\in{\mathcal{U}}$, and $x,y\in X$,
$x\prec y$ implies that $u(x)<u(y)$), then the representation is called
Richter-Peleg multi-utility representation [32].

In case of a poset, we shall use too the following concept333A similar term
already exists in computer science under the name of _random structures_ (see
[40])..

######  Definition 11.

Let $(X,\sqsubseteq)$ be a finite partially ordered set with $|X|=n$. We shall
say that a Richter-Peleg multi-utility representation $\mathcal{U}$ is
_bijective_ when each function $u\in\mathcal{U}$ is a bijection from $X$ to
$\\{1,...,n\\}$.

######  Remark 12.

The number of functions needed for a Richter-Peleg multi-utility coincides
with the dimension of the partial order [44].

######  Definition 13.

A total preorder $\precsim$ on $X$ is called _representable_ if there is a
real-valued function $u\colon X\to\mathbb{R}$ that is order-preserving, so
that, for every $x,y\in X$, it holds that $[x\precsim y\iff u(x)\leq u(y)]$.
The map $u$ is said to be an _order-monomorphism_ (also known as a _utility
function_ for $\precsim$).

A biorder $\prec$ from $A$ to $X$ is said to be _representable_ (as well as
_realizable with respect to $<$_) if there exist two real-valued functions
$u\colon A\to\mathbb{R}$, $v\colon X\to\mathbb{R}$ such that $a\prec x\iff
u(a)<v(x)$ ($a\in A$, $x\in X$). In this case it is also said that the pair
$(u,v)$ _represents_ $\prec$.

Although we will work with this definition of representability for biorders
(realizable with respect to $<$), in Section 4 the following definition
(introduced in [13]) is also needed:

A biorder $\prec$ from $A$ to $X$ is said to be _representable with respect to
$\leq$_ (as well as _realizable with respect to $\leq$_) if there exist two
real-valued functions $u\colon A\to\mathbb{R}$, $v\colon X\to\mathbb{R}$ such
that $a\prec x\iff u(a)\leq v(x)$ ($a\in A$, $x\in X$). In this case we shall
say that the pair $(u,v)$ represents $\prec$ _with respect to $\leq$_.

######  Definition 14.

Let $\prec$ be an asymmetric relation from a topological space $(A,\tau_{A})$
to $(X,\tau_{X})$. The relation $\prec$ is said to be _$\tau_{A}$ -continuous_
if the strict contour set $L_{\prec}(x)=\\{a\in A:a\prec x\\}$ is a
$\tau_{A}$-open set, for every $x\in X$. Dually, it is said to be _$\tau_{X}$
-continuous_ if the strict contour set $U_{\prec}(a)=\\{x\in X:a\prec x\\}$ is
a $\tau_{X}$-open set, for every $a\in A$. We shall say that the relation is
_bicontinuous_ if it is both $\tau_{A}$-continuous and $\tau_{X}$-continuous.

In particular, in the case of a single set $X$ (that is, $A=X$) endowed with a
single topology $\tau$ (so, $\tau=\tau_{A}=\tau_{X}$), the binary relation
$\prec$ is said to be _upper semi-continuous_ if the strict contour set
$L_{\prec}(x)=\\{y\in X:y\prec x\\}$ is $\tau$-open, for every $x\in X$.
Dually, it is said to be _lower semi-continuous_ if the strict contour set
$U_{\prec}(x)=\\{y\in X:x\prec y\\}$ is $\tau$-open, for every $x\in X$. We
shall say that the relation is _$\tau$ -continuous_ if it is both upper and
lower semi-continuous.

######  Definition 15.

A biorder $\prec$ from $A$ to $X$ is said to be _continuously representable on
$(A,\tau_{A})$_ if it admits a representation $(u,v)$ such that the function
$u\colon A\to\mathbb{R}$ is continuous when $A$ is given the topology
$\tau_{A}$ and the real line is given its usual topology. Dually, $\prec$ is
said to be _continuously representable on $(X,\tau_{X})$_ if it admits a
representation $(u,v)$ such that the function $v\colon X\to\mathbb{R}$ is
continuous when $X$ is given the topology $\tau_{X}$ and the real line is
given its usual topology. We say that the biorder is _continuously
representable_ if it admits a representation $(u,v)$ such that both functions
$u$ and $v$ are continuous.

An example of a biorder (also related to the traces and the continuity of the
representation) may be found in [16]. Let us recall now some characterizations
of the representability, for total preorders and biorders.

######  Definition 16.

A total preorder $\precsim$ defined on $X$ is said to be _perfectly separable_
if there exists a countable subset $D\subseteq X$ such that for every $x,y\in
X$ with $x\prec y$ there exists $d\in D$ such that $x\precsim d\precsim y$.

Let $\prec$ be a biorder from $A$ to $X$. A subset $M$ of $A\cup X$ is said to
be _strictly dense_ (see [3, 13]) if for all $a\in A$ and $x\in X$, $a\prec x$
implies the existence of an element $m\in M$ such that either $m\in X\text{
and }a\prec m\precsim^{**}x$, or $m\in A\text{ and }a\precsim^{*}m\prec x$.

######  Remark 17.

Notice that if the number of classes defined by the equivalence relation
$\sim^{*}$ (or $\sim^{**}$) of the trace $\precsim^{*}$ (resp.
$\precsim^{**}$) on $A$ (resp. $X$) is countable, then the biorder has a
trivial strictly dense subset made by means of the representatives of classes
$A/\sim^{*}$ (resp. $X/\sim^{**}$).

The following result is well-known [9, 13].

######  Theorem 18.

Let $A$ and $X$ be two nonempty sets.

  1. (a)

A total preorder $\precsim$ on $X$ is representable if and only if it is
perfectly separable.

  2. (b)

A biorder $\prec$ from $A$ to $X$ is representable if and only if there exists
a countable strictly dense subset.

A similar study on representability of interval orders, semiorders (see also
[11]) and total preorders but now in the extended real line $\bar{\mathbb{R}}$
appears in [17].

Given a biorder $\prec$ from $A$ to $X$, it is possible to define the
corresponding quotient sets as well as a new relation (see [3])
$\mathrel{\widehat{\prec}}$ from $A/\sim^{*}$ to $X/\sim^{**}$ by

$\widehat{a}\mathrel{\widehat{\prec}}\widehat{x}\iff a\prec x,\text{ for any
}\widehat{a}\in A/\sim^{*},\,\widehat{x}\in X/\sim^{**}.$

It is known (see [3]) that this relation $\mathrel{\widehat{\prec}}$ is well
defined and that it is actually a biorder: the _quotient biorder_. It also
holds true that $\widehat{a}\mathrel{\widehat{\prec}}^{*}\widehat{b}\iff
a\prec^{*}b$, and $\widehat{x}\mathrel{\widehat{\prec}}^{**}\widehat{y}\iff
x\prec^{**}y$, for any $\widehat{a},\widehat{b}\in A/\sim^{*}$ and for any
$\widehat{x},\widehat{y}\in X/\sim^{**}$. Thus, any representation
$(\widehat{u},\widehat{v})$ of $\mathrel{\widehat{\prec}}$ has the additional
property that $\widehat{u}$ and $\widehat{v}$ also represent the traces
$\mathrel{\widehat{\prec}}^{*}$ and $\mathrel{\widehat{\prec}}^{**}$,
respectively.

Moreover, any representation $(\widehat{u},\widehat{v})$ of
$\mathrel{\widehat{\prec}}$ delivers also a representation of $\prec$ just
defining $u(a)=\widehat{u}(\widehat{a})$ and $v(x)=\widehat{v}(\widehat{x})$
(for any $a\in A$ and $x\in X$). Therefore, if $\mathrel{\widehat{\prec}}$ is
representable then $\prec$ is representable, too. The converse is also true as
the following lemma shows [3]:

######  Lemma 19.

Let $\prec$ be a biorder from $A$ to $X$ and let $\mathrel{\widehat{\prec}}$
be the corresponding quotient biorder from $A/\sim^{*}$ to $X/\sim^{**}$.
Assume that $\prec$ admits a representation $(u,v)$. Then,
$\mathrel{\widehat{\prec}}$ is also representable.

The following definition was introduced by Nakamura in [33] and, as it is
shown in Corollary 21 (see also [33] or Remark 1 in [8]), it is equivalent to
the aforementioned order-denseness condition named ‘strictly dense’.

######  Definition 20.

Let $\prec$ be a biorder from $A$ to $X$. A pair of subsets $A^{*}\subseteq A$
and $X^{*}\subseteq X$ is said to be _jointly dense_ for $\prec$ if for all
$a\in A$ and $x\in X$, $a\prec x$ implies the existence of two elements
$a^{*}\in A^{*}$ and $x^{*}\in X^{*}$ such that $a\precsim^{*}a^{*}\prec
x^{*}\precsim^{**}x$.

Next corollary is well-known [3, 8, 12, 33]:

######  Corollary 21.

Let $\prec$ be a biorder from $A$ to $X$. The following statements are
equivalent:

  1. ($i$)

The biorder has a pair of jointly dense and countable subsets.

  2. ($ii$)

The biorder has a countable strictly dense subset.

  3. ($iii$)

The biorder is representable.

  4. $(iv)$

The biorder is representable through a pair of functions $(u,v)$ with the
additional condition that $u$ represents the trace $\precsim^{*}$ and $v$ the
trace $\precsim^{**}$.

##  3 A new definition for Distributed System

In the following pages, we introduce a new definition for the concept of a
distributed system with $n$ processes (the original definitions of these
concepts –an event, a process and a distributed system– have been introduced
in Section 1). But first, we redefine the concepts of _causal precedence_ and
_communication_.

Since in the following pages many relations are going to appear, for the sake
of clarity, from now we shall use the symbol $\mathcal{P}$ in order to refer
to a biorder relation, whereas we shall use the symbol $\precsim$ for total
preorders (also for the traces associated to a biorder).

######  Definition 22.

Let $\\{(X_{k},\prec_{k})\\}_{k\in K}$ be a finite family of strict partially
ordered and disjoint sets (i.e., $X_{i}\cap X_{j}=\emptyset,\,\forall\,i\neq
j$) and $\\{\mathcal{P}_{ij}\\}_{i\neq j}$ a family of relations from $X_{i}$
to $X_{j}$ (for any $i\neq j,\,i,j\in K$). The _causal precedence_
corresponding to $\\{\prec_{k}\\}_{k\in K}\cup\\{\mathcal{P}_{ij}\\}_{i\neq
j}$ on $X=\bigcup\limits_{k\in K}X_{k}$ is the transitive closure of the union
$(\bigcup\limits_{k\in K}\prec_{k})\bigcup(\bigcup\limits_{i\neq
j}\\{\mathcal{P}_{ij}\\})$. This relation shall be denoted by $\rightarrow$:

$\\{(\bigcup\limits_{k\in K}\prec_{k})\bigcup(\bigcup\limits_{i\neq
j}\\{\mathcal{P}_{ij}\\})\\}^{+}=\rightarrow.$

######  Remark 23.

Notice that, with the definition above, the absence of cycles is not
guaranteed, as it is shown the Figure 4. The existence of this cycles implies
an error in the computing, known as _deadlock_ [26].

$a$$c$$b$$d$$\bullet$$\bullet$$\bullet$$\bullet$

Figure 4: A cycle in a distributed system: a deadlock

If there is no cycle, then the transitive closure is a strict partial order.
In the present paper we will assume that there is no error or deadlock in the
distributed system, that is, we shall assume that the causal precedence is a
strict partial order.

Now, recovering the idea of a distributed system in the spirit of Definition
1, we first mathematically formalize the idea of _communication_ just as a
finite relation between to distinct sets satisfying a ‘bijective’ condition.

######  Definition 24.

Let $A$ and $B$ be two disjoint sets. A _communication from $A$ to $B$_ is a
finite binary relation $\mathcal{P}\subseteq A\times B$ (so,
$|\mathcal{P}|<\infty$) such that for any $(a,b)\in\mathcal{P}$ and
$a^{\prime}\in A,\,b^{\prime}\in B$ the following _bijective_ condition is
satisfied:

$(a^{\prime},b)\in\mathcal{P}\Rightarrow a=a^{\prime}\quad\text{ as well as
}\quad(a,b^{\prime})\in\mathcal{P}\Rightarrow b^{\prime}=b.$

Here, the elements $a\in A$ such that $(a,b)\in\mathcal{P}$ (for some $b\in
B$) are said to be the _senders_ , whereas the elements $b\in B$ such that
$(a,b)\in\mathcal{P}$ (for some $a\in A$) are said to be the _receivers_ 444We
call them senders/receivers in the spirit of Definition 1..

Now, we focus on communications between ordered sets.

######  Definition 25.

Let $(A,\precsim_{A})$ and $(B,\precsim_{B})$ be two disjoint partially
ordered sets. We shall say that a binary relation $\mathcal{P}$ is a _causal
biorder_ from $A$ to $B$ if $\mathcal{P}\subseteq A\times B$ and for any
$a,c\in A$, $b,d\in B$ it holds that

$(a\mathcal{P}b)\text{ and }(c\mathcal{P}d)\quad\Rightarrow\quad(a\rightarrow
d)\text{ or }(c\rightarrow b),$

where $\rightarrow$ denotes the corresponding causal precedence of
$\precsim_{A}\cup\precsim_{B}\cup\mathrel{\mathcal{P}}$ on $A\cup B$.

######  Example 26.

Let $(A,\precsim_{A})$ and $(B,\precsim_{B})$ be two partially ordered sets as
defined in Figure 5. Let $\mathcal{P}$ and $\mathcal{P}^{\prime}$ be two
relations from $A$ to $B$ defined by:

$\mathcal{P}=\\{(a_{2},b_{1}),(a_{3},b_{3})\\}\quad\text{ and
}\quad\mathcal{P}^{\prime}=\\{(a_{2},b_{2}),(a_{3},b_{3})\\}.$

It is straightforward to see that $\mathcal{P}$ is a causal biorder whereas
$\mathcal{P}^{\prime}$ is not.

$(A,\precsim_{A})$${a}_{2}$${a}_{3}$${a}_{1}$$\bullet$$\bullet$$\bullet$

$(B,\precsim_{B})$$b_{2}$$b_{3}$$b_{1}$$\bullet$$\bullet$$\bullet$

Figure 5: Two partially ordered sets, $(A,\precsim_{A})$ and
$(B,\precsim_{B})$.

######  Definition 27.

Let $(A,\precsim_{A})$ and $(B,\precsim_{B})$ be two disjoint partially
ordered sets and $\mathcal{P}$ a communication from $A$ to $B$. We define the
relation $\overline{\mathcal{P}}$ from $A$ to $B$ by

$a\overline{\mathcal{P}}b\iff
a\precsim_{A}a^{\prime}\mathcal{P}b^{\prime}\precsim_{B}b,\text{ for some
}a^{\prime}\in A,b^{\prime}\in B.$

That is,
$\overline{\mathcal{P}}=\precsim_{A}\circ\mathcal{P}\circ\precsim_{B}$.

######  Proposition 28.

Let $(A,\precsim_{A})$ and $(B,\precsim_{B})$ be two disjoint partially
ordered sets and $\mathcal{P}$ any relation from $A$ to $B$. If
$(A,\precsim_{A})$ or $(B,\precsim_{B})$ is a chain, then:

  1. $(i)$

$\mathcal{P}$ is a causal biorder.

  2. $(ii)$

$\overline{\mathcal{P}}$ is a biorder.

In particular, any communication from $A$ to $B$ is a causal biorder.

###### Proof.

Let $a,x\in A$ and $b,y\in B$ be elements such that $a\mathcal{P}b$ and
$x\mathcal{P}y$. If $(A,\precsim_{A})$ is a chain, then $a\precsim_{A}x$ or
$x\precsim_{A}a$ is satisfied. Hence, it holds that
$a\precsim_{A}x\mathcal{P}yb$ or $x\precsim_{A}a\mathcal{P}b$, thus,
$a\rightarrow b$ or $x\rightarrow b$. So, $\mathcal{P}$ is a causal biorder.
We reason dually if $(B,\precsim_{B})$ is a chain.

Let $a,b\in A$ and $x,y\in B$ be points such that $a\overline{\mathcal{P}}x$
and $b\overline{\mathcal{P}}y$. Hence, by definition, there exist
$a^{\prime},b^{\prime}\in A$ and $x^{\prime},y^{\prime}\in X$ such that
$a\precsim_{A}a^{\prime}\mathcal{P}x^{\prime}\precsim_{B}x$ and
$b\precsim_{A}b^{\prime}\mathcal{P}y^{\prime}\precsim_{B}y$. If
$(A,\precsim_{A})$ is a chain, we distinguish two cases:

  1. 1.

If $a\precsim_{A}b$, then
$a\precsim_{A}b^{\prime}\mathcal{P}y^{\prime}\precsim_{B}y$, so
$a\overline{\mathcal{P}}y$.

  2. 2.

If $b\precsim_{A}a$, then
$b\precsim_{A}a^{\prime}\mathcal{P}x^{\prime}\precsim_{B}x$, so
$b\overline{\mathcal{P}}x$.

Therefore, $\overline{\mathcal{P}}$ is a biorder. We reason dually in case
$(B,\precsim_{B})$ is a chain. ∎

######  Remark 29.

$(1):$ By Proposition 28, it is clear that a communication $\mathcal{P}$ is a
causal biorder as well as $\overline{\mathcal{P}}$ is a biorder.

$(2):$ In order to keep close to the original definition given by Lamport (see
Definition 1), where sending or receiving a message is an event, in Definition
24 is not allowed to send a message from $a$ in $A$ to more than one receiver
in $B$. Dually, an element $b$ in $B$ cannot receive more than one message
from $A$. From a mathematical point of view, it would be possible to
generalise the idea of communication without restricting it to a finite
cardinal, that is, with $|\mathcal{P}|=\infty$. However, in the present paper
we shall work just on communications in the sense of Definition 24.

Now we are ready to propose a definition of a _distributed system of $n$ sets_
from a mathematical and theoretical point of view (the original definitions of
these concepts –an event, a process and a distributed system– have been
introduced in Section 1).

######  Definition 30.

Let $\\{(X_{i},\precsim_{i})\\}_{i=1}^{n}$ be a family of disjoint and totally
ordered sets and
$\mathrel{\mathcal{P}}=\\{\mathrel{\mathcal{P}_{ij}}\\}_{i\neq j}$ (with
$i,j\in\\{1,...,n\\}$) be a family of communications from $X_{i}$ to $X_{j}$
(with $i\neq j$). Each totally ordered set is said to be a _process_. Each
element of the processes is said to be an _event_. The pair
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}})$ is said to be
a _distributed system_.

######  Remark 31.

$(1)$ In the previous definition, as it was in the original definition of L.
Lamport (see [27], in particular page 559 and footnote 2), the messages may be
received out of order (that is, without satisfying the causal ordering of
messages). Furthermore, with this definition there may be cycles with respect
to the causal relation (see Figure 4).

$(2)$ Notice that a communication may be empty, so that there is no sending of
messages in one direction between two processes. In this case we shall denote
$\mathrel{\mathcal{P}_{ij}}=\\{\emptyset\\}$.

$(3)$ It can be proved that each total order $\precsim_{i}$ in $X_{i}$ refines
the traces $\precsim_{ij}^{*}$ and $\precsim_{ji}^{**}$ related to the
biorders $\overline{\mathcal{P}}_{ij}$ and $\overline{\mathcal{P}}_{ji}$
(respectively), for any $j\neq i$. Actually, this property was used in [16] in
order to define the concept of a distributed system of two processes. However,
the use of the _communication_ concept in order to define a distributed system
is closer to reality, since it captures the idea of sending and receiving
messages. Moreover, it derives in the new term of _causal biorder_ , which
seems interesting when dealing with a set endowed with more than one relation.
Hence, Definition 30 has been written by means of communications.

######  Proposition 32.

Let $(A,\precsim_{A})$ and $(B,\precsim_{B})$ be two disjoint totally ordered
sets and $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ two communications from $A$
to $B$. Let $((A,\precsim_{A})\cup(B,\precsim_{B}),\mathcal{P}_{1})$ and
$((A,\precsim_{A})\cup$ $(B,\precsim_{B}),\mathcal{P}_{2})$ be the
corresponding distributed systems and $\rightarrow_{1}$ and $\rightarrow_{2}$
their causal relations, respectively. If the causal relations concur, i.e.,
$\rightarrow_{1}=\rightarrow_{2}$, then the communications are also the same
(i.e., $\mathcal{P}_{1}=\mathcal{P}_{2}$) or the causal ordering of messages
is not satisfied.

###### Proof.

Let $a\in A$ and $b\in B$ be such that $a\mathcal{P}_{1}b$. Then,
$a\rightarrow_{1}b$, that means $a\rightarrow_{2}b$, thus, there exist
$a_{1},b_{1}$ such that $a\precsim_{A}a_{1}\mathcal{P}_{2}b_{1}\precsim_{B}b$.
Thus, $a\mathcal{P}_{1}b$ implies $a\overline{\mathcal{P}}_{2}b$.

Suppose now that $a\overline{\mathcal{P}}_{2}b$ but $\neg(a\mathcal{P}_{2}b)$.
Then, there must exist $a_{2}\in A,\,b_{2}\in B$ such that
$a\prec_{A}a_{2}\mathcal{P}_{2}b_{2}\precsim_{B}b$ or
$a\precsim_{A}a_{2}\mathcal{P}_{2}b_{2}\prec_{B}b$. Assume that
$a\prec_{A}a_{2}\mathcal{P}_{2}b_{2}\precsim_{B}b$ is satisfied (we reason
analogously for the dual case), then it holds that $a_{2}\rightarrow_{2}b$
with $a\prec_{A}a_{2}$, that is, $a_{2}\rightarrow_{1}b$ with
$a\prec_{A}a_{2}$. So, $a_{2}\overline{\mathcal{P}}_{1}b$, thus, $a\prec
a_{2}\precsim_{A}a_{3}\mathcal{P}_{1}b_{3}\precsim_{B}b$ for some $a_{3}\in
A$, $b_{3}\in B$.

Here we distinguish two cases. If $b_{3}=b$, then $\mathcal{P}_{1}$ fails to
be a communication since we have that $a_{3}\mathcal{P}_{1}b$ as well as
$a\mathcal{P}_{1}b$, with $a\neq a_{3}$. If $b_{3}\prec b$, then the causal
ordering of messages is not satisfied, since we have that
$a_{3}\mathcal{P}_{1}b_{3}$ and $a\mathcal{P}_{1}b$ as well as
$a\prec_{A}a_{2}$ and $b_{3}\prec_{B}b$ (see Figure 2). This concludes the
proof. ∎

Now, we introduce the concept of _line communication_.

######  Definition 33.

Let $(\bigcup\limits_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}})$ be
a distributed system, where
$\mathrel{\mathcal{P}}=\\{\mathrel{\mathcal{P}_{ij}}\\}_{i\neq j}$ (with
$i,j\in\\{1,...,n\\}$) is the family of communications from $X_{i}$ to $X_{j}$
(with $i\neq j$). It is said that $\mathrel{\mathcal{P}}$ is a _line
communication_ if $\mathcal{P}_{ij}=\\{\emptyset\\}$ for any $j\neq i+1$, for
each $i=1,...,n-1$.

Hence, when the processes are endowed with a line communication, these
computers or processes are ordered in a sequence (so, totally ordered) such
that each computer only sends messages to the next one (see Figure 6).

$(X_{1},\precsim_{1})$$(X_{2},\precsim_{2})$$(X_{3},\precsim_{3})$

Figure 6: A distributed system of three processes with line communication.

######  Proposition 34.

Let
$(\bigcup\limits_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup\limits_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ and
$(\bigcup\limits_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}^{\prime}}=\bigcup\limits_{i\neq
j}\mathrel{\mathcal{P}^{\prime}_{ij}})$ be two distributed systems with the
same processes and both with line communication. Assume that the causal
ordering of messages is always satisfied as well as there is no cycles (that
is, the $\rightarrow$ is a strict partial order). Then, the corresponding
causal precedences coincide ($\rightarrow_{1}=\rightarrow_{2}$) if and only if
$\mathrel{\mathcal{P}}_{ij}=\mathrel{\mathcal{P}^{\prime}}_{ij}$ for each
$i\neq j$, that is, if and only if they have the same communications.

###### Proof.

$\Rightarrow:$ If the corresponding causal precendeces coincide, then they
also coincide when we restrict the relation to a subset $X_{i}\cup X_{i+1}$
(for any $i=1,...,n-1$). Moreover, since $\mathrel{\mathcal{P}}$ is a line
communication, it holds that $\rightarrow_{1{|_{X_{i}\cup
X_{i+1}}}}=(\precsim_{i}\cup\precsim_{i+1}\cup\mathrel{\mathcal{P}}_{i\,i+1})^{+}$,
that is, the restriction of the causal relation $\rightarrow_{1}$ to
$X_{i}\cup X_{i\,i+1}$ is just the causal relation of the distributed system
$((X_{i},\precsim_{i})\cup(X_{i+1},\precsim_{i+1}),\mathcal{P}_{i\,i+1})$.
Dually, it holds that $\rightarrow_{2{|_{X_{i}\cup
X_{i+1}}}}$$=(\precsim_{i}\cup\precsim_{i+1}\cup\mathrel{\mathcal{P}}_{i\,i+1}^{\prime})^{+}$.
Therefore, by Proposition 32, the communications
$\mathrel{\mathcal{P}}_{i\,i+1}$ and $\mathrel{\mathcal{P}^{\prime}}_{i\,i+1}$
also coincide, and that for any $i=1,...,n-1$.

$\Leftarrow:$ This implication is trivial. ∎

######  Remark 35.

Notice that the descomposition of a partially ordered set in $n$ disjoint
chains is not unique. Therefore, it may be possible to construct distinct
distributed systems such that the corresponding causal relation coincides with
the initial partial order. In order to show that we include the following
example:

######  Example 36.

Let $\precsim$ be a partial order defined on $X=\\{a,b,c,d\\}$ by
$\\{c\precsim b\precsim a,b\precsim d\\}$. Then, the partial order can be
characterized by means of the following distributed systems (among others) of
2 processes (see Figure 7):

$(1)$ $(X_{1},\precsim_{1})=(\\{a,b,c\\},c\prec_{1}b\prec_{1}a)$ and
$(X_{2},\precsim_{2})=(\\{d\\},\\{\emptyset\\})$, with communication
$\mathcal{P}_{12}=\\{(b,d)\\}$.

$(2)$ $(X_{1},\precsim_{1})=(\\{a,c\\},c\prec_{1}a)$ and
$(X_{2},\precsim_{2})=(\\{b,d\\},b\prec_{2}d)$, with communications
$\mathcal{P}_{12}=\\{(c,b)\\}$ and $\mathcal{P}_{21}=\\{(b,a)\\}$.

$a$$b$$c$$d$$\bullet$$\bullet$$\bullet$$\bullet$

$a$$c$$d$$b$$\bullet$$\bullet$$\bullet$$\bullet$

Figure 7: A partial order represented through two distinct distributed
systems.

######  Remark 37.

Hence, given a preorder, it seems interesting to study the existence and
uniqueness of distributed systems that characterize (through its causal
precedence) the preorder with some additional properties such as that the
length of the processes is minimal, or that the number of messages is minimal,
etc. For instance, in the example of Figure 7, in the first case the length of
the longest process is three and the number of messages is one, whereas in the
second case these values are two and two, respectively.

##  4 Representability of Distributed Systems

Since it is possible to add a new process to a distributed system (that is,
connecting another computer to the system, including also the corresponding
communication), it is interesting to study how to create a new representation
of the distributed system arised from the union of two distributed systems,
but now aggregating the representations before.

In this paper we do not achieve the answer to this question but, at least, we
are able to construct weak representations of distributed systems with line
communications starting from pairs of functions that represent each biorder.

We shall assume that the causal ordering of messages is satisfied, as well as
there are no cycles. Thus, we assume that our distributed systems are such
that the causal relation $\rightarrow$ is a strict partial order.

The following definitions introduce the concept of representability for a
distributed system of $n$ processes.

######  Definition 38.

Let
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ be a distributed system. We say that it is
_weakly representable_ if there exists a family $\\{u_{i}\\}_{i=1}^{n}$
(called _weak representation_) of real functions $u_{i}\colon
X_{i}\to\mathbb{R}$ such that $(u_{i},u_{j})$ weakly represents the biorder
$\mathrel{\overline{\mathcal{P}}_{ij}}$ with respect to $<$ (that is,
$x_{i}\mathrel{\overline{\mathcal{P}}_{ij}}x_{j}\Rightarrow
u_{i}(x_{i})<u_{j}(x_{j})$, for any $x_{i}\in X_{i},\,x_{j}\in X_{j}$) as well
as each $u_{i}$ represents the total order $\precsim_{i}$ (i.e.,
$x\precsim_{i}y\iff u_{i}(x)\leq u_{i}(y),\,x,y\in X_{i}$), for any
$i,j\in\\{1,...,n\\}$ and $i\neq j$.

If each set $X_{i}$ is endowed with a topology $\tau_{i}$, then we will say
that the distributed system is _continuously weakly representable_ if there
exists a continuous weak representation.

######  Remark 39.

$(1)$ Notice that, for any $x\in X_{i}$ and $y\in X_{j}$ such that
$x\rightarrow y$, it holds that $u_{i}(x)<u_{j}(y)$, for any
$i,j\in\\{1,2,...,n\\}$.

$(2)$ The aforementioned functions $u_{i}$ are known as _Lamport clocks_ (see
[27]). In fact, a Lamport clock is a function $\mathcal{C}$ satisfying that
$a\rightarrow b$ implies $\mathcal{C}(a)<\mathcal{C}(b)$, for any $a,b\in X$.
On the other hand, $\mathcal{C}(a)<\mathcal{C}(b)$ does not imply
$a\rightarrow b$.

######  Definition 40.

Let
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ be a distributed system. We say that it is
_(finitely) representable_ if there exists a (finite) family of weak
representations $\\{\\{u_{i}^{k}\\}_{i=1}^{n}\\}_{k\in\mathcal{K}}$ such that
$x_{i}\mathrel{\overline{\mathcal{P}}_{ij}}x_{j}$ iff
$u^{k}_{i}(x_{i})<u_{j}^{k}(x_{j})$ for any $k\in\mathcal{K}$, for any
$x_{i}\in X_{i},\,x_{j}\in X_{j}$ and $i\neq j$.

If each set $X_{i}$ is endowed with a topology $\tau_{i}$, then we will say
that the distributed system is _continuously representable_ if there exists a
continuous representation.

As following Preposition 41 shows, the term before is analogous to the
Richter-Peleg multi-utility representation used for preorders. [6, 7, 20, 36,
38]

######  Proposition 41.

A distributed system
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ is (finitely) representable if and only if the
corresponding causal relation $\rightarrow$ is (finitely) Richter-Peleg multi-
utility representable.

###### Proof.

Given a representation $\\{\\{u_{i}^{k}\\}_{i=1}^{n}\\}_{k\in\mathcal{K}}$ of
the distributed system, the family of functions
$\\{w_{k}\\}_{k\in\mathcal{K}}$ defined by

$w_{k}(x)=u_{i}^{k}(x)\text{ if }x\in X_{i},\text{ with }k\in\mathcal{K},$

is a Richter-Peleg multi-utility representation of the strict partial order
$\rightarrow$.

Dually, starting from a Richter-Peleg multi-utility representation
$\\{w_{k}(x)\\}_{k\in\mathcal{K}}$ of the causal relation $\rightarrow$ of a
distributed system
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$, then the following representation
$\\{\\{u_{i}^{k}\\}_{i=1}^{n}\\}_{k\in\mathcal{K}}$ arises:

$u_{i}^{k}(x)=w_{k}(x),\text{ when }x\in X_{i},\text{ with
}k\in\mathcal{K},\text{ for each }i=1,...,n.$

∎

######  Remark 42.

Notice that the main difference is the domain of the corresponding functions.
In the case of distributed systems the functions are defined on the processes,
whereas in the case of preorders they are defined on all the set (which would
be the union of the processes). This difference may be relevant when dealing
with continuity and topological spaces.

Now we introduce another kind of representation in bijection with the concept
of multi-utility [6, 7, 20, 36, 38], and that it is actually common and known
in computing by _vector clock representation_ (see [31, 37]). Due to that
coincidence (and in order to distinguish it from the definition before), we
shall call it by _vector representation_.

######  Definition 43.

Let
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ be a distributed system. We say that it is
_vector representable_ if there exists a family of weaks representations with
respect to $\leq$ (called _vector clocks_)
$\\{\\{u_{i}^{k}\\}_{i=1}^{n}\\}_{k\in\mathcal{K}}$ such that
$x_{i}\mathrel{\overline{\mathcal{P}}_{ij}}x_{j}$ iff $u_{i}^{k}(x_{i})\leq
u_{j}^{k}(x_{j})$ for any $k\in\mathcal{K}$, as well as there exists an index
$l\in\mathcal{K}$ such that $u_{i}^{l}(x_{i})<u_{j}^{l}(x_{j})$ (for any
$x_{i}\in X_{i},\,x_{j}\in X_{j}$ and $i\neq j$).

If each set $X_{i}$ is endowed with a topology $\tau_{i}$, then we will say
that the distributed system is _continuously vector representable_ if there
exists a continuous vector representation.

######  Remark 44.

In computing, these vector clocks are constructed through _timestamps_
algorithms (see [31, 37]).

The problem of aggregating representations is not trivial. In order to
ilustrate that, we include the following example.

######  Example 45.

Let $\mathcal{P}_{12}$ and $\mathcal{P}_{23}$ two communications between
$A=\\{a,b\\}$ (with $a\prec_{A}b$) and $X=\\{x,y\\}$ (with $x\prec_{X}y$) and
$\Lambda=\\{\alpha,\beta\\}$ (with $\alpha\prec_{\Lambda}\beta$),
respectively, defined as follows:

$a\mathcal{P}_{12}x\mathcal{P}_{23}\beta,\quad
a\mathcal{P}_{12}y\quad\text{and}\quad b\mathcal{P}_{12}y.$

Now we define the tuple $(u,v,w)$ by $u(a)=0,u(b)=1,v(x)=1,v(y)=2,w(\alpha)=1$
and $w(\beta)=2$. Then, the pairs $(u,v)$ and $(v,w)$ are representations of
the distributed systems defined on $A\cup X$ and on $X\cup\Lambda$,
respectively. However, the tuple $(u,v,w)$ fails to represent the distributed
system made up by the three processes: $u(a)=0<w(\alpha)=1$ but
$\neg(a\rightarrow\alpha)$.

$b$$a$$\beta$$\alpha$$y$$x$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

$1$$0$$2$$1$$2$$1$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

Figure 8: A distributed system. Each process contains just two events. The
dashed arrows represent the communication between processes.

In the following lines it is shown how to construct weak representations of
distributed systems with line communications starting from pairs of functions
that represent each biorder. For more clearness, before introduce the general
case, first we include here the particular case of a distributed system of
three processes with a linear communication.

######  Proposition 46.

Let
$(\bigcup_{i=1}^{3}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i=1}^{2}\mathrel{\mathcal{P}_{i\,i+1}})$
a distributed system of three processes with a linear communication such that
for every $i\in\\{1,2\\}$ the pair $(u_{i},v_{i})$ is a representation of the
biorder $\mathrel{\overline{\mathcal{P}}_{i\,i+1}}$555We may assume, without
loss of generality, that the codomain of the utilities is the interval $(0,1)$
instead of the all real line.. Then, the tuple
$(u=u_{1}+u_{u_{2}},v=v_{1}+u_{2},w=v_{2}+v_{v_{1}})$ is a weak representation
of the distributed system, where $u_{u_{2}}$ and $v_{v_{1}}$ are defined as
follows:

$u_{u_{2}}(x)=\inf\\{u_{2}(y)\colon x\overline{\mathcal{P}}_{12}y\,;\,y\in
X_{2}\\};\text{ for any }x\in X_{1},$ $v_{v_{1}}(x)=\sup\\{v_{1}(y)\colon
y\overline{\mathcal{P}}_{23}x\,;\,y\in X_{2}\\};\text{ for any }x\in X_{3},$

on the assumption that $\inf\\{\emptyset\\}=1$ and $\sup\\{\emptyset\\}=0.$

###### Proof.

First, notice that since the utilities take values on $(0,1)$, and taking into
account that $\inf\\{\emptyset\\}=1$ and $\sup\\{\emptyset\\}=0$, the
functions $u_{u_{2}}$ and $v_{v_{1}}$ are well defined (that is, the infimum
and the supremum always exist).

Let $x,y$ be two elements such that $x\overline{\mathcal{P}}_{12}y$. Then, it
holds true that $u_{1}(x)<v_{1}(y)$ as well as $u_{u_{2}}(x)\leq u_{2}(y)$.
Therefore, the condition $u(x)<v(y)$ is satisfied. We argue analogously for a
pair of elements $x,y$ such that $x\overline{\mathcal{P}}_{23}y$.

Since $x\precsim_{1}x^{\prime}\overline{\mathcal{P}}_{12}y$ implies
$x\overline{\mathcal{P}}_{12}y$, the inequality $u_{u_{2}}(x)\leq
u_{u_{2}}(x^{\prime})$ is also satisfied. If $x\precsim_{1}x^{\prime}$ and
there is no $y\in X_{2}$ such that $x^{\prime}\overline{\mathcal{P}}_{12}y$,
then $u_{u_{2}}(x^{\prime})=\inf\\{\emptyset\\}=1$ so, again, it holds that
$u_{u_{2}}(x)\leq u_{u_{2}}(x^{\prime})$. Thus, we conclude that
$u_{u_{2}}(x)\leq u_{u_{2}}(x^{\prime})$ is always satisfied for any
$x,x^{\prime}\in X_{1}$ such that $x\precsim_{1}x^{\prime}$. We argue
analogously for a pair of elements $y,y^{\prime}\in X_{3}$ such that
$y\precsim_{3}y^{\prime}$. In addition, the functions $v_{1}$ and $u_{2}$ also
represent the total order $\precsim_{2}$, as well as $u_{1}$ and $v_{2}$
represent the total orders $\precsim_{1}$ and $\precsim_{3}$, respectively.
Hence, we deduce that the functions $u=u_{1}+u_{u_{2}},v=v_{1}+u_{2}$ and
$w=v_{2}+v_{v_{1}}$ are representations of the total orders $\precsim_{1}$,
$\precsim_{2}$ and $\precsim_{3}$, respectively.

Let $x,z$ be now two elements such that
$x\overline{\mathcal{P}}_{12}y\overline{\mathcal{P}}_{23}z$, for some $y\in
X_{2}$. Then, since it holds true that $u_{1}(x)<v_{1}(y)\leq v_{v_{1}}(z)$
and $u_{u_{2}}(x)\leq u_{2}(y)\leq v_{2}(z)$, the condition $u(x)<w(z)$ is
satisfied.

Thus, we conclude that $(u=u_{1}+u_{u_{2}},v=v_{1}+u_{2},w=v_{2}+v_{v_{1}})$
is a weak representation of the distributed system. ∎

Before generalize the proposition above to $n$ processes, first we introduce
the following operators.

######  Definition 47.

Let $(\bigcup_{i=1}^{2}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}})$ be a
distributed system with a single communication $\mathcal{P}$ from $X_{1}$ to
$X_{2}$. Let $u$ and $v$ be two (not necessarily strictly) increasing
functions on $X_{1}$ and $X_{2}$ (respectively) that take values on $(0,1)$.
Assume that $\inf\\{\emptyset\\}=1$ and $\sup\\{\emptyset\\}=0.$Then, we
define the following two operators:

$\underline{op}(v)(x)=\inf\\{v(y)\colon x\overline{\mathcal{P}}y\\}_{\\{y\in
X_{2}\\}}\,;\quad x\in X_{1},$ $\overline{op}(u)(x)=\sup\\{u(y)\colon
y\overline{\mathcal{P}}x\\}_{\\{y\in X_{1}\\}}\,;\quad x\in X_{2}.$

We shall call these operators _lower operator_ and _upper operator_ ,
respectively.

######  Remark 48.

$(1)$ Notice that, starting from a function $u$ on $X_{1}$, $\overline{op}(u)$
defines a new function on $X_{2}$, and not in $X_{1}$. Dually, starting now
from a function $v$ on $X_{2}$, $\underline{op}(v)$ defines a new function on
$X_{1}$, and not in $X_{2}$.

$(2)$ In fact, since sending and receiving messages is an event, the infimum
(of a non-empty set) is a minimum and the suprema (of a non-empty set) is a
maximum. Otherwise, the infimum of an empty set is the top of the ordered set,
that is, 1, and the supremum is the bottom, that is, 0.

######  Proposition 49.

Let $(\bigcup_{i=1}^{2}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}})$ be a
distributed system with a single communication $\mathcal{P}$ from $X_{1}$ to
$X_{2}$. Let $u$ and $v$ be two (not necessarily strictly) increasing
functions on $X_{1}$ and $X_{2}$ (respectively) that take values on $(0,1)$.
Then, the following properties are satisfied:

  1. ($i$)

$\underline{op}(v)$ and $\overline{op}(u)$ are increasing in $X_{1}$ and
$X_{2}$, respectively.

  2. ($ii$)

The pairs $(\underline{op}(v),v)$ and $(u,\overline{op}(u))$ represent the
biorder $\overline{\mathcal{P}}$ with respect to $\leq$.

  3. $(iii)$

$x_{1}\sim^{*}y_{1}$ implies
$\underline{op}(v)(x_{1})=\underline{op}(v)(y_{1})$, as well as
$x_{2}\sim^{**}y_{2}$ implies
$\overline{op}(v)(x_{2})=\overline{op}(v)(y_{2})$, for any $x_{1},y_{1}\in
X_{1},\,x_{2},y_{2}\in X_{2}$.666Here, $\sim^{*}$ and $\sim^{**}$ denote the
equivalence relations associated to the traces $\precsim^{*}$ and
$\precsim^{**}$ of the biorder $\mathrel{\overline{\mathcal{P}}}$,
respectively.

###### Proof.

$(i):$ If $x\precsim_{1}y$, then it holds that $y\overline{\mathcal{P}}z$
implies $x\overline{\mathcal{P}}z$. Therefore, applying the definition of the
lower operator, it follows that the inequality
$\underline{op}(v)(x)\leq\underline{op}(v)(y)$ is satisfied, that is,
$\underline{op}(v)$ is increasing with respect to $\precsim_{1}$ on $X_{1}$.
We argue dually in order to prove that $\overline{op}(u)$ is increasing with
respect to the total order $\precsim_{2}$ defined on $X_{2}$.

$(ii):$ If $x\overline{\mathcal{P}}y$, then applying the definition of the
lower operator, it is clear that the inequality
$\underline{op}(v)(x)\leq(v)(y)$ is satisfied. We argue analogously for the
pair $(u,\overline{op}(u))$. On the other hand, suppose that
$\underline{op}(v)(x)\leq v(y)$. Since $v$ takes values on $(0,1)$,
$\underline{op}(v)(x)=r\in(0,1)$, which means that (by definition of
$\underline{op}(v)$) there exists $z\in X_{2}$ such that
$x\overline{\mathcal{P}}z$ with $v(z)=r$ (here take into account Remark 48
(2)). Thus, $v(z)=r\leq v(y)$ and then, $z\precsim_{2}y$. Therefore, we
conclude that $x\overline{\mathcal{P}}y$. Hence, the pair
$(\underline{op}(v),v)$ represents the biorder with respect to $\leq$.

$(iii):$ If $x_{1}\sim^{*}y_{1}$, then $x_{1}\overline{\mathcal{P}}z$ holds if
and only if $y_{1}\overline{\mathcal{P}}z$ is satisfied, for any $z\in X_{2}$.
Therefore, by the definition of the lower opertator, the equality
$\underline{op}(v)(x_{1})=\underline{op}(v)(y_{1})$ holds true. We argue
analogously for the indifference $\sim^{**}$. ∎

######  Remark 50.

$(1)$ Dealing with a distributed system
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ of $n$ processes, since –by Proposition 49
$(i)$– $\underline{op}(u_{i})$ and $\overline{op}(u_{i})$ are increasing in
their corresponding sets ($X_{i-1}$ and $X_{i+1}$, respectively), it is
possible to apply an operator more than once. So, starting from an increasing
function $u_{i}$ in $X_{i}$, we shall denote by $\underline{op}^{2}(u_{i})$
the function $\underline{op}(\underline{op}(u_{i}))$ defined in $X_{i-2}$.
This notation is generalized to $\underline{op}^{k}(u_{i})$, achieving a
function in $X_{i-k}$. We shall use the same notation for the upper operator
$\overline{op}$. Since the hypothesis of Proposition 49 are again satisfied
(now for $\underline{op}^{k}(u_{i})$ and $\overline{op}^{k}(u_{i})$), the
proporties $(i)$ and ($ii$) are also true for these iterations.

$(2)$ The fact that the functions $u$ and $v$ are strictly increasing (thus,
they represent the corresponding total preorder) does not guarantee that
$\underline{op}(v)$ and $\overline{op}(u)$ are also.

######  Theorem 51.

Let
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i=1}^{n-1}\mathrel{\mathcal{P}_{i\,i+1}})$
a distributed system of $n$ processes with a line communication such that for
every $i\in\\{1,...,n-1\\}$ the pair $(u_{i},v_{i})$ is a representation of
the biorder $\overline{\mathcal{P}}_{i\,i+1}$, with the additional property
that $u_{i}$ and $v_{i}$ represent the total orders $\precsim_{i}$ and
$\precsim_{i+1}$, respectively. Then, $(w_{1},...,w_{n})$ is a weak
representation of the distributed system, where each function $w_{i}$ is
defined on $X_{i}$ by a sum of $n-1$ functions as follows:

$w_{1}$ | $=$ | $u_{1}+\sum_{k=1}^{n-2}\underline{op}^{k}(u_{k+1})$
---|---|---
$w_{2}$ | $=$ | $v_{1}+u_{2}+\sum_{k=1}^{n-3}\underline{op}^{k}(u_{k+2})$
$w_{3}$ | $=$ | $\overline{op}(v_{1})+v_{2}+u_{3}+\sum_{k=1}^{n-4}\underline{op}^{k}(u_{k+3})$
$\vdots$ | $\vdots$ | $\vdots$
$w_{j}$ | $=$ | $\sum_{k=1}^{j-2}\overline{op}^{j-1-k}(v_{k})+v_{j-1}+u_{j}+\sum_{k=1}^{n-j-1}\underline{op}^{k}(u_{k+j})$
$\vdots$ | $\vdots$ | $\vdots$
$w_{n}$ | $=$ | $v_{n-1}+\sum_{k=1}^{n-2}\overline{op}^{k}(v_{n-1-k})$

###### Proof.

First, in the following table we recover the distinct functions defined on
each process:

$X_{1}$ | $X_{2}$ | $X_{3}$ | $\cdots$ | $X_{n-1}$ | $X_{n}$
---|---|---|---|---|---
$u_{1}$ | $v_{1}$ | $\overline{op}(v_{1})$ | $\cdots$ | $\overline{op}^{n-3}(v_{1})$ | $\overline{op}^{n-2}(v_{1})$
$\underline{op}(u_{2})$ | $u_{2}$ | $v_{2}$ | $\cdots$ | $\overline{op}^{n-4}(v_{2})$ | $\overline{op}^{n-3}(v_{2})$
$\underline{op}^{2}(u_{3})$ | $\underline{op}(u_{3})$ | $u_{3}$ | $\cdots$ | $\overline{op}^{n-5}(v_{3})$ | $\overline{op}^{n-4}(v_{3})$
$\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$
$\underline{op}^{n-2}(u_{n-1})$ | $\underline{op}^{n-3}(u_{n-1})$ | $\underline{op}^{n-4}(u_{n-1})$ | $\cdots$ | $u_{n-1}$ | $v_{n-1}$

So, then, each function $w_{i}$ is the sum of all these $n-1$ functions
defined on the set $X_{i}$. Let’s see now that this tuple $(w_{1},...,w_{n})$
is a weak representation of the distributed system.

Since –by Proposition 49 $(i)$– all the functions defined on each set $X_{i}$
(for each $i\in\\{1,...,n\\}$) are increasing (with respect to the
corresponding total order $\precsim_{i}$) and there is –at least– one which is
strictly increasing ($u_{i}$ and/or $v_{i-1}$), we conclude that the sum of
all of them (denoted by $w_{i}$) is a representation of the total order
$\precsim_{i}$.

Finally, taking into account Proposition 49 $(ii)$ and that $(u_{i},v_{i})$ is
a representation of the biorder $\overline{\mathcal{P}}_{i\,i+1}$ (for each
$i\in\\{1,...,n-1\\}$) with respect to $<$, it is straightward to check that
if $x\overline{\mathcal{P}}_{i\,i+1}y$ holds then $w_{i}(x)<w_{i+1}(y)$ is
satisfied (for each $i\in\\{1,...,n-1\\}$ and for any $x\in X_{i},\,y\in
X_{i+1}$). So, we conclude that $(w_{1},...,w_{n})$ is a weak representation
of the distributed system. ∎

##  5 Quasi-finite partial orders

In this section a particular but interesting class of partial orders are
studied: _quasi-finite partial orders_. This kind of structures includes all
those partial orders that can be understood as a finite family of chains with
a communication. The key of this section is to focus the research on the
quotient sets (with respect to the traces of the biorders), which makes
possible a discrete study of the representability, achieving results not only
of the quotient structure but also of the original one. Thus, it is also
possible to apply some techniques on finite posets as those introduced in
[19].

In fact, given a distributed system
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$, we may define an equivalence relation
$\mathcal{I}_{i}$ on $X_{i}$ by means of the intersection of all the
equivalence relations $\mathcal{I}_{ij}^{*}$ and $\mathcal{I}_{ji}^{**}$ (for
any $i\neq j$) on $X_{i}$ (that is, the equivalence relation associated to the
union of all the traces on $X_{i}$) (see Remark 9). Then, since the
communication is a finite relation, the cardinal of each quotient set
$\overline{X}_{i}=X_{i}/\mathcal{I}_{i}$ is finite, for any $i=1,...,n$.

The goal of the present section is the attainment of a method to construct
finite Richter-Peleg multi-utility representations for quasi-finite partial
orders, i.e., a representation method for distributed systems. For more
clarity, Example 55 is included in order to show this procedure.

Let’s see how quasi-finite partial orders are defined.

######  Definition 52.

We shall say that a partial order on a set is _quasi-finite_ if it is the
causal relation of a distributed system.

######  Remark 53.

$(1)$ By definition, quasi-finite partial orders are near-complete.

$(2)$ Given a distributed system
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$, we may be interested just in the communication
$\mathrel{\mathcal{P}}$ and skip the remaining information, that is, the total
orders $\precsim_{i}$. In that case, a finite poset
$(\bigcup_{i=1}^{n}(X_{i}/\mathcal{I}_{i},\overline{\precsim}_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ is achieved, where $\overline{\precsim}_{i}$ is
the total order on $\overline{X}_{i}=X_{i}/\mathcal{I}_{i}$ and now the
communication $\mathrel{\mathcal{P}}$ is restricted to the quotient sets (see
Example 11 in [16]).

The following theorem shows how to construct a Richter-Peleg multi-utility
representation of a quasi-finite partial order, just starting from a bijective
Richter-Peleg multi-utility representation (see Definition 11) of a finite
poset and utilities of total preorders.

######  Theorem 54.

Let $\precsim$ be a quasi-finite partial order on $X$ that coincides with the
causal relation associated to a distributed system
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$. Let $\\{w_{i}\\}_{i=1}^{n}$ be a family of
utilities777We may assume, without loss of generality, that the codomain of
the utilities is the interval $(0,1)$ instead of the all real line.
$w_{i}\colon(X_{i},\precsim_{i})\to(0,1)$ and
$\mathcal{U}=\\{u_{l}\\}_{l=1}^{k}$ a bijective Richter-Peleg multi-utility
representation associated to
$(\bigcup_{i=1}^{n}(X_{i}/\mathcal{I}_{i},\overline{\precsim}_{i}),$
$\mathrel{\mathcal{P}})$. Then, the family of functions
$\mathcal{V}=\\{v_{l}\\}_{l=1}^{k}$ defined by

$v_{l}(x)=u_{l}(\bar{x})+w_{i}(x),\quad\text{if }x\in X_{i},\forall x\in X$

is a Richter-Peleg multi-utility representation of the quasi-finite partial
order $\precsim$.

###### Proof.

$\Rightarrow:$ Let $x,y$ be two elements in $X$ such that $x\prec y$.

If $x$ and $y$ belong to the same process $X_{i}$, then $x\prec_{i}y$ so,
$w_{i}(x)<w_{i}(y)$. Since $x\prec_{i}y$, it is also true that
$x\precsim_{ij}^{*}y$ as well as $x\precsim_{ji}^{**}y$ for any trace defined
on $X_{i}$. Therefore, $u_{l}(\bar{x})\leq u_{l}(\bar{y})$ is satisfied, for
any function $u_{l}\in\mathcal{U}$. Hence, we conclude that
$v_{l}(x)<v_{l}(y)$ for any $v_{l}\in\mathcal{V}$.

If $x$ and $y$ belong to distinct processes, $X_{i}$ and $X_{j}$ respectively,
then it holds that $x\overline{\mathcal{P}}_{ij}y$ so,
$u_{l}(\bar{x})<u_{l}(\bar{y})$ is satisfied for any $u_{l}\in\mathcal{U}$.
Therefore, since $u_{l}(\bar{x})+1\leq u_{l}(\bar{y})$ and the codomain of the
utilities is the interval $(0,1)$, we conclude that that $v_{l}(x)<v_{l}(y)$
for any $v_{j}\in\mathcal{V}$.

$\Leftarrow:$ Suppose that $v_{l}(x)<v_{l}(y)$ is satisfied for any
$v_{l}\in\mathcal{V}$. Since $v_{l}(x)=u_{l}(\bar{x})+w_{i}(x)$ (with $x\in
X_{i}$, for any $i=1,...,n$) and the codomain of the utilities is the interval
$(0,1)$, $v_{l}(x)<v_{l}(y)$ holds true if and only if $u_{l}(\bar{x})\leq
u_{l}(\bar{y})$ for any $u_{l}\in\mathcal{U}$.

Now, we distinguish two cases. 888Here notice that, since
$\mathcal{U}=\\{u_{l}\\}_{l=1}^{k}$ is bijective Richter-Peleg multi-utility
associated to the poset arised from the quotient of the traces on the
processes, $u_{l_{0}}(x)=u_{l_{0}}(y)$ holds true (for some index $l_{0}$) if
and only if both elements belong to the same class (and so, also to the same
process). As a matter of fact, since they belong to the same class then it
holds that $u_{l}(x)=u_{l}(y)$ not only for that index $l_{0}$ but also for
any index $l$.

  1. 1.

$u_{l}(\bar{x})<u_{l}(\bar{y})$ for any $u_{l}\in\mathcal{U}$. In that case we
distinguish again two cases.

    1. (a)

$x$ and $y$ belong to the same process $X_{i}$. In that case, since
$u_{l}(\bar{x})<u_{l}(\bar{y})$ for any $u_{l}\in\mathcal{U}$, there exists a
trace $\precsim_{ij}^{*}$ or $\precsim_{ji}^{**}$ on $X_{i}$ such that
$x\prec_{ij}^{*}y$ or $x\prec_{ji}^{**}y$. Thus, we conclude that
$x\prec_{i}y$ and, hence, $x\prec y$.

    2. (b)

$x$ and $y$ belong to distinct processes, $X_{i}$ and $X_{j}$ respectively. In
that case, since $u_{l}(\bar{x})<u_{l}(\bar{y})$ for any
$u_{l}\in\mathcal{U}$, there exist elements $x_{k_{1}}\in
X_{k_{1}},...,x_{k_{s}}\in X_{k_{s}}$ (for some
$k_{1},...,k_{s}\in\\{1,...,n\\}$) such that
$x\mathrel{\overline{\mathcal{P}}}_{i\,k_{1}}x_{k_{1}}\mathrel{\overline{\mathcal{P}}}_{k_{1}\,k_{2}}\cdots\mathrel{\overline{\mathcal{P}}}_{k_{s-1}\,k_{s}}x_{k}\mathrel{\overline{\mathcal{P}}}_{k_{s}\,j}y$.
Thus, we conclude that $x\prec y$.

  2. 2.

$u_{l}(\bar{x})=u_{l}(\bar{y})$ for any $u_{l}\in\mathcal{U}$. In that case
$x$ and $y$ belong to the same quotient class and, therefore, to the same
process. Thus, since $u_{l}(\bar{x})=u_{l}(\bar{y})$ for any
$u_{l}\in\mathcal{U}$ and $v_{l}(x)<v_{l}(y)$ for any $v_{l}\in V$, it holds
that $w_{i}(x)<w_{i}(y)$. Then, we conclude that $x\prec_{i}y$ and, hence,
$x\prec y$.

∎

$y_{1}\,\bullet$$x_{1}\,\bullet$$y_{2}\,\bullet$$x_{2}\,\bullet$$\bullet\,y_{3}$$\bullet\,z_{3}$$\bullet\,x_{3}$$(X_{1},\precsim_{1})$$(X_{2},\precsim_{2})$$(X_{3},\precsim_{3})$

Figure 9: The distributed system of three processes of Example 55.

######  Example 55.

Let $(X_{1},\precsim_{1}),(X_{2},\precsim_{2})$ and $(X_{3},\precsim_{3})$ be
three totally ordered sets (they may be uncountable, but representable in any
case) such that $x_{i}=\max\\{(X_{i},\precsim_{i})\\}$ and
$y_{i}=\min\\{(X_{i},\precsim_{i})\\}$, for $i=1,2,3.$ Suppose that there is a
communication between these sets (defined by
$\mathcal{P}_{12},\mathcal{P}_{13}$ and $\mathcal{P}_{32}$) as it is shown in
Figure 9, such that $y_{1}\mathrel{\mathcal{P}}_{13}z_{3},$
$x_{1}\mathrel{\mathcal{P}}_{12}y_{2}$ and
$x_{3}\mathrel{\mathcal{P}}_{32}y_{2}$.

If we focus on the quotient we achieve the poset of Figure 10. Here, it is
straightforward to check that $\overline{x}_{1}=U_{\prec_{1}}(y_{1})\subseteq
X_{1}$, $\overline{y}_{1}=L_{\precsim_{1}}(y_{1})\subseteq X_{1}$,
$\overline{x}_{2}=X_{2}$, $\overline{x}_{3}=U_{\precsim_{3}}(z_{3})\subseteq
X_{3}$ and $\overline{y}_{3}=L_{\prec_{3}}(z_{3})\subseteq X_{3}$.

$\overline{x}_{1}$$\overline{y}_{1}$$\overline{x}_{3}$$\overline{y}_{3}$$\overline{x}_{2}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

$4$$2$$3$$1$$5$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

$2$$1$$4$$3$$5$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

Figure 10: Hasse diagram and the corresponding bijective Richter-Peleg multi-
utility $\\{u_{1},u_{2}\\}$ of the quotient associated to the distributed
system of Figure 9.

So, now, given $w_{1},w_{2}$ and $w_{3}$ three representations (that take
values on $(0,1)$) of $\precsim_{1}$, $\precsim_{2}$ and $\precsim_{3}$,
respectively, we can easily construct a representation of the distributed
system through these functions and the utilities of the poset, as commented in
Theorem 54:

$v_{1}(x)=u_{1}(\bar{x})+w_{i}(x),\quad\text{if }x\in X_{i},\forall x\in X,$
$v_{2}(x)=u_{2}(\bar{x})+w_{i}(x),\quad\text{if }x\in X_{i},\forall x\in X.$

It is straightforward to see that $\\{v_{1},v_{2}\\}$ is also a Richter-Peleg
multi-utility of the causal relation (see Proposition 41).

In the theorem before, the functions of the representation are defined through
the sum of two functions. Hence, it is possible to study the continuity of the
functions of the representation by means of the continuity of the other ones.

######  Theorem 56.

Let
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}}=\bigcup_{i\neq
j}\mathrel{\mathcal{P}_{ij}})$ be a distributed system where each set $X_{i}$
is endowed with a topology $\tau_{i}$. Let $\mathcal{I}_{i}$ be the
equivalence relation on $X_{i}$ emerged from the intersection of all the
equivalence relations $\sim_{ij}^{*}$ and $\sim_{ji}^{**}$ (for any $i\neq j$)
on $X_{i}$. Assume that the following conditions are satisfied for each
$i=1,...,n$:

  1. $(i)$

The total orders $\precsim_{i}$ are $\tau_{i}$-continuous and representable.

  2. $(ii)$

Each class $\overline{x}=\\{y\in X_{i}\,\colon\,y\mathcal{I}_{i}x\\}$ is open
in $X_{i}$, for any $x\in X_{i}$.

Then, the distributed system is continuously representable.

###### Proof.

By Theorem 54, we may construct a representation of the distributed system
such that each function $v_{l}$ is defined in $X_{i}$ by
$v_{l}(x)=u_{l}(\bar{x})+w_{i}(x)$ (as stated in Theorem 54). By hypothesis
$(i)$, we may assume that $w_{i}$ is continuous [9], and by condition $(ii)$
it is straightforward to see that $u_{l}$ is continuous too. Hence, each
function $v_{l}$ is continuous in $X_{i}$, for any $i=1,...,n$. ∎

######  Remark 57.

The reciprocal of the theorem above is not true (see Example 11 and Remark 12
of [16]).

From Theorem 56 and Proposition 41 the following corollary is deduced, which
may be useful if we are focusing on a quasi-finite partially ordered set
$(X,\precsim)$ endowed with a topology.

######  Corollary 58.

Let $\precsim$ be a quasi-finite partial order on $(X,\tau)$. Assume that
there exists a distributed system
$(\bigcup_{i=1}^{n}(X_{i},\precsim_{i}),\mathrel{\mathcal{P}})$ such that the
following conditions are satisfied for each $i=1,...,n$:

  1. $(i)$

The total orders $\precsim_{i}$ are $\tau_{i}$-continuous and representable,
where $\tau_{i}=\tau_{|_{X_{i}}}$.

  2. $(ii)$

Each class $\overline{x}=\\{y\in X_{i}\,\colon\,y\mathcal{I}_{i}x\\}$ is open
in $X_{i}$, for any $x\in X_{i}$.

  3. $(iii)$

Any open set $U\in\tau_{i}$ is also open in $\tau$.

Then, there exists a continuous and finite Richter-Peleg multi-utility of the
partial order $\precsim$ on $(X,\tau)$.

##  6 Further comments

For a sake of brevity and clearness, in the present paper we have argued on
total orders and partial orders, however, it can be easily generalised to
total preorders and preorders.

The sections related to representability (and the aggregation problem) may be
implemented through partial functions, using the idea of partial
representability (see [6]). In order to illustrate this final idea, we include
the following result:

######  Proposition 59.

Let $(X_{1},\precsim_{1}),(X_{2},\precsim_{2})$ and $(X_{3},\precsim_{3})$ be
three representable totally ordered sets and $\mathcal{P}_{12}$ and
$\mathcal{P}_{23}$ two communications from $X_{1}$ to $X_{2}$ and from $X_{2}$
to $X_{3}$, respectively. Thus, the structure arised is a distributed system
of three processes with line communication. Assume that each biorder is
representable, such that:

$x\overline{\mathcal{P}}_{12}y\iff u_{1}(x)<v_{1}(y),\text{ for any }x\in
X_{1},y\in X_{2},$ $y\overline{\mathcal{P}}_{23}z\iff v_{2}(y)<w_{1}(z),\text{
for any }y\in X_{2},z\in X_{3},$

as well as the biorder $\overline{\mathcal{P}}_{13}$ emerged from the
composition $\overline{\mathcal{P}}_{12}\circ\overline{\mathcal{P}}_{23}$
(i.e., $x\overline{\mathcal{P}}_{13}z\iff
x\overline{\mathcal{P}}_{12}y\overline{\mathcal{P}}_{23}z$, for some $y\in
X_{2}$) is representable by $(u_{2},w_{2}):$

$x\overline{\mathcal{P}}_{13}z\iff u_{2}(x)<w_{2}(z),\text{ for any }x\in
X_{1},z\in X_{3}.$

(Here, we assume that the functions $u_{1},u_{2},v_{1},v_{2},w_{1}$ and
$w_{2}$ takes values on $(0,1)$, as well as they also represent the total
order of the corresponding set). Then, the associated causal relation
$\rightarrow$ is partially representable (see [6]) through the functions
$\\{\sigma_{1},\sigma_{2},\sigma_{3}\\}$ defined as follows:

$\sigma_{1}(x)=\left\\{\begin{array}[]{ll}u_{1}(x)&\mbox{; }x\in
X_{1}\\\\[4.0pt] v_{1}(x)&\mbox{; }x\in X_{2}\\\\[4.0pt] w_{1}(x)+1&\mbox{;
}x\in X_{3}\\\\[4.0pt]
\end{array}\right.\qquad\sigma_{2}(x)=\left\\{\begin{array}[]{ll}u_{1}(x)&\mbox{;
}x\in X_{1}\\\\[4.0pt] v_{2}(x)+1&\mbox{; }x\in X_{2}\\\\[4.0pt]
w_{1}(x)+1&\mbox{; }x\in X_{3}\\\\[4.0pt] \end{array}\right.$

$\sigma_{3}(x)=\left\\{\begin{array}[]{ll}u_{2}(x)&\mbox{; }x\in
X_{1}\\\\[4.0pt] \emptyset&\mbox{; }x\in X_{2}\\\\[4.0pt] w_{2}(x)&\mbox{;
}x\in X_{3}\\\\[4.0pt] \end{array}\right.$

So that, $\quad x\rightarrow y$ if and only if $\sigma(x)<\sigma(y)$ for some
$\sigma\in\\{\sigma_{i}\\}_{i=1}^{3}$ as well as $\sigma_{i}(x)<\sigma_{i}(y)$
for any $i=1,2,3$ such that $\sigma_{i}$ is defined on both $x$ and $y$.

## Acknowledgments

Asier Estevan acknowledges financial support from the Ministry of Science and
Innovation of Spain under grant PID2021-127799NB-I00 as well as from the UPNA
under grant JIUPNA19-2022.

## References

  * [1] McCord, Michael C. (1990). Slot grammar: a system for simpler construction of practical natural language grammars. In R. Studer (ed.), Natural Language and Logic: International Scientific Symposium, pp. 118–45. Lecture Notes in Computer Science. Berlin: Springer-Verlag.
  * [2] Alcantud, J.C.R.; Bosi, G.; Zuanon, M.; Richter-Peleg multi-utility representations of preorders, _Theory and Decision_ 80(2016) 443-450. .
  * [3] Aleskerov, F.; Bouyssou, D.; Monjardet, B.; Utility maximization, choice and preference (second edition), Springer, Berlin, 2007.
  * [4] Bosi, G.; Candeal, J.C.; Induráin, E.; Continuous representability of interval orders and biorders, _Journal of Mathematical Phychology_ 51 (2007) 122-125.
  * [5] Bosi, G.; Estevan, A.; Gutiérrez García, J.; Induráin, E.; Continuous representability of interval orders, the topological compatibility setting, _Internat. J. Uncertain. Fuzziness Knowledge-Based Systems_ 23 (3)(2015) 345-365.
  * [6] Bosi, G.; Estevan, A.; Zuanon, M.; Partial representations of orderings, _Internat. J. Uncertain. Fuzziness Knowledge-Based Systems_. 26 (03) (2018), 453-473.
  * [7] Bosi, G.; Herden, G.; On continuous multi-utility representations of semi-closed and closed preorders, Mathematical Social Sciences 79 (2016), 20-29.
  * [8] Bouyssou, D.; Marchant, T.; Biorders with frontiers, _Order_ 28 (1) (2011) 53-87.
  * [9] Bridges, D.S.; Mehta, G.B.; Representations of Preference Orderings, Berlin-Heidelberg-New York: Springer-Verlag, 1995.
  * [10] Busemann, H.; Timelike spaces, PWN Publishers, Warszawa, 1967.
  * [11] Candeal, J.C.; Estevan, A.; Gutiérrez-García, J.; Induráin, E.; Semiorders with separability properties, _Journal of Mathematical Phychology_ 56 (2012), 444-451.
  * [12] Chateauneuf, A.; Continuous representation of a preference relation on a connected topological space, _Journal of Mathematical Economics_ 16 (1987) 139-146.
  * [13] Doignon, J.P.; Ducamp, A.; Falmagne, J.C.; On realizable biorders and the biorder dimension of a relation. _Journal of Mathematical Phychology_ 28 (1984) 73-109.
  * [14] Doignon, J.P.; Monjardet, B.; Roubens, M.; Vincke, Ph.; Biorder families, valued relations and preference modelling, _Journal of Mathematical Phychology_ 30 (1988) 435-480.
  * [15] Ducamp, A.; Falmagne, J.Cl.; Composite Measurement, _Journal of Mathematical Phychology_ , 6(3) (1969) 359-390.
  * [16] Estevan, A.; Some results on biordered structures, in particular distributed systems. _Journal of Mathematical Phychology_ 77 (2017) 70-81.
  * [17] Estevan, A.; Gutiérrez García, J.; Induráin, E.; Numerical Representation of Semiorders. _Order_ 30 (2013) 455-462.
  * [18] Estevan, A.; Gutiérrez García, J.; Induráin, E.; Further results on the continuous representability of semiorders. _Internat. J. Uncertain. Fuzziness Knowledge-Based Systems_ 21, (5) (2013) 675-694.
  * [19] Estevan, A.; Valero, O.; Schellekends, M.; Approximating SP-orders through total preorders: incomparability and transitivity through permutations. _Quaestiones Mathematicae_. 40 (2017), 414-433.
  * [20] Evren, O.; Ok, E.A.; On the multi-utility representation of preference relations, Journal of Mathematical Economics 47 (2011), 554-563.
  * [21] Fidge, C.; Logical time in distributed computing systems, _IEEE Computer_ (1991) 28-33.
  * [22] Fishburn, P.C.; Intransitive indifference in preference theory: a survey, _Operations Research_ 18 (2) (1970) 207-228.
  * [23] Fishburn, P.C.; Interval Orders and Interval Graphs, Wiley, New York, 1985\.
  * [24] Guttman, L.A.; A basis for scaling qualitative data. _American Sociological Review_ , 91, (1944), 13-150.
  * [25] Kronheimer, E. H.; Penrose, R.; On the structure of causal spaces, _Proc. Camb. Phil. Soc._ , 63 (1966), 481-501.
  * [26] Kshemkalyani,A. D.; Singhal, M.; _Distributed Computing: Principles, Algorithms, and Systems._ Cambridge University Press. 2011.
  * [27] Lamport, L.; Time, clocks and the ordering of events in a distributed system, _ACM Commun. Comput. Algebra_ 21 (7) (1978) 558-565.
  * [28] Levin, V. L.; Functionally closed preorders and strong stochastic dominance, _Soviet Math. Doklady_ 32 (1985), 22-26.
  * [29] Levin, V. L.; The Monge-Kantorovich problems and stochastic preference relation, _Advances in Mathematical Economics_ , 3 (2001), 97-124.
  * [30] Luce, R.D.; Semiorders and a theory of utility discrimination, _Econometrica_ 24 (1956) 178-191.
  * [31] Mattern, F.; Virtual time and global satates of distributed systems, _Proceedings of the International Workshop on Parallel and Distributed Algorithms_.
  * [32] Minguzzi, E.; Normally Preordered Spaces and Utilities, Order 30 (2013), 137-150.
  * [33] Nakamura, Y.; Real interval representations, _Journal of Mathematical Phychology_ 46 (2002) 140-177.
  * [34] Nishimura, H.; Ok, E. A.; Representation of an incomplete and nontransitive preference relation, _Journal of Economic Theory_ , 166 (2016), 164-185.
  * [35] Panangaden, P.; Causality in Physycs and computation, _Theorical Computer Science_ 546 (2014) 10-16.
  * [36] Peleg, B.; Utility functions for partially ordered topological spaces, _Econometrica_ (1996) 49-56.
  * [37] Raynal, M.; Singhal, M.; Logical time: capturing causality in distributed systems, _IEEE Computer_ (1991) 28-33.
  * [38] Richter, M.; Revealed preference theory, _Econometrica_ 34 (1966) 635-645.
  * [39] Riguet, J.; Sur les ensembles réguliers de relations binaires, les relations de Ferrers, _Comptes Rendus de l’Académie des Sciences_ , 231, (1950), 936-937.
  * [40] Schellekens, M.; _A modular calculus for the average cost of data structuring_. Springer. 2008. SBN 978-0-387-73384-5.
  * [41] Scott D.; Suppes, P.; Foundational aspects of theories of measurement, _J. Symbolic Logic_ 23 (1958) 113-128.
  * [42] Singhal, M.; _Advanced Concepts in Operating Systems_. Tata Mcgraw Hill Education Pvt. Limited, 2011.
  * [43] Torres-Rojas, F. J.; Ahamad, M.; Plausible clocks: constant size logical clocks for distributed systems, _Distributed Computing_ 12 (1999) 179-195.
  * [44] Trotter, W.T.; Combinatorics and Partially Ordered Sets: Dimension Theory. The Johns Hopkins University Press.
  * [45] Tversky, A.; Intransitivity of preferences, _Psychological Review_ 76 (1969) 31-48.