On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems

Guohong Cao; Mukesh Singhal

doi:10.1109/ICPP.1998.708461

On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems

Guohong Cao, Mukesh Singhal

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

49 Scopus citations

Abstract

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. R. Prakash and M. Singhal (1996) proposed the first coordinated checkpointing algorithm for mobile computing systems. However we showed that their algorithm may result in an inconsistency. In this paper, we prove a more general result about coordinated checkpointing: there does not exist a non-blocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on the proof, we propose an efficient algorithm for mobile computing systems, which forces only a minimum number of processes to take checkpoints and dramatically reduces the blocking time during the checkpointing process. Correctness proofs and performance analysis of the algorithm are provided.

Original language	English (US)
Title of host publication	Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998
Editors	Ten H. Lai
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	37-44
Number of pages	8
ISBN (Electronic)	0818686502
DOIs	https://doi.org/10.1109/ICPP.1998.708461
State	Published - 1998
Event	1998 International Conference on Parallel Processing, ICPP 1998 - Minneapolis, United States Duration: Aug 10 1998 → Aug 14 1998

Publication series

Name	Proceedings of the International Conference on Parallel Processing
ISSN (Print)	0190-3918

Other

Other	1998 International Conference on Parallel Processing, ICPP 1998
Country/Territory	United States
City	Minneapolis
Period	8/10/98 → 8/14/98

All Science Journal Classification (ASJC) codes

Software
General Mathematics
Hardware and Architecture

Access to Document

10.1109/ICPP.1998.708461

Cite this

Cao, G., & Singhal, M. (1998). On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems. In T. H. Lai (Ed.), Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998 (pp. 37-44). (Proceedings of the International Conference on Parallel Processing). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICPP.1998.708461

Cao, Guohong ; Singhal, Mukesh. / On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems. Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998. editor / Ten H. Lai. Institute of Electrical and Electronics Engineers Inc., 1998. pp. 37-44 (Proceedings of the International Conference on Parallel Processing).

@inproceedings{c4477fae992e413fa07b04a2661d0fd8,

title = "On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems",

abstract = "Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. R. Prakash and M. Singhal (1996) proposed the first coordinated checkpointing algorithm for mobile computing systems. However we showed that their algorithm may result in an inconsistency. In this paper, we prove a more general result about coordinated checkpointing: there does not exist a non-blocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on the proof, we propose an efficient algorithm for mobile computing systems, which forces only a minimum number of processes to take checkpoints and dramatically reduces the blocking time during the checkpointing process. Correctness proofs and performance analysis of the algorithm are provided.",

author = "Guohong Cao and Mukesh Singhal",

note = "Publisher Copyright: {\textcopyright} 1998 IEEE. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.; 1998 International Conference on Parallel Processing, ICPP 1998 ; Conference date: 10-08-1998 Through 14-08-1998",

year = "1998",

doi = "10.1109/ICPP.1998.708461",

language = "English (US)",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "37--44",

editor = "Lai, {Ten H.}",

booktitle = "Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998",

address = "United States",

}

Cao, G & Singhal, M 1998, On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems. in TH Lai (ed.), Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998. Proceedings of the International Conference on Parallel Processing, Institute of Electrical and Electronics Engineers Inc., pp. 37-44, 1998 International Conference on Parallel Processing, ICPP 1998, Minneapolis, United States, 8/10/98. https://doi.org/10.1109/ICPP.1998.708461

On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems. / Cao, Guohong; Singhal, Mukesh.
Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998. ed. / Ten H. Lai. Institute of Electrical and Electronics Engineers Inc., 1998. p. 37-44 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems

AU - Cao, Guohong

AU - Singhal, Mukesh

PY - 1998

Y1 - 1998

N2 - Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. R. Prakash and M. Singhal (1996) proposed the first coordinated checkpointing algorithm for mobile computing systems. However we showed that their algorithm may result in an inconsistency. In this paper, we prove a more general result about coordinated checkpointing: there does not exist a non-blocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on the proof, we propose an efficient algorithm for mobile computing systems, which forces only a minimum number of processes to take checkpoints and dramatically reduces the blocking time during the checkpointing process. Correctness proofs and performance analysis of the algorithm are provided.

AB - Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. R. Prakash and M. Singhal (1996) proposed the first coordinated checkpointing algorithm for mobile computing systems. However we showed that their algorithm may result in an inconsistency. In this paper, we prove a more general result about coordinated checkpointing: there does not exist a non-blocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on the proof, we propose an efficient algorithm for mobile computing systems, which forces only a minimum number of processes to take checkpoints and dramatically reduces the blocking time during the checkpointing process. Correctness proofs and performance analysis of the algorithm are provided.

UR - http://www.scopus.com/inward/record.url?scp=85043995232&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85043995232&partnerID=8YFLogxK

U2 - 10.1109/ICPP.1998.708461

DO - 10.1109/ICPP.1998.708461

M3 - Conference contribution

AN - SCOPUS:85043995232

T3 - Proceedings of the International Conference on Parallel Processing

SP - 37

EP - 44

BT - Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998

A2 - Lai, Ten H.

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1998 International Conference on Parallel Processing, ICPP 1998

Y2 - 10 August 1998 through 14 August 1998

ER -

Cao G, Singhal M. On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems. In Lai TH, editor, Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998. Institute of Electrical and Electronics Engineers Inc. 1998. p. 37-44. (Proceedings of the International Conference on Parallel Processing). doi: 10.1109/ICPP.1998.708461

On the impossibility of min-process non-blocking checkpointing and an efficient checkpointing algorithm for mobile computing systems

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this