CFP last date
20 December 2024
Reseach Article

Rigorous Design of moving Sequencer Omission Tolerant Atomic Broadcast

by Prateek Srivastava, Prasun Chakrabarti, Avinash Panwar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 102 - Number 3
Year of Publication: 2014
Authors: Prateek Srivastava, Prasun Chakrabarti, Avinash Panwar
10.5120/17797-8608

Prateek Srivastava, Prasun Chakrabarti, Avinash Panwar . Rigorous Design of moving Sequencer Omission Tolerant Atomic Broadcast. International Journal of Computer Applications. 102, 3 ( September 2014), 27-33. DOI=10.5120/17797-8608

@article{ 10.5120/17797-8608,
author = { Prateek Srivastava, Prasun Chakrabarti, Avinash Panwar },
title = { Rigorous Design of moving Sequencer Omission Tolerant Atomic Broadcast },
journal = { International Journal of Computer Applications },
issue_date = { September 2014 },
volume = { 102 },
number = { 3 },
month = { September },
year = { 2014 },
issn = { 0975-8887 },
pages = { 27-33 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume102/number3/17797-8608/ },
doi = { 10.5120/17797-8608 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:32:10.875921+05:30
%A Prateek Srivastava
%A Prasun Chakrabarti
%A Avinash Panwar
%T Rigorous Design of moving Sequencer Omission Tolerant Atomic Broadcast
%J International Journal of Computer Applications
%@ 0975-8887
%V 102
%N 3
%P 27-33
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This article investigates a mechanism to tolerate omission failure in moving sequencer based atomic broadcast at distributed systems. Various mechanisms are already given for moving sequencer based atomic broadcast like RMP [1], DTP [2], Pin Wheel [3] and mechanism proposed by [4]. But none of these mechanisms are efficient to tolerate different failure. Scholarly observation is that, these algorithms can tolerate only crash failure but not capable to tolerate omission or byzantine failure. This work is an extension of [4]. This work proposes a mechanism to tolerate omission failure in moving sequencer based atomic broadcast. Hence this work is a refined version of [4]. This work relies on unicast broadcast hence it will introduce a very less number of messages in comparison to previous mechanisms [5]. B [6] has been used as formal technique for development of proposed model. B uses set theory as a modeling notation, refinements to represent system at different abstraction level. Pro B [7] has been used as model checker and animator for constraint based checking, to discover errors due to invariant violation and for deadlocks, thereby, validating the specifications.

References
  1. Jia, W. , Kaiser, J. , and Nett, E. 1996. RMP: Fault–Tolerant GroupCommunication. Micro, IEEE, Oxford, Clarendon, 16( 2) , 59 – 67.
  2. Kim, J. , and Kim C. 1997. A total ordering protocol using a dynamic token-passing scheme. Distributed System Engineering. 4(2), 87–95.
  3. Cristian, F. , Mishra, S. , and Alvarez, G. 1997. High performance asynchronous atomic broadcast. Distributed System Engineering 4(2), pp. 109-128.
  4. Srivastava, P. , Lakhtaria, K. , Panwar A. , and Jain, A. 2014. Rigorous design of moving sequencer crash tolerant atomic broadcast with unicast broadcast. IEEE International Conference on Recent Advances and Innovations in Engineering – ICRAIE, Rajasthan, India.
  5. D´efago, X. , Schiper, A. , and Urb´an, P. 2004. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv. 36(4), 372– 421.
  6. Abrial, J. , R. 1996. The B-book: assigning programs to meanings Cambridge University Press New York. USA, ISBN:0-521-49619-5.
  7. Leuschel, M. , Butler, M. 2003. Pro B: A model checker for B. In: Araki, K. , Gnesi, S. , Mandrioli, D. (eds. ) FME. Springer, Heidelberg, LNCS, 2805, 855-874.
  8. Ekwall, R. , and Schiper, A. 2011. A Fault-Tolerant Token-Based Atomic Broadcast Algorithm. Dependable and Secure Computing, IEEE Transactions. 8(5), 625–639.
  9. Hadzilacos, V. , and Toueg, S. 1993. Fault-Tolerant Broadcasts and Related Problems. Distributed systems (2nd Ed. ), ACM Press/Addison- Wesley Publishing Co. , New York, USA, 97-145.
  10. Lamport, L. , 1978. The Implementation of Reliable Distributed Multiprocess Systems. Computer Networks. 2(2), 95–114.
  11. Schneider. , and F. B. 1990. Implementing fault tolerant services using the state machine approach: a tutorial. ACM Computing Survey. 22(4), 299-319.
  12. Kaashoek, M. F. and Tanenbaum, A. S. 1996. An evaluation of the Amoeba group communication system. In Proceeding of 16th International Conference on Distributed Computing Systems (ICDCS-16). Hong Kong, 436–447.
  13. Armstrong, S. , Freier, A. , and Marzullo, K. , 1992. Multicast transport protocol. Network working group. RFC 1301, IETF.
  14. Carr, R. , 1985. The Tandem global update protocol. Tandem Systems Review. 74–85.
  15. Garcia-Molina, H. and Spauster, A. 1991. Ordered and reliable multicast Communication. ACM Trans. Comput. Syst. 9(3), 242–271.
  16. Jia, X. 1995. A total ordering multicast protocol using propagation trees. IEEE Trans. Parall. Distrib. Syst. 6, 617–627.
  17. Birman, K. P. , Schiper, A. , and Stephenson, P. 1991. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst. 9(3), 272–314.
  18. Navaratnam, S. , Chanson, S. T. , and Neufeld, G. W. 1988. Reliable group communication in distributed systems. In Proceeding of 8th International Conference on Distributed Computing Systems (ICDCS-8). San Jose, CA, USA, 439–446.
  19. Wilhelm, U. and Schiper, A. 1995. A hierarchy of totally ordered multicasts. In Proc. 14th Symp. on Reliable Distributed Systems (SRDS), Bad Neuenahr, Germany, 106–115.
  20. Reiter, M. K. 1994. Secure agreement protocols: Reliable and atomic group multicast in Rampart. In Proceeding of 2nd ACM Conference on Computer and Communications Security (CCS-2). 68–80.
  21. Reiter, M. K. 1996. Distributing trust with the Rampart toolkit. Communications of the ACM. 39(4), 71–74.
  22. Srivastava, P. ,Lakhtaria, K. , Jain, A. 2013. Rigorous design of moving sequencer atomic broadcast with unicast broadcast. In Proceeding of International Conference on Advances in computer science. Elsevier. 484-491.
  23. Cristian, F. , Aghili, H. , Strong, R. , and Volev, D. 1995. Atomic broadcast: From simple message diffusion to Byzantine agreement. IEEE, Proceeding of FTCS-25, 431.
  24. Berman, P. , and Bharali, A. A. 1993. Quick Atomic broadcast. Springer Berlin Heidelberg. LNCS. 725, 189-203.
  25. Le Lann, G. and Bres, G. 1991. Reliable atomic broadcast in distributed systems with omission faults. ACM Operating Systems Review. SIGOPS 25, 80–86.
  26. Chang, J. M. , and Maxemchuk, N. F. 1984. Reliable broadcast protocols. ACM Trans. Comput. Syst. 2(3), 251–273.
Index Terms

Computer Science
Information Sciences

Keywords

Broadcast Atomic Broadcast Total Order Unicast Sequencer Crash Omission Model Checking B formal method.