Welcome to Scholar Publishing Group

Distributed Processing System, 2022, 3(2); doi: 10.38007/DPS.2022.030207.

Fault-tolerant Scheduling Algorithm for Real-time Periodic Tasks in Heterogeneous Distributed Systems Based on Discrete Logarithmic Multi-signature


Loggesh Sainuni

Corresponding Author:
Loggesh Sainuni

Institute of IT & Computer Science, Afghanistan


Heterogeneous processors have high performance and low energy consumption, so they are widely used in various real-time(RT) systems, such as flight control systems. In a RT system, tasks that fail to meet deadlines can have catastrophic consequences. In order to avoid the situation that the system failure causes the task to miss the deadline, it is necessary to provide the system with fault tolerance. Fault-tolerant scheduling is an effective way to achieve system fault tolerance. There are two types of system faults: transient faults and permanent faults. The purpose of this paper is to study the fault-tolerant scheduling algorithm of RT periodic tasks in heterogeneous distributed systems based on discrete logarithmic multi-signature. This paper studies the transient fault tolerance problem. Existing transient fault-tolerant algorithms only consider fault-tolerance and ignore the RT nature of tasks. Therefore, considering both fault tolerance and time constraints, this paper proposes a transient fault-tolerant scheduling algorithm DB-FTSA based on time deadlines. According to the time deadline, calculate the number of fault-tolerant tasks that can provide fault tolerance, and give priority to fault tolerance of high-priority tasks. Configuration improves system reliability. At the same time, the algorithm fully considers the setup time and task execution time, making the algorithm closer to reality and more accurate. In order to overcome the problem that the traditional dynamic programming algorithm does not support a single type of sub-module, the algorithm uses active and passive sub-modules to achieve fault tolerance to reduce sub-module redundancy. It has been experimentally proven that, therefore, large tasks should be replaced with as many small tasks as possible to reduce the number of processors required.


Discrete Logarithmic Multi-signature, Heterogeneous Distributed System, RT Periodic Task, Fault-tolerant Scheduling Algorithm

Cite This Paper

Loggesh Sainuni. Fault-tolerant Scheduling Algorithm for Real-time Periodic Tasks in Heterogeneous Distributed Systems Based on Discrete Logarithmic Multi-signature. Distributed Processing System (2022), Vol. 3, Issue 2: 87-94. https://doi.org/10.38007/DPS.2022.030207.


[1] Roy A, Aydin H, Zhu D. Energy-aware primary/backup scheduling of periodic RT tasks on heterogeneous multicore systems. Sustainable Computing: Informatics and Systems, 2021, 29(2):100474. https://doi.org/10.1016/j.suscom.2020.100474

[2] Kada B, Kalla H. A Fault-Tolerant Scheduling Algorithm Based on Checkpointing and Redundancy for Distributed RT Systems. International journal of distributed systems and technologies, 2019, 10(3):58-75.

[3] Chauhan N K, Tyagi I, Kumar H, et al. Tasks Scheduling Through Hybrid Genetic Algorithm in RT System on Heterogeneous Environment. SN Computer Science, 2022, 3(1):1-13. https://doi.org/10.1007/s42979-021-00959-0

[4] Ghanavati S, Abawajy J, Izadi D. Automata-based Dynamic Fault Tolerant Task Scheduling Approach in Fog Computing. IEEE Transactions on Emerging Topics in Computing, 2020, PP(99):1-1.

[5] Baital K, Chakrabarti A. Dynamic Scheduling of Real-Time Tasks in Heterogeneous Multicore Systems. Embedded Systems Letters, IEEE, 2019, 11(1):29-32. https://doi.org/10.1109/LES.2018.2846666

[6] Bouyahia O, Abdallah A, Yazidi A, et al. Fault Tolerant Fuzzy Logic Control of a 6-Phase Induction Generator for Wind Turbine Energy Production. Electric Power Components and Systems, 2021, 49(8):756-766.

[7] Kumar N, Mayank J, Mondal A. Reliability Aware Energy Optimized Scheduling of Non-Preemptive Periodic Real-Time Tasks on Heterogeneous Multiprocessor System. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(4):871-885.

[8] Sharma R, Nitin N, Alshehri M A R, et al. Priority-based joint EDF–RM scheduling algorithm for individual real-time task on distributed systems. The Journal of Supercomputing, 2021, 77(1):890-908.

[9] Abohamama A S, El-Ghamry A, Hamouda E. Real-Time Task Scheduling Algorithm for IoT-Based Applications in the Cloud–Fog Environment. Journal of Network and Systems Management, 2022, 30(4):1-35. https://doi.org/10.1007/s10922-022-09664-6

[10] Senapati D, Sarkar A, Karfa C. PRESTO: A Penalty-aware Real-time Scheduler for Task Graphs on Heterogeneous Platforms. IEEE Transactions on Computers, 2021, PP(99):1-1.

[11] Younes A, Salah A B, Farag T, et al. Task Scheduling Algorithm For Heterogeneous Multi Processing Computing Systems. Journal of Theoretical and Applied Information Technology, 2019, 97(12):3477-3487.

[12] Zhuo R, Chen Y, Peng J, et al. A novel spectral-temporal Bayesian unmixing algorithm with spatial prior for Sentinel-2 time series. Remote Sensing Letters, 2022, 13(5):522-532.

[13] Lakhan A, Li X. Mobility and Fault Aware Adaptive Task Offloading in Heterogeneous Mobile Cloud Environments. ICST Transactions on Mobile Communications and Applications, 2019, 5(16):159947. https://doi.org/10.4108/eai.3-9-2019.159947

[14] Behera L. A fault-tolerant time-triggered scheduling algorithm of mixed-criticality systems. Computing, 2022, 104(3):577-599.

[15] Rao K P, Ramamurthy D V, Reddy N S, et al. Integrated simultaneous scheduling of machines, automated guided vehicles and tools in multi machine flexible manufacturing system using symbiotic organisms search algorithm. Journal of Industrial and Production Engineering, 2022, 39(4):317-339.

[16] Ren P, Hong J C. Research on Hybrid Real-Time System Scheduling Algorithm for Multiprocessor Environment. Journal of Physics: Conference Series, 2021, 1732(1):012069 (7pp).

[17] Hervé, Samba Aimé, Aurelien Y T, Leandre N N, et al. Improved Networked Iterative Learning Fault-tolerant Control Algorithm for Systems with Time-delays, Random Packet Losses, Limited Communication and Actuator Failure. International Journal of Control, Automation and Systems, 2022, 20(7):2425-2433. https://doi.org/10.1007/s12555-021-0179-9

[18] Bukhari S S H, Younus M U, Jaffri Z U A, et al. Scientific Workflow Makespan Minimization in Edge Multiple Service Providers Environment. Wireless Personal Communications, 2022, 125(4):3187-3203. https://doi.org/10.1007/s11277-022-09704-z