Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Specifying and using a partitionable group communication service
Autore:
Fekete, A; Lynch, N; Shvartsman, A;
Indirizzi:
Univ Sydney, Basser Dept Comp Sci, Sidney, NSW 2006, Australia Univ Sydney Sidney NSW Australia 2006 mp Sci, Sidney, NSW 2006, Australia MIT, Comp Sci Lab, Cambridge, MA 02139 USA MIT Cambridge MA USA 02139MIT, Comp Sci Lab, Cambridge, MA 02139 USA Univ Connecticut, Dept Comp Sci & Engn, Storrs, CT 06269 USA Univ Connecticut Storrs CT USA 06269 omp Sci & Engn, Storrs, CT 06269 USA
Titolo Testata:
ACM TRANSACTIONS ON COMPUTER SYSTEMS
fascicolo: 2, volume: 19, anno: 2001,
pagine: 171 - 216
SICI:
0734-2071(200105)19:2<171:SAUAPG>2.0.ZU;2-C
Fonte:
ISI
Lingua:
ENG
Soggetto:
BACKWARD SIMULATIONS; SYSTEM; MULTICAST; PROTOCOL; TOTEM;
Keywords:
algorithms; design; performance; verification; group communication protocols; message-passing protocols; conditional performance analysis; total-order broadcast; composable building blocks; service specification; ordered broadcast; distributed algorithms;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
55
Recensione:
Indirizzi per estratti:
Indirizzo: Fekete, A Univ Sydney, Basser Dept Comp Sci, Madsen Bldg F09, Sidney, NSW 2006, Australia Univ Sydney Madsen Bldg F09 Sidney NSW Australia 2006 Australia
Citazione:
A. Fekete et al., "Specifying and using a partitionable group communication service", ACM T COMP, 19(2), 2001, pp. 171-216

Abstract

Group communication services are becoming accepted as effective building blocks for the construction of fault-tolerant distributed applications. Manyspecifications for group communication services have been proposed. However, there is still no agreement about what these specifications should say, especially in cases where the services are partitionable, i.e., where communication failures may lead to simultaneous creation of groups with disjointmemberships, such that each group is unaware of the existence of any othergroup. In this paper, we present a new, succinct specification for a view-oriented partitionable group communication service. The service associates each message with a particular view of the group membership. All send and receive events for a message occur within the associated view. The service provides a total order on the messages within each view, and each processor receives a prefix of this order. Our specification separates safety requirements from performance and fault-tolerance requirements. The safety requirements are expressed by an abstract, global state machine. To present the performance and fault-tolerance requirements, we include failure-status inputactions in the specification; we then give properties saying that consensus on the view and timely message delivery are guaranteed in an execution provided that the execution stabilizes to a situation in which the failure-status stops changing and corresponds to a consistently partitioned system. Because consensus is not required in every execution, the specification is not subject to the existing impossibility results for partitionable systems. Our specification has a simple implementation, based on the membership algorithm of Cristian and Schmuck. We show the utility of the specification byconstructing an ordered-broadcast application, using an algorithm (based on algorithms of Amir, Dolev, Keidar, and others) that reconciles information derived from different instantiations of the group. The application manages the view-change activity to build a shared sequence of messages, i.e., the per-view total orders of the group service are combined to give a universal total order. We prove the correctness and analyze the performance and fault-tolerance of the resulting application.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 06/04/20 alle ore 00:41:33