Article

Relaxed determinism: making redundant execution on multiprocessors practical

Authors:

Jesse Pool,

Ian Sin Kwok Wong,

David LieAuthors Info & Claims

HOTOS'07: Proceedings of the 11th USENIX workshop on Hot topics in operating systems

Article No.: 5, Pages 1 - 6

Published: 07 May 2007 Publication History

Publisher Site

Abstract

Given that the majority of future processors will contain an abundance of execution cores, redundant execution can offer a promising method for increasing the availability and resilience against intrusions of computing systems. However, redundant execution systems rely on the premise that when external input is duplicated identically to a set of replicas executing the same program, the replicas will produce identical outputs unless they are compromised or experience an error. Unfortunately, threaded applications exhibit nondeterminism that breaks this premise and current redundant execution systems are unable to account for this non-determinism, especially on multiprocessors. In this paper, we introduce a method called relaxed determinism that is utilized by our system, called Replicant, to support redundant execution with reasonable performance while tolerating non-determinism.

References

[1]

{1} S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66-76, 1996.

Digital Library

Google Scholar

[2]

{2} D. Bernick, B. Bruckert, P. D. Vigna, D. Garcia, R. Jardine, J. Klecka, and J. Smullen. NonStop advanced architecture. In Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN), pages 12-21, June 2005.

Digital Library

Google Scholar

[3]

{3} A. L. Cox, K. Mohanram, and S. Rixner. Dependable ≠ unaffordable. In Proceedings of the Workshop on Architectural and System Support for Improving Software Dependability, pages 58-62, Oct. 2006.

Digital Library

Google Scholar

[4]

{4} B. Cox, D. Evans, A. Filipi, J. Rowanhill, W. Hu, J. Davidson, J. Knight, A. Nguyen-Tuong, and J. Hiser. N-Variant systems: A secretless framework for security through diversity. In Proceedings of the 15th USENIX Security Symposium, pages 105-120, Aug. 2006.

Digital Library

Google Scholar

[5]

{5} G. W. Dunlap, S. T. King, S. Cinar, M. A. Basrai, and P. M. Chen. ReVirt: Enabling intrusion analysis through virtual-machine logging and replay. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI), pages 211-224, Dec. 2002.

Digital Library

Google Scholar

[6]

{6} Intel Corp., 2007. http://www.intel.com/technology/magazine/computing/quad-core-1206.htm (Last accessed: 03/08/2007).

Google Scholar

[7]

{7} T. J. LeBlanc and J. M. Mellor-Crummey. Debugging parallel programs with instant replay. IEEE Transactions on Computers, 36(4):471-482, Apr. 1987.

Digital Library

Google Scholar

[8]

{8} S. M. Srinivasan, S. Kandula, C. R. Andrews, and Y. Zhou. Flashback: A lightweight extension for rollback and deterministic replay for software debugging. In Proceedings of the 2004 Annual Usenix Technical Conference, pages 29-44, June 2004.

Digital Library

Google Scholar

[9]

{9} A. Yumerefendi, B. Mickle, and L. Cox. TightLip: Keeping applications from spilling the beans. In Proceedings of the 4th Symposium on Networked Systems Design and Implementation (NSDI), Apr. 2007.

Digital Library

Google Scholar

Cited By

View all

Liu LTan HJiang SHan ZLi XHuang H(2019)Dependent task placement and scheduling with function configuration in edge computingProceedings of the International Symposium on Quality of Service10.1145/3326285.3329055(1-10)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3326285.3329055
Thomm IStilkerich MKapitza RLohmann DSchröder-Preikschat WWellings ARavn A(2011)Automated application of fault tolerance mechanisms in a component-based systemProceedings of the 9th International Workshop on Java Technologies for Real-Time and Embedded Systems10.1145/2043910.2043925(87-95)Online publication date: 26-Sep-2011
https://dl.acm.org/doi/10.1145/2043910.2043925
Liu TCurtsinger CBerger EWobber TDruschel P(2011)DthreadsProceedings of the Twenty-Third ACM Symposium on Operating Systems Principles10.1145/2043556.2043587(327-336)Online publication date: 23-Oct-2011
https://dl.acm.org/doi/10.1145/2043556.2043587
Show More Cited By

Index Terms

Recommendations

The case for determinism in database systems

Replication is a widely used method for achieving high availability in database systems. Due to the nondeterminism inherent in traditional concurrency control schemes, however, special care must be taken to ensure that replicas don't diverge. Log ...
Determinism at Standard-Library Level in TM-Based Applications

Deterministic execution of a multi-threaded application guarantees that threads access shared memory in the same order and the application gives the same output whenever it runs with the same input parameters. Determinism provides repeatability, which ...
Debug determinism: the sweet spot for replay-based debugging
HotOS'13: Proceedings of the 13th USENIX conference on Hot topics in operating systems

Deterministic replay tools offer a compelling approach to debugging hard-to-reproduce bugs. Recent work on relaxed-deterministic replay techniques shows that replay debugging with low in-production overhead is possible. However, despite considerable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

HOTOS'07: Proceedings of the 11th USENIX workshop on Hot topics in operating systems

May 2007

127 pages

Editor:
Galen Hunt
Microsoft Research

Publisher

USENIX Association

United States

Publication History

Published: 07 May 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
2
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

View all

Liu LTan HJiang SHan ZLi XHuang H(2019)Dependent task placement and scheduling with function configuration in edge computingProceedings of the International Symposium on Quality of Service10.1145/3326285.3329055(1-10)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3326285.3329055
Thomm IStilkerich MKapitza RLohmann DSchröder-Preikschat WWellings ARavn A(2011)Automated application of fault tolerance mechanisms in a component-based systemProceedings of the 9th International Workshop on Java Technologies for Real-Time and Embedded Systems10.1145/2043910.2043925(87-95)Online publication date: 26-Sep-2011
https://dl.acm.org/doi/10.1145/2043910.2043925
Liu TCurtsinger CBerger EWobber TDruschel P(2011)DthreadsProceedings of the Twenty-Third ACM Symposium on Operating Systems Principles10.1145/2043556.2043587(327-336)Online publication date: 23-Oct-2011
https://dl.acm.org/doi/10.1145/2043556.2043587
Bergan THunt NCeze LGribble SArpaci-Dusseau RChen B(2010)Deterministic process groups in dOSProceedings of the 9th USENIX conference on Operating systems design and implementation10.5555/1924943.1924956(177-191)Online publication date: 4-Oct-2010
https://dl.acm.org/doi/10.5555/1924943.1924956
Kapitza RSchunter MCachin CStengel KDistler TVerissimo PWeatherspoon H(2010)StoryboardProceedings of the Sixth international conference on Hot topics in system dependability10.5555/1924908.1924909(1-8)Online publication date: 3-Oct-2010
https://dl.acm.org/doi/10.5555/1924908.1924909
Roeder TSchneider F(2010)Proactive obfuscationACM Transactions on Computer Systems10.1145/1813654.181365528:2(1-54)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1813654.1813655
Altekar GStoica IMatthews JAnderson T(2009)ODRProceedings of the ACM SIGOPS 22nd symposium on Operating systems principles10.1145/1629575.1629594(193-206)Online publication date: 11-Oct-2009
https://dl.acm.org/doi/10.1145/1629575.1629594

Abstract

References

Cited By

Index Terms

Recommendations

The case for determinism in database systems

Determinism at Standard-Library Level in TM-Based Applications

Debug determinism: the sweet spot for replay-based debugging

Comments

Information

Published In

Sponsors

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations