Corona: a stabilizing deterministic message-passing skip list

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

Preview

PDF - Published Version Download (339kB) | Preview

Abstract

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.

Item Type:	Article (Journal)
Additional Information:	5251/33049. The same title appears in Lecture Notes in Scopus
Uncontrolled Keywords:	Message-passing
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	Dr. Rizal Mohd Nor
Date Deposited:	04 Dec 2013 09:29
Last Modified:	18 Dec 2015 21:50
URI:	http://irep.iium.edu.my/id/eprint/33049

Actions (login required)

View Item