NDLI: Design of multi-invariant data structures for robust shared accesses in multiprocessor systems

Please wait, while we are loading the content...

Design of multi-invariant data structures for robust shared accesses in multiprocessor systems

Content Provider	IEEE Xplore Digital Library
Author	I-Ling Yen Bastani, F.B. Taylor, D.J.
Copyright Year	1976
Abstract	Multiprocessor systems are widely used in many application programs to enhance system reliability and performance. However, reliability does not come naturally with multiple processors. We develop a multi-invariant data structure approach to ensure efficient and robust access to shared data structures in multiprocessor systems. Essentially, the data structure is designed to satisfy two invariants, a strong invariant, and a weak invariant. The system operates at its peak performance when the strong invariant is true. The system will operate correctly even when only the weak invariant is true, though perhaps at a lower performance level. The design ensures that the weak invariant will always be true in spite of fail-stop processor failures during the execution. By allowing the system to converge to a state satisfying only the weak invariant, the overhead for incorporating fault tolerance can be reduced. We present the basic idea of multi-invariant data structures. We also develop design rules that systematically convert fault-intolerant data abstractions into corresponding fault-tolerant versions. In this transformation, we augment the data structure and access algorithms to ensure that the system always converges to the weak invariant, even in the presence of fail-stop processor failures. We also design methods for the detection of integrity violations and for restoring the strong invariant. Two data structures, namely binary search tree and double-linked list, are used to illustrate the concept of multi-invariant data structures.
Sponsorship	IEEE Computer Society Technical Council on Software Engineering Association for Computing Machinery (ACM) IEEE Computer Society
Starting Page	193
Ending Page	207
Page Count	15
File Size	276869
File Format	PDF
ISSN	00985589
Volume Number	27
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-03-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Data structures Robustness Multiprocessing systems Fault tolerant systems Protocols Reliability Tree data structures Intelligent robots Concurrent computing System performance
Content Type	Text
Resource Type	Article
Subject	Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A fault-tolerant mapping scheme for a configurable multiprocessor system

Fault tolerant algorithms for broadcasting on the star graph network

Graceful degradation in algorithm-based fault tolerant multiprocessor systems

Intermittent fault diagnosis in multiprocessor systems

Implementing Fault-Tolerant Distributed Objects

A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh

Design tradeoffs for process scheduling in shared memory multiprocessor systems

Sequoia: a fault-tolerant tightly coupled multiprocessor for transaction processing

Realizing fault-tolerant interconnection networks via chaining

Design of multi-invariant data structures for robust shared accesses in multiprocessor systems

Similar Documents

A fault-tolerant mapping scheme for a configurable multiprocessor system

Fault tolerant algorithms for broadcasting on the star graph network

Graceful degradation in algorithm-based fault tolerant multiprocessor systems

Intermittent fault diagnosis in multiprocessor systems

Implementing Fault-Tolerant Distributed Objects

A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh

Design tradeoffs for process scheduling in shared memory multiprocessor systems

Sequoia: a fault-tolerant tightly coupled multiprocessor for transaction processing

Realizing fault-tolerant interconnection networks via chaining

Design of multi-invariant data structures for robust shared accesses in multiprocessor systems