Boundedness, hierarchy of fairness, and communication networks with delay
- 1 January 1989
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 26 (3-4) , 161-178
- https://doi.org/10.1080/00207168908803692
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
This publication has 11 references indexed in Scilit:
- Decidability questions for fairness in Petri netsPublished by Springer Nature ,2005
- Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-MachinesSIAM Journal on Computing, 1987
- Boundedness, empty channel detection, and synchronization for communicating finite automataTheoretical Computer Science, 1986
- An introduction to FIFO nets— monogeneous nets: A subclass of FIFO netsTheoretical Computer Science, 1985
- Priority Networks of Communicating Finite State MachinesSIAM Journal on Computing, 1985
- Fairness and conspiraciesInformation Processing Letters, 1984
- Unboundedness detection for a class of communicating finite-state machinesInformation Processing Letters, 1983
- On Communicating Finite-State MachinesJournal of the ACM, 1983
- Towards Analyzing and Synthesizing ProtocolsIEEE Transactions on Communications, 1980
- Formal Methods in Communication Protocol DesignIEEE Transactions on Communications, 1980