Precedence constraints in hard real-time distributed systems

Hard real-time multitask-multiprocessor systems are one of the more important species of the taxonomic genus of distributed systems. The assignment of m preemptible periodic tasks to be executed in a set of n processors (interconnected through a communications network) is a NP-complete problem that must meet several constraints: time, allocation, resources, communication and precedence. The first three are processor-dependent and the fourth is network-dependent, but all of them can be verified as the assignment process goes on. Precedence constraints, instead, can be best verified when a tentative assignment, meeting the first four constraints, is obtained. In this paper, a formally proved method is presented to validate tentative assignments. In order to solve the problem of jitter in data arrivals, timed release counters are proposed