A Robust Causal Order Protocol
Resumo
This paper presents a robust causal order protocol implemented for the BCG platform (Reliable Group Communication Base) developed at LaSiD/UFBA (Distributed System Laboratory at UFBA). It was designed using a symmetric message recovery approach in which any process of the group can detect and retransmit missing messages providing a reliable message recovery mechanism. Its algorithm, based on certain properties and structures of the BCG, makes the proposed protocol more flexible than similar protocols published to date. Data collected from experiments are also reported.
Palavras-chave:
robust network protocols, message recovering, group communication protocols, causal ordering
Referências
G. A. Alvarez, F. Cristian and S. Mishra. On-Demand Asynchronous Atomic Broadcast. 5th IFIP Working Conf. on Dependable Computing for Critical Applications, 1995.
K. Birman, T. A. Joseph. Reliable Communication in the Presence of Failures. ACM TDCS, (5,1). pp. 47-76, 1987.
Barcellos, A. M. P. PRMP: A Scaleable Polling-based Reliable Multicast Protocol. Ph. D. Thesis. Newcastle upon Tyne, September 1998.
R. Baldoni, A. Mostefaoui and M. Raynal, Causal Deliveries in Unreliable Networks with Real-Time Delivery Constraints. Technical Report 2427, INRIA. December 1994.
K. Birman, A. Schiper and P. Stephenson. Lighweight Causal and Atomic Group Multicast. ACM Transaction on Computing Systems, (9,3), pp. 272-314, August 1991.
F. J. N. Cosquer and P. Veríssimo. The Impact of Group Communication Paradigms on Groupware Support. Proc. of the 5th Workshop on Future Trends of Distributed Computing Systems. Korea. 1995.
D. Cheriton, W. Zwaenepoel. Distributed Process Groups in V Kernel. ACM TOCS, (3,2), pp. 97-107, 1985.
P. O. Ezhilchelvan. R. A Macêdo and S. K. Shrivastava. Newtop: A Fault-Tolerant Group Communication Protocol. Proc. of the 15th International Conference on Distributed Computing Systems, IEEE Computer Society, pp. 296-306, Canadá, June 1995.
S. Floyd, V. Jacobson. S. McCanne, C. Liu, L. Zhang. A Reliable Multicast Framework for Light-Weight Sessions and Application Level Framing. ACM SIGCOMM'95. Cambridge, USA, August 1995.
F. G. P. Greve and R. J. A. Macêdo. The BCG Membership Service Performance Analysis. In Proc. of XVI Simpósio Brasileiro de Redes de Computadores. Rio de Janeiro, May 1998.
L. Lamport. Time, Clocks and Ordering of Events in a Distributed System. CACM, (21, 7), pp. 558-265, July 1978,.
G. M. de A. Lima and R. J. A. Macêdo. Avaliação de Desempenho do protocolo BCGcausal Technical Report, RTI-003/97. November 1997.
G. M. de A. Lima and R. J. A. Macêdo. Avaliação de Desempenho de Protocolos de Ordenação Causal para Comunicação em Grupo. XXV Conferencia Latinoamericana de Informática, CLEI99, 1999.
R. J. de A. Macêdo. Fault Toleram Group Communication Protocols for Asynchronous Systems. Ph.D. Thesis, Computing Science Department, University of Newcastle upon Tyne, UK, 1994.
R. J. de A. Macêdo. Causal Order Protocols for Group Communication. SBRC95, Belo Horizonte-MG. pp. 265-283, May 1995.
R. J. A. Macêdo and P. D. Ezhilchelvan, S. K. Shrivastava. Buffer Overflow A voidance Techniques for Groups Communication Protocols. SBRC96, pp. 633-652, Fortaleza-CE, May 1996.
R. J. A. Macêdo and P. D. Ezhilchelvan, S. K. Shrivastava. Modeling Group Communication Using Causal Clocks. 5th European Workshop on Dependable Computing, Lisbon, February, 1993.
K. Miller, K. Robertson, A. Tweedly and M. White. Starbus Multicast File Transfer Prococol (MFTP) Specification. Internet draft (expired), January 1997.
L. L. Peterson, N. C. Buchholz and R. D. Schlichting. Preserving and Using Concext Informacion in Interprocess Comunication. ACM Transaction on Computing Systems. (7, 3), pp. 2 17-246, August 1989.
S. Paul, K. Sabnani. J. Lin and S. Bhattacharryya. Reliable Multicast Transport Protocol (RMTP). IEEE Journal on Selected Arcas in Communications, Vol. 13, No. 3, April 1997.
R. Renesse, K. Birman and S. Maffeis. HORUS, A Flexible Group Communication System. Communication of the ACM, April 1996.
P. Veríssimo, L. Rodrigues and Werner Vogels. Group Orientation: a Paradigm for Modem Distributed Systems. ESPRIT Basic Research Project First Year Report, volume 1, October 1993.
R. Yavatkar, J. Griffioen and M. Sudan. A Reliable Dissemination for Interaccive Collaborative Applications. ACM Multimedia, 1995.
K. Birman, T. A. Joseph. Reliable Communication in the Presence of Failures. ACM TDCS, (5,1). pp. 47-76, 1987.
Barcellos, A. M. P. PRMP: A Scaleable Polling-based Reliable Multicast Protocol. Ph. D. Thesis. Newcastle upon Tyne, September 1998.
R. Baldoni, A. Mostefaoui and M. Raynal, Causal Deliveries in Unreliable Networks with Real-Time Delivery Constraints. Technical Report 2427, INRIA. December 1994.
K. Birman, A. Schiper and P. Stephenson. Lighweight Causal and Atomic Group Multicast. ACM Transaction on Computing Systems, (9,3), pp. 272-314, August 1991.
F. J. N. Cosquer and P. Veríssimo. The Impact of Group Communication Paradigms on Groupware Support. Proc. of the 5th Workshop on Future Trends of Distributed Computing Systems. Korea. 1995.
D. Cheriton, W. Zwaenepoel. Distributed Process Groups in V Kernel. ACM TOCS, (3,2), pp. 97-107, 1985.
P. O. Ezhilchelvan. R. A Macêdo and S. K. Shrivastava. Newtop: A Fault-Tolerant Group Communication Protocol. Proc. of the 15th International Conference on Distributed Computing Systems, IEEE Computer Society, pp. 296-306, Canadá, June 1995.
S. Floyd, V. Jacobson. S. McCanne, C. Liu, L. Zhang. A Reliable Multicast Framework for Light-Weight Sessions and Application Level Framing. ACM SIGCOMM'95. Cambridge, USA, August 1995.
F. G. P. Greve and R. J. A. Macêdo. The BCG Membership Service Performance Analysis. In Proc. of XVI Simpósio Brasileiro de Redes de Computadores. Rio de Janeiro, May 1998.
L. Lamport. Time, Clocks and Ordering of Events in a Distributed System. CACM, (21, 7), pp. 558-265, July 1978,.
G. M. de A. Lima and R. J. A. Macêdo. Avaliação de Desempenho do protocolo BCGcausal Technical Report, RTI-003/97. November 1997.
G. M. de A. Lima and R. J. A. Macêdo. Avaliação de Desempenho de Protocolos de Ordenação Causal para Comunicação em Grupo. XXV Conferencia Latinoamericana de Informática, CLEI99, 1999.
R. J. de A. Macêdo. Fault Toleram Group Communication Protocols for Asynchronous Systems. Ph.D. Thesis, Computing Science Department, University of Newcastle upon Tyne, UK, 1994.
R. J. de A. Macêdo. Causal Order Protocols for Group Communication. SBRC95, Belo Horizonte-MG. pp. 265-283, May 1995.
R. J. A. Macêdo and P. D. Ezhilchelvan, S. K. Shrivastava. Buffer Overflow A voidance Techniques for Groups Communication Protocols. SBRC96, pp. 633-652, Fortaleza-CE, May 1996.
R. J. A. Macêdo and P. D. Ezhilchelvan, S. K. Shrivastava. Modeling Group Communication Using Causal Clocks. 5th European Workshop on Dependable Computing, Lisbon, February, 1993.
K. Miller, K. Robertson, A. Tweedly and M. White. Starbus Multicast File Transfer Prococol (MFTP) Specification. Internet draft (expired), January 1997.
L. L. Peterson, N. C. Buchholz and R. D. Schlichting. Preserving and Using Concext Informacion in Interprocess Comunication. ACM Transaction on Computing Systems. (7, 3), pp. 2 17-246, August 1989.
S. Paul, K. Sabnani. J. Lin and S. Bhattacharryya. Reliable Multicast Transport Protocol (RMTP). IEEE Journal on Selected Arcas in Communications, Vol. 13, No. 3, April 1997.
R. Renesse, K. Birman and S. Maffeis. HORUS, A Flexible Group Communication System. Communication of the ACM, April 1996.
P. Veríssimo, L. Rodrigues and Werner Vogels. Group Orientation: a Paradigm for Modem Distributed Systems. ESPRIT Basic Research Project First Year Report, volume 1, October 1993.
R. Yavatkar, J. Griffioen and M. Sudan. A Reliable Dissemination for Interaccive Collaborative Applications. ACM Multimedia, 1995.
Publicado
29/09/1999
Como Citar
LIMA, George Marconi de A.; MACÊDO, Raimundo J. de A..
A Robust Causal Order Protocol. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 11. , 1999, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1999
.
p. 205-212.
DOI: https://doi.org/10.5753/sbac-pad.1999.19791.
