Boundedness, hierarchy of fairness, and communication networks with delay

Abstract

In this paper, we consider networks of communicating finite-state machines (CFSMs) with a delay-related fairness (T-fairness) constant imposed on all computations. The notion of T-fairness, in a sense, allows us to measure the degree of synchronization of parallel systems “quantitatively”. Based on the value of T, we define a hierarchy of unbounded networks. We are able to show that, in general, the hierarchy is infinite. However, if we restrict ourselves to networks of 2 machines, the hierarchy collapses all the way to the second level. We also derive the complexity result of the boundedness problem for CFSM networks with respect to T-fairness.

Keywords:

• Boundedness problem
• communicating finite-state machines
• complexity
• fairness
• Petri nets

C.R. Categories:

• C.2.2 [Computer-Communication Networks]
• F.1.1 [Computation by Abstract Devices]