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...
Saved in:
| Main Authors: | , , |
|---|---|
| 格式: | Article |
| 语言: | English |
| 出版: |
Elsevier
2013
|
| 主题: | |
| 在线阅读: | http://irep.iium.edu.my/33049/1/1-s2.0-S0304397512008055-main.pdf http://irep.iium.edu.my/33049/ http://www.sciencedirect.com/science/article/pii/S0304397512008055 |
| 标签: |
添加标签
没有标签, 成为第一个标记此记录!
|
| id |
my.iium.irep.33049 |
|---|---|
| record_format |
dspace |
| spelling |
my.iium.irep.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 REM 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 |
| institution |
Universiti Islam Antarabangsa Malaysia |
| building |
IIUM Library |
| collection |
Institutional Repository |
| continent |
Asia |
| country |
Malaysia |
| content_provider |
International Islamic University Malaysia |
| content_source |
IIUM Repository (IREP) |
| url_provider |
http://irep.iium.edu.my/ |
| 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/1/1-s2.0-S0304397512008055-main.pdf http://irep.iium.edu.my/33049/ http://www.sciencedirect.com/science/article/pii/S0304397512008055 |
| _version_ |
1643610353992466432 |
| score |
13.251813 |