TY - CHAP
T1 - Long-lived Rambo
T2 - Trading knowledge for communication
AU - Georgiou, Chryssis
AU - Musial, Peter M.
AU - Shvartsman, Alexander A.
N1 - Funding Information:
IThis work is supported in part by the NSF Grants 9988304, 0121277, and 0311368, and by the NSF CAREER Award 9984778. ∗Corresponding author at: Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06278, USA. E-mail address: aas@cse.uconn.edu (A.A. Shvartsman).
PY - 2004
Y1 - 2004
N2 - Shareable data services providing consistency guarantees, such as atomicity (linearizability), make building distributed systems easier. However, combining linearizability with efficiency in practical algorithms is difficult. A reconfigurable linearizable data service, called RAMBO, was developed by Lynch and Shvartsman. This service guarantees consistency under dynamic conditions involving asynchrony, message loss, node crashes, and new node arrivals. The specification of the original algorithm is given at an abstract level aimed at concise presentation and formal reasoning about correctness. The algorithm propagates information by means of gossip messages. If the service is in use for a long time, the size and the number of gossip messages may grow without bound. This paper presents a consistent data service for long-lived objects that improves on RAMBO in two ways: it includes an incremental communication protocol and a leave service. The new protocol takes advantage of the local knowledge, and carefully manages the size of messages by removing redundant information, while the leave service allows the nodes to leave the system gracefully. The new algorithm is formally proved correct by forward simulation using levels of abstraction. An experimental implementation of the system was developed for networks-of-workstations. The paper also includes analytical and preliminary empirical results that illustrate the advantages of the new algorithm.
AB - Shareable data services providing consistency guarantees, such as atomicity (linearizability), make building distributed systems easier. However, combining linearizability with efficiency in practical algorithms is difficult. A reconfigurable linearizable data service, called RAMBO, was developed by Lynch and Shvartsman. This service guarantees consistency under dynamic conditions involving asynchrony, message loss, node crashes, and new node arrivals. The specification of the original algorithm is given at an abstract level aimed at concise presentation and formal reasoning about correctness. The algorithm propagates information by means of gossip messages. If the service is in use for a long time, the size and the number of gossip messages may grow without bound. This paper presents a consistent data service for long-lived objects that improves on RAMBO in two ways: it includes an incremental communication protocol and a leave service. The new protocol takes advantage of the local knowledge, and carefully manages the size of messages by removing redundant information, while the leave service allows the nodes to leave the system gracefully. The new algorithm is formally proved correct by forward simulation using levels of abstraction. An experimental implementation of the system was developed for networks-of-workstations. The paper also includes analytical and preliminary empirical results that illustrate the advantages of the new algorithm.
UR - http://www.scopus.com/inward/record.url?scp=35048862873&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048862873&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-27796-5_17
DO - 10.1007/978-3-540-27796-5_17
M3 - Chapter
AN - SCOPUS:35048862873
SN - 3540222308
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 196
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Kralovic, Rastislav
A2 - Sykora, Ondrej
PB - Springer Verlag
ER -