Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 20
ADVANCES IN PARALLEL AND VECTOR PROCESSING FOR STRUCTURAL MECHANICS
Edited by: B.H.V. Topping and M. Papadrakakis
Paper VI.1

An Efficient Algorithm for Crash Recovery in Parallel Systems using a Non-FIFO Channel: An Optimistic Approach

K.H. Lee and J.R. Kenevan

Department of Computer Science, Illinois Institute of Technology, Chicago, United States of America

Full Bibliographic Reference for this paper
K.H. Lee, J.R. Kenevan, "An Efficient Algorithm for Crash Recovery in Parallel Systems using a Non-FIFO Channel: An Optimistic Approach", in B.H.V. Topping, M. Papadrakakis, (Editors), "Advances in Parallel and Vector Processing for Structural Mechanics", Civil-Comp Press, Edinburgh, UK, pp 199-205, 1994. doi:10.4203/ccp.20.6.1
Abstract
This paper presents several recovery algorithms that is appropriate for concurrent programming or parallel processing in system for industry. Our algorithm uses vector clock and does not require channels to be FIFO. Maximum consistent state can be tracked using only global local time and it requires neither unique timestamp nor any index tables. The proposed algorithm consists of two phases: Independent rollback for forming rollback line and snapshot for forming consistent view of global state. Since all the existing algorithm used on Lamport logical clock, they can lost some information about the causality relation. Also, they implemented algorithm by FIFO channel. Our algorithm is a simpler and more generalized algorithm than existing ones: it does not require a state index table, a log table and a vector table. Our algorithm requires less memory: it does not need O(n) additional information for dependency tracking.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description