Corona: a stabilizing deterministic message-passing skip list

We present Corona, a deterministic self-stabilizing algorithm for skip list construction in structured overlay networks. Corona operates in the low-atomicity message-passing asynchronous system model. Corona requires constant process memory space for its operation and, therefore, scales well. We pro...

Full description

Bibliographic Details
Main Authors:	Mohd. Nor, Rizal, Nesterenko, Mikhail, Scheideler, Christian
Format:	Article
Language:	English
Published:	Elsevier 2013
Subjects:	QA75 Electronic computers. Computer science
Online Access:	http://irep.iium.edu.my/33049/ http://irep.iium.edu.my/33049/ http://irep.iium.edu.my/33049/ http://irep.iium.edu.my/33049/1/1-s2.0-S0304397512008055-main.pdf

id	iium-33049
recordtype	eprints
spelling	iium-330492015-12-18T13:50:35Z http://irep.iium.edu.my/33049/ Corona: a stabilizing deterministic message-passing skip list Mohd. Nor, Rizal Nesterenko, Mikhail Scheideler, Christian QA75 Electronic computers. Computer science We present Corona, a deterministic self-stabilizing algorithm for skip list construction in structured overlay networks. Corona operates in the low-atomicity message-passing asynchronous system model. Corona requires constant process memory space for its operation and, therefore, scales well. We prove the general necessary conditions limiting the initial states from which a self-stabilizing structured overlay network in a message-passing system can be constructed. The conditions require that initial state information has to form a weakly connected graph and it should only contain identifiers that are present in the system. We formally describe Corona and rigorously prove that it stabilizes from an arbitrary initial state subject to the necessary conditions. We extend Corona to construct a skip graph. Elsevier 2013-11-11 Article PeerReviewed application/pdf en http://irep.iium.edu.my/33049/1/1-s2.0-S0304397512008055-main.pdf Mohd. Nor, Rizal and Nesterenko, Mikhail and Scheideler, Christian (2013) Corona: a stabilizing deterministic message-passing skip list. Theoretical Computer Science, 512. 119 - 129. ISSN 0304-3975 http://www.sciencedirect.com/science/article/pii/S0304397512008055 10.1016/j.tcs.2012.08.029
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
language	English
topic	QA75 Electronic computers. Computer science
spellingShingle	QA75 Electronic computers. Computer science Mohd. Nor, Rizal Nesterenko, Mikhail Scheideler, Christian Corona: a stabilizing deterministic message-passing skip list
description	We present Corona, a deterministic self-stabilizing algorithm for skip list construction in structured overlay networks. Corona operates in the low-atomicity message-passing asynchronous system model. Corona requires constant process memory space for its operation and, therefore, scales well. We prove the general necessary conditions limiting the initial states from which a self-stabilizing structured overlay network in a message-passing system can be constructed. The conditions require that initial state information has to form a weakly connected graph and it should only contain identifiers that are present in the system. We formally describe Corona and rigorously prove that it stabilizes from an arbitrary initial state subject to the necessary conditions. We extend Corona to construct a skip graph.
format	Article
author	Mohd. Nor, Rizal Nesterenko, Mikhail Scheideler, Christian
author_facet	Mohd. Nor, Rizal Nesterenko, Mikhail Scheideler, Christian
author_sort	Mohd. Nor, Rizal
title	Corona: a stabilizing deterministic message-passing skip list
title_short	Corona: a stabilizing deterministic message-passing skip list
title_full	Corona: a stabilizing deterministic message-passing skip list
title_fullStr	Corona: a stabilizing deterministic message-passing skip list
title_full_unstemmed	Corona: a stabilizing deterministic message-passing skip list
title_sort	corona: a stabilizing deterministic message-passing skip list
publisher	Elsevier
publishDate	2013
url	http://irep.iium.edu.my/33049/ http://irep.iium.edu.my/33049/ http://irep.iium.edu.my/33049/ http://irep.iium.edu.my/33049/1/1-s2.0-S0304397512008055-main.pdf
first_indexed	2023-09-18T20:47:44Z
last_indexed	2023-09-18T20:47:44Z
_version_	1777409787903868928

Corona: a stabilizing deterministic message-passing skip list

Similar Items