In this paper, we consider a scalable distributed-memory architecture for w
hich we propose a problem representation that assigns real-time tasks on th
e processing units of the architecture to maximize deadline compliance rate
. Based on the selected problem representation, we derive an algorithm that
dynamically schedules real-time tasks on the processors of the distributed
architecture. The algorithm uses a formula to generate the adequate schedu
ling time so that deadline loss due to scheduling overhead is minimized whi
le deadline compliance rate is being maximized. The technique we propose is
proved to be correct in the sense that the delivered solutions are not obs
olete, i.e. the assigned tasks to working processors are guaranteed to meet
their deadlines once executed. The correctness criterion is obtained based
on our technique to control the scheduling time. To evaluate the performan
ce of the algorithms that we propose, we provide a number of experiments th
rough a simulation study. We also propose an implementation of our algorith
ms in the context of scheduling real-time transactions on an Intel-Paragon
distributed-memory multiprocessor. The results of the conducted experiments
show interesting performance trade-offs among the candidate algorithms. (C
) 2000 Elsevier Science Inc. All rights reserved.