# On the k-synchronizability of systems

arXiv: https://arxiv.org/abs/1909.01627 · HTML: https://mlsanity.com/paper/1909.01627/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [A partial order view of message-passing communication models](https://mlsanity.com/paper/2210.13062/) (2022)

## Abstract (arXiv)

In this paper, we work on the notion of k-synchronizability: a system is k-synchronizable if any of its executions, up to reordering causally independent actions, can be divided into a succession of k-bounded interaction phases. We show two results (both for mailbox and peer-to-peer automata): first, the reachability problem is decidable for k-synchronizable systems; second, the membership problem (whether a given system is k-synchronizable) is decidable as well. Our proofs fix several important issues in previous attempts to prove these two results for mailbox automata.