Towards Generalised Half-Duplex Systems¹¹1This work has been supported by the French government, through the EUR DS4H Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-17-EURE- 0004.

FIFO automata, also known as asynchronous communicating automata (i.e., finite state automata that exchange messages via FIFO queues) are an interesting formalism for modeling distributed protocols. In their most general formulation, these automata are Turing powerful, and in order to be able to model check them it is necessary to reduce their expressiveness.

Binary half-duplex systems, introduced by Cece and Finkel [6], are systems with two participants and a bidirectional channel formed of two FIFO queues, such that communication happens only in one direction at a time. The stereotypical half-duplex device is the walkie-talkie (or the CB). In several applications, in particular when FIFO buffers are bounded and sends may be blocking, half-duplex communications are considered a good practice to avoid send-send deadlocks. Language support for enforcing this discipline of communication includes, for instance, binary session types [15, 16] or Sing# channel contracts [11, 21].

In [6], Cece and Finkel show that (1) whether a system is half-duplex is decidable in polynomial time, (2) the set of reachable configurations is regular, and (3) properties like progress and boundedness are decidable in polynomial time. Cece and Finkel also present two possible notions ‘multiparty half-duplex’ systems generalizing their class to systems of any number of machines for p2p communications (one FIFO queue per pair of machine).

The first generalisation involves assuming that at most one queue over all queues is non-empty at any time. This generalisation preserves decidability but is very restrictive. The second generalisation restricts the communications between each pair of participants to half-duplex communications, that is only one buffer per bidirectional channel can be used simultaneously. This generalisation however does not preserve decidability: the systems captured by this definition form a Turing powerful class. In fact, with just three machines it is possible to mimic the tape of a Turing machine.

It could be believed that these results end the discussion about multi-party half-duplex systems. In this work, we claim conversely that there is another natural and relevant notion of multi-party half-duplex communications that allows us to generalise the results of Cece and Finkel. We introduce greedy systems, which are systems for which all executions can be rescheduled in such a way that all receptions are immediately preceded by their corresponding send. This notion is quite natural, and closely related to other notions like synchronisability [4], $1$-synchronous systems [5], or existentially $1$-bounded system [13] (see Section 6 for a detailed discussion).

In this work, we establish the following results:

1. 1.

   whether a system is greedy is decidable in polynomial time (when the number of processes is fixed);

2. 2.

   for greedy systems, all regular safety properties, which includes reachability, absence of unspecified receptions, progress, and boundedness are decidable in polynomial time.

3. 3.

   we generalize binary half-duplex systems to multiparty mailbox half-duplex systems and we show that (1) mailbox half-duplex systems are greedy, and (2) greedy systems without orphan messages, at least in the binary case, are half-duplex.

The first result follows from techniques developed by Bouajjani et al [5] for $k$-synchronous systems. The main challenge here is that we address a more general model of communicating systems that encompasses both mailbox and p2p communications, but also allows any form of sharing of buffers among processes. The second result is based on an approach that, to the best of our knowledge, is new, although it borrows from some general principles from regular model-checking. The challenge is that, unlike for binary half-duplex systems, the reachability set of greedy systems is not regular, which complicates how automata-based techniques can be used to solve regular safety. The third contribution aims at answering, although incompletely, the question we would like to address with this work: what is a relevant notion of multi-party half-duplex systems?

For a finite set $S$, $S^{*}$ denotes the set of finite words over $S$, $w_{\_}1\cdot w_{\_}2$ denotes the concatenation of two words, $|w|$ denotes the length of $w$, and $\epsilon$ denotes the empty word. We assume some familiarity with non-deterministic finite state automata, and we write $\mathcal{L}(\mathcal{A})$ for the language accepted by the automaton $\mathcal{A}$. For two sets $S$ and $I$, we write $\mathbf{b}$ (in bold) for an element of $S^{I}$, and $b_{\_}i$ for the $i$-th component of $\mathbf{b}$, so that $\mathbf{b}=(b_{\_}i)_{\_}{i\in I}$.

A FIFO automaton is basically a finite state machine equipped with FIFO queues where transitions are labelled with either queuing or dequeuing actions. More precisely:

Actions $a=(i,{\dagger},v)$, for ${\dagger}\in\{!,?\}$ are also denoted by $i{\dagger}v$. Given a FIFO automaton $\mathcal{A}=(L,\mathbb{V},I,\delta,l_{\_}0)$, a configuration of $\mathcal{A}$ is a tuple $\gamma=(l,\mathbf{b})\in L\times\mathbb{V}^{I}$. The initial configuration is $\gamma_{0}=(l_{\_}0,\mathbf{b}^{\emptyset})$ where for all $i\in I$, $b^{\emptyset}_{i}=\epsilon$. A step is a tuple $(\gamma,a,\gamma^{\prime})$ (often written $\gamma\xrightarrow[\tiny\mathcal{A}]{a}\gamma^{\prime}$) where $\gamma=(l,\mathbf{b})$ and $\gamma^{\prime}=(l^{\prime},\mathbf{b}^{\prime})$ are configurations and $a$ is an action, such that the following holds:

• •

  $(l,a,l^{\prime})\in\delta$,

• •

  if $a=i!v$, then $b^{\prime}_{\_}i=b_{\_}i\cdot v$ and $b_{\_}j^{\prime}=b_{\_}j$ for all $j\in I\setminus\{i\}$.

• •

  if $a=i?v$, then $b_{\_}i=v\cdot b_{\_}i^{\prime}$ and $b_{\_}j^{\prime}=b_{\_}j$ for all $j\in I\setminus\{i\}$.

Next, we define systems of FIFO automata. We pick a very general definition, where each FIFO queue might be queued (resp. dequeued) by more than one automaton, and where an automaton might ‘send a message to itself’. Most of the theory can be done in this general setting without extra cost, but we merely have in mind either mailbox systems or p2p systems (defined below).

A FIFO system, later called simply a system, is a family $\mathfrak{S}=(\mathcal{A}_{\_}p)_{\_}{p\in\mathbb{P}}$ of FIFO automata such that all FIFO automata have disjoint sets of actions: for all $p\neq q\in\mathbb{P}$, $\mathsf{Act}_{\_}p\cap\mathsf{Act}_{\_}q=\emptyset$. Each $p\in\mathbb{P}$ is referred to as a process. The condition on the disjointness of the sets of actions helps to identify the process that is responsible for a given action: for an action $a$, we write $\mathsf{process}(a)$ to denote the unique $p$ (when it exists) such that $a\in\mathsf{Act}_{\_}p$.

Let us now define mailbox and p2p systems. Informally, a p2p system is a system in which each pair of processes has a dedicated buffer for exchanging messages. Instead, for mailbox communication, each process receives messages from all other processes in a single buffer. Let us now formally define these notions. To this aim, it will be useful to identify what are the buffers an automaton queues in (resp. dequeues from). Hence, for a given FIFO automaton $\mathcal{A}_{\_}p=(L_{\_}p,\mathbb{V}_{\_}p,I_{\_}p,\mathsf{Act}_{\_}p,\delta_{\_}p,l_{\_}{0,p})$, and for ${\dagger}\in\{!,?\}$, we write $I_{\_}p^{\dagger}$ for the set of buffer identifiers $i$ such that there exists $v\in\mathbb{V}_{\_}p$ such that $i{\dagger}v\in\mathsf{Act}_{\_}p$. A system $\mathfrak{S}=(\mathcal{A}_{\_}p)_{\_}{p\in\mathbb{P}}$ is p2p if for all $p\in\mathbb{P}$, $I_{\_}p\subseteq\mathbb{P}^{2}$, $I^{!}_{\_}p=\{p\}\times(\mathbb{P}\setminus\{p\})$, and $I^{?}_{\_}p=(\mathbb{P}\setminus\{p\})\times\{p\}$. A system $\mathfrak{S}=(\mathcal{A}_{\_}p)_{\_}{p\in\mathbb{P}}$ is a mailbox system if for all $p\in\mathbb{P}$, $I_{\_}p\subseteq\mathbb{P}$, $I_{\_}p^{!}=\mathbb{P}\setminus\{p\}$ and $I_{\_}p^{?}=\{p\}$. Thus in a p2p system with $n$ processes, there are at most $n(n-1)$ buffers, and in a mailbox system with $n$ processes there are at most $n$ buffers. A binary system is a system $\mathfrak{S}=(\mathcal{A}_{\_}p)_{\_}{p\in\mathbb{P}}$ such that $\mathbb{P}=\{1,2\}$ and for all $p\in\mathbb{P}$, $I_{\_}p^{!}=\{3-p\}=I_{\_}{3-p}^{?}$; note that a binary system is both p2p and mailbox. We sometimes use a more handy notation for actions of a mailbox (resp. p2p) system: if $\mathsf{process}(i!v)=p$ and $\mathsf{process}(i?v)=q$, we sometimes write $!v^{\tiny p\to q}$ instead of $i!v$ and $?v^{\tiny p\to q}$ instead of $i?v$.

The size $|\mathfrak{S}|$ of $\mathfrak{S}$ is the sum of the $|\mathcal{A}_{\_}p|$. Note that $|\mathbb{P}|$ and $|I|$ are independent from the size of $\mathfrak{S}$. In particular, when we say that an algorithm is in polynomial time, we mean in time $\mathcal{O}(|\mathfrak{S}|^{k})$ for some $k$ that may depend on $|\mathbb{P}|$ and $|I|$.

The FIFO automaton $\mathsf{product}(\mathfrak{S})$ associated with $\mathfrak{S}$ is the standard asynchronous product automaton: $\mathsf{product}(\mathfrak{S})=(\Pi_{\_}{p\in\mathbb{P}}L_{\_}p,\bigcup_{\_}{p\in\mathbb{P}}\mathbb{V}_{\_}p,\bigcup_{\_}{p\in\mathbb{P}}I_{\_}p,\delta,\mathbf{l}_{\_}0)$ where $\mathbf{l}_{\_}0=(l_{\_}{0,p})_{\_}{p\in\mathbb{P}}$ and $\delta$ is the set of triples $(\mathbf{l},a,\mathbf{l}^{\prime})$ for which there exists $p\in\mathbb{P}$ such that $(l_{\_}p,a,l_{\_}p^{\prime})\in\delta_{\_}p$ and $l_{\_}q=l_{\_}q^{\prime}$ for all $q\in\mathbb{P}\setminus\{p\}$. We often identify $\mathfrak{S}$ and $\mathsf{product}(\mathfrak{S})$ and write for instance $\xrightarrow[\tiny\mathfrak{S}]{a}$ instead of $\xrightarrow[\tiny\mathsf{product}(\mathfrak{S})]{a}$. Similarly, we say that $\gamma=(\mathbf{l},\mathbf{b})$ is a configuration of $\mathfrak{S}$ while we mean that $\gamma$ is a configuration of $\mathsf{product}(\mathfrak{S})$. An execution $e=a_{\_}1\cdots a_{\_}n\in\mathsf{Act}^{*}$ is a sequence of actions. As usual $\xRightarrow{e}$ stands for $\xrightarrow{a_{\_}1}\cdots\xrightarrow{a_{\_}n}$. We write $\mathsf{executions(\mathfrak{S})}$ for $\{e\in\mathsf{Act}^{*}\mid\gamma_{\_}0\xRightarrow[\tiny\mathfrak{S}]{e}\gamma\mbox{ for some }\gamma\}$.

Next, we introduce the definition of reachable configuration:

Given an execution $e=a_{\_}1\cdots a_{\_}n$, we say that $\{j,j^{\prime}\}\subseteq\{1,\cdots,n\}^{2}$ is a matching pair if there exists a buffer identifier $i$, a message $v$ and natural number $k$ such that (1) $a_{\_}j=i!v$, (2) $a_{\_}{j^{\prime}}=i?v$, (3) $a_{\_}j$ is the $k$-th send action on $i$ in $e$, and (4) $a_{\_}{j^{\prime}}$ is the $k$-th receive action on $i$ in $e$. A communication of $e$ is either a matching pair $\{j,j^{\prime}\}$, or a singleton $\{j\}$ such that $j$ does not belong to any matching pair (such a communication is called unmatched). We write $\mathsf{com}(e)$ to denote the set of communications of $e$.

An execution imposes a total order on the actions. Sometimes, however, it is useful to visualise only the causal dependencies between actions. Message sequence charts [18] are usually used to this aim, as they only depict an order between matched pairs of actions and between actions of the same process. However, message sequence charts do not represent graphically the causal dependencies due to shared buffers, like the ones found in mailbox systems. Here we define action graphs that depict all causal dependencies. When considering p2p communications, action graphs and message sequence charts coincide. We say that two actions $a_{\_}1,a_{\_}2$ commute if $\mathsf{process}(a_{\_}1)\neq\mathsf{process}(a_{\_}2)$ and it is not the case that $a_{\_}1$ and $a_{\_}2$ are two actions of the same type on a same buffer: there is no ${\dagger}\in\{!,?\}$, $i\in I$ and $v_{\_}1,v_{\_}2\in\mathbb{V}$ such that $a_{\_}1=i{\dagger}v_{\_}1$ and $a_{\_}2=i{\dagger}v_{\_}2$.

When $j\prec_{\_}{e}j^{\prime}$, we say that $a_{\_}j$ happens before $a_{\_}{j^{\prime}}$. Note that for an execution $e$ with $e\in\mathsf{executions(\mathfrak{S})}$, $\prec_{\_}{e}^{*}$ is a partial order. Two executions $e,e^{\prime}$ are causally equivalent, denoted by $e\stackrel{{\scriptstyle\tiny\mathfrak{S}}}{{\sim}}e^{\prime}$, if their action graphs are isomorphic. Said differently, $e,e^{\prime}$ are causally equivalent if they are two linearisations of a same happens before partial order. Note that if $\gamma_{0}\xRightarrow[\tiny\mathfrak{S}]{e}\gamma$ and $e\stackrel{{\scriptstyle\tiny\mathfrak{S}}}{{\sim}}e^{\prime}$, then $\gamma_{0}\xRightarrow[\tiny\mathfrak{S}]{e^{\prime}}\gamma$.

Another graphical tool that we will use to talk about equivalent executions is the conflict graph, which is intuitively obtained from the action graph by merging matching pairs of vertices.

In this section we introduce greedy systems. Those systems aim at mimicking rendez-vous or synchronous communications by checking whether each execution can be rescheduled to an equivalent one where all receptions immediately follow their corresponding send.

In the remainder of this section, we show that deciding whether a system is greedy is feasible in polynomial time. The proof is in three steps: first, we give a graphical characterisation of the executions that are causally equivalent to greedy executions; second, we show that the non-greediness of a system is revealed by the existence of ‘bad’ executions of a certain shape, called borderline executions. Finally, we show that the graphical characterisation can be exploited to show the regularity of the language of borderline violations, from which we get the decidability of greediness.

Let $\Sigma=I\times\{!,!?\}\times\mathbb{V}$ denote the set of communications, and let $\Sigma_{\_}{?}=I\times\{?\}\times\mathbb{V}$ be the set of receive actions. Then a greedy execution can be represented by a word in $\Sigma^{*}$ and a borderline violation is represented by a word in $\Sigma^{*}\cdot\Sigma_{\_}{?}$. So now, we define two non-deterministic finite state automata over $\Sigma\cup\Sigma_{\_}{?}$: the first one accepts all greedy executions of a system, and the second one all borderline violations. We later explain how these automata are used to decide greediness.

From the computability of the two previous automata, we deduce the decidability of system greediness.

In this section we explore how to verify various safety properties of greedy systems in polynomial time. Since the reachability set of a greedy system is not regular, it is not obvious that regular safety properties are always decidable. We show that this problem actually is decidable, with a polynomial time complexity under mild assumptions. Then, we list a few regular safety properties that were also considered in other works, in particular for approaches based on session types [17, 9, 23].