More Web Proxy on the site http://driver.im/

article

Maintaining data temporal consistency in distributed real-time systems

Authors:

Aloysius K. MokAuthors Info & Claims

Real-Time Systems, Volume 48, Issue 4

Pages 387 - 429

https://doi.org/10.1007/s11241-012-9150-4

Published: 01 July 2012 Publication History

Abstract

Previous works on maintaining temporal consistency of real-time data objects mainly focuses on real-time database systems in which the transmission delays (jitters) of update jobs are simply ignored. However, this assumption does not hold in distributed real-time systems where the jitters of the update jobs can be large and change unpredictably with time. In this paper, we examine the design problems when the More-Less (ML) approach (Xiong and Ramamritham in Proc. of the IEEE real-time systems symposium 1999; IEEE Trans Comput 53:567---583, 2004), known to be an efficient scheme for maintaining temporal consistency of real-time data objects, is applied in a distributed real-time system environment. We propose two new extensions based on ML, called Jitter-based More-Less (JB-ML) and Statistical Jitter-based More-Less (SJB-ML) to address the jitter problems. JB-ML assumes that in the system the jitter is a constant for each update task, and it provides a deterministic guarantee in temporal consistency of the real-time data objects. SJB-ML further relaxes this restriction and provides a statistical guarantee based on the given QoS requirements of the real-time data objects. We demonstrate through extensive simulation experiments that both JB-ML and SJB-ML are effective approaches and they significantly outperform ML in terms of improving schedulability.

References

[1]

Ahmed QN, Vrbsky SV (2000) Triggered updates for temporal consistency in real-time databases. Real-Time Syst 19(3):209-243.

Digital Library

[2]

Amirijoo M, Hansson J, Son SH, Member S (2006) Specification and management of QoS in real-time databases supporting imprecise computations. IEEE Trans Comput, 304-319.

[3]

Bernstein P, Hadzilacos V, Goodman N (1987) Concurrency Control and Recovery in Database Systems, vol 370. Addison-wesley, New York.

[4]

Burns A, Tindell K, Wellings AJ (1995) Effective analysis for engineering real-time fixed priority schedulers. IEEE Trans Softw Eng 21:475-480.

Digital Library

[5]

Di Natale M, Stankovic JA (1994) Dynamic end-to-end guarantees in distributed real-time systems. In: Proc. of the IEEE real-time systems symposium, pp 216-227.

[6]

Golab L, Johnson T, Shkapenyuk V (2009) Scheduling updates in a real-time stream warehouse. In: Proc. of the IEEE international conference on data engineering, pp 1207-1210.

[7]

Gustafsson T, Hansson J (2004) Data management in real-time systems: a case of on-demand updates in vehicle control systems. In: Proc. of the IEEE real-time and embedded technology and applications symposium, pp 182-191.

[8]

Han S, Chen D, Xiong M, Mok AK (2008) A schedulability analysis of deferrable scheduling using patterns. In: Proc. of the euromicro conference on real-time systems.

[9]

Han S, Chen D, Xiong M, Mok AK (2009) Online scheduling switch for maintaining data freshness in flexible real-time systems. In: Proc of the IEEE real-time systems symposium.

[10]

Han S, Zhu X, Mok AK, Chen D, Nixon M (2011) Reliable and real-time communication in industrial wireless mesh networks. In: Proc of the IEEE real-time and embedded technology and applications symposium.

[11]

Ho SJ, Kuo TW, Mok AK (1997) Similarity-based load adjustment for real-time data-intensive applications. In: Proc. of IEEE real-time system symposium, pp 144-153.

[12]

Kang KD, Son SH, Stankovic JA (2004) Managing deadline miss ratio and sensor data freshness in realtime databases. IEEE Trans Knowl Data Eng 16(10).

[13]

Kuo TW, Mok AK (1993) Ssp: a semantics-based protocol for real-time data access. In: Proc of the IEEE real-time systems symposium, pp 76-86.

[14]

Kuo TW, Mok AK (1994) Using data similarity to achieve synchronization for free. In: 11th IEEE workshop on real-time operating systems and software, pp 112-116.

[15]

Labrinidis A, Roussopoulos N (2001) Update propagation strategies for improving the quality of data on the web. In: Proc of the international conference on very large databases, pp 391-400.

[16]

Lam KY, Kuo TW (2001) Real-time database systems: architecture and techniques. Kluwer Academic Amsterdam.

[17]

Lam KY, Xiong M, Liang B, Guo Y (2004) Statistical quality of service guarantee for temporal consistency of real-time data objects. In: Proc of the IEEE real-time systems symposium.

[18]

Leung J, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic real-time tasks. Perform Eval 2:237-250.

[19]

Li H, Mason L (2007) Estimation and simulation of network delay traces for voip in service overlay network. In: Proc of the international symposium on signals, systems and electronics, pp 423-425.

[20]

Li J, Chen JJ, Xiong M, Li G (2011) Workload-aware partitioning for maintaining temporal consistency upon multiprocessor platforms. In: Real-time systems symposium.

[21]

Li M, Liu Y (2009) Underground coal mine monitoring with wireless sensor networks. ACM Trans Sens Netw 5(2):1-29.

Digital Library

[22]

Locke D (1997) Real-time databases: real-world requirements. In: Bestavros A, Lin KJ, Son SH (eds) Real-time database systems: issues and applications. Kluwer Academic, Amsterdam pp 83-91.

[23]

Lu C, Wang X, Koutsoukos X (2005) Feedback utilization control in distributed real-time systems with end-to-end tasks. IEEE Trans Parallel Distrib Syst, 550-561.

[24]

Papageorgiou M, Diakaki C, Dinopoulou V, Kotsialos A, Wang Y (2005) Review of road traffic control strategies. Proc IEEE 91(12):2043-2067.

[25]

Qu H, Labrinidis A (2007) Preference-aware query and update scheduling in web-databases. In: Proc of the IEEE international conference on data engineering, pp 356-365.

[26]

Ramamritham K (1993) Real-time databases. Distrib Parallel Databases 1:199-226.

Digital Library

[27]

Ramamritham K, Son SH, Dipippo LC (2004) Real-time databases and data services. Real-Time Syst 28(2):179-215.

Digital Library

[28]

Saifullah A, Xu Y, Lu C, Chen Y (2010) Real-time scheduling for wirelesshart networks. In: Real-time systems symposium.

[29]

Saifullah A, Xu Y, Lu C, Chen Y (2011) End-to-end delay analysis for fixed priority scheduling in wirelesshart networks. Proc. of the IEEE Real-Time and Embedded Technology and Applications Symposium.

[30]

Sha L, Rajkumar R, Lehoczky JP (1990) Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans Comput 39(9):1175-1185.

Digital Library

[31]

Shanker U, Misra M, Sarje AK (2008) Distributed real time database systems: background and literature review. Distrib Parallel Databases 23(2):127-149.

Digital Library

[32]

Song J, Han S, Mok AK, Chen D, Lucas M, Nixon M, Pratt W (2008) WirelessHART: applying wireless technology in real-time industrial process control. In: Proc. of the IEEE real-time and embedded technology and applications symposium, pp 377-386.

[33]

Tan R, Xing G, Liu B, Wang J (2009) Impact of data fusion on real-time detection in sensor networks. In: Proc. of the IEEE real-time systems symposium, pp 323-332.

[34]

Xiang J, Li GH, Xu HJ, Du XK (2008) Data freshness guarantee and scheduling of update transactions in RTMDBS. In: Proc of the international conference on wireless communications, networking and mobile computing, pp 1-4.

[35]

Xiong M, Ramamritham K (1999) Deriving deadlines and periods for real-time update transactions. In: Proc of the IEEE real-time systems symposium.

[36]

Xiong M, Ramamritham K (2004) Deriving deadlines and periods for real-time update transactions. IEEE Trans Comput 53:567-583.

Digital Library

[37]

Xiong M, Han S, Lam KY (2005) A deferrable scheduling algorithm for real-time transactions maintaining data freshness. In: Proc of the IEEE real-time systems symposium, pp 27-37.

[38]

Xiong M, Han S, Chen D (2006) Deferrable scheduling for temporal consistency: schedulability analysis and overhead reduction. In: Proc of the IEEE international conference on embedded and real-time computing systems and applications.

[39]

Xiong M, Han S, Lam KY, Chen D (2008a) Deferrable scheduling for maintaining real-time data freshness: algorithms, analysis, and results. IEEE Trans Comput.

[40]

Xiong M, Wang Q, Ramamritham K (2008b) On earliest deadline first scheduling for temporal consistency maintenance. Real-Time Syst 40(2):208-237.

Digital Library

[41]

Xiong M, Han S, Chen D, Lam KY, Feng S (2010) Desh: overhead reduction algorithms for deferrable scheduling. Real-Time Syst 44(1-3):1-25.

Digital Library

[42]

Zuhily A, Burns A (2007) Optimal (d-j)-monotonic priority assignment. Inf Proces Lett 103(6):247-250.

Digital Library

Cited By

Zhou QCai SLi JGao YQu ZJin T(2024)Deadline and Period Assignment for Guaranteeing Timely Response of the Cyber-Physical SystemACM Transactions on Design Automation of Electronic Systems10.1145/368904830:1(1-26)Online publication date: 24-Aug-2024
https://dl.acm.org/doi/10.1145/3689048
Bai TLi ZFan BLiao J(2022)Maintaining temporal validity of real-time data in component-based systemsComputing10.1007/s00607-022-01089-y104:11(2347-2374)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s00607-022-01089-y
Zhou QLi GChen QLi J(2021)Guaranteeing Timely Response to Changes of Monitored Objects by Assigning Deadlines and Periods to TasksACM Transactions on Embedded Computing Systems10.1145/347702720:5s(1-22)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3477027
Show More Cited By

Maintaining data temporal consistency in distributed real-time systems

Recommendations

Triggered Updates for Temporal Consistency in Real-TimeDatabases

A real-time database system has temporal consistency constraints in addition to timing constraints. The timing constraints require a transaction to be completed by a specified deadline, and the temporal consistency constraints require that temporal data ...
Maintaining Temporal Consistency of Discrete Objects in Soft Real-Time Database Systems

A real-time database system contains base data items which record and model a physical, real-world environment. For better decision support, base data items are summarized and correlated to derive views. These base data and views are accessed by ...
Maintaining Temporal Consistency in Real-Time Database Systems
ICCIT '07: Proceedings of the 2007 International Conference on Convergence Information Technology

A real-time database system usually requires maintaining a large amount of temporal data objects which record and model a physical, real-world environment. These temporal data objects are accessed by application transactions to generate the ultimate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Real-Time Systems

Real-Time Systems Volume 48, Issue 4

July 2012

140 pages

ISSN:0922-6443

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 July 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhou QCai SLi JGao YQu ZJin T(2024)Deadline and Period Assignment for Guaranteeing Timely Response of the Cyber-Physical SystemACM Transactions on Design Automation of Electronic Systems10.1145/368904830:1(1-26)Online publication date: 24-Aug-2024
https://dl.acm.org/doi/10.1145/3689048
Bai TLi ZFan BLiao J(2022)Maintaining temporal validity of real-time data in component-based systemsComputing10.1007/s00607-022-01089-y104:11(2347-2374)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s00607-022-01089-y
Zhou QLi GChen QLi J(2021)Guaranteeing Timely Response to Changes of Monitored Objects by Assigning Deadlines and Periods to TasksACM Transactions on Embedded Computing Systems10.1145/347702720:5s(1-22)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3477027
Bai LShao ZLin ZCheng S(2017)Fixing inconsistencies of fuzzy spatiotemporal XML dataApplied Intelligence10.5555/3110563.311058447:1(257-275)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.5555/3110563.3110584
Li GDeng CLi JZhou QWei W(2017)Deadline and Period Assignment for Update Transactions in Co-Scheduling EnvironmentIEEE Transactions on Computers10.1109/TC.2016.264520566:7(1119-1131)Online publication date: 7-Jun-2017
https://dl.acm.org/doi/10.1109/TC.2016.2645205
Park SKim JFox G(2014)Effective real-time scheduling algorithm for cyber physical systems societyFuture Generation Computer Systems10.5555/2748143.274836332:C(253-259)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.5555/2748143.2748363

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents