The Relationship Between Multiway and Two-Way Fair Merges

Abstract

In the context of communicating systems of autonomous processes, we study two kinds of processes - a two-way fair merge, that interleaves two possibly infinite sequences into one, and a multiway fair merge, that interleaves more than two possibly infinite sequences into one. We describe two constructions. The first one shows how the effect of any arbitrary number of two-way fair merges in a finite network can be exactly obtained by a single multiway fair merge and some determinate processes. The second one shows how the effect of a single multiway fair merge with any number of input channels can be exactly obtained by a finite network of two-way fair merges.