An atomic commit protocol can cause long-term locking of databases if the coordinator crashes or becomes disconnected from the network. In this paper we describe how to eliminate the coordinator. This decentralized, cooperative atomic commit protocol piggybacks transaction statuses of all transaction participants onto tokens which are passed among the participants. Each participant uses the information in the tokens to make a decision of when to go to the next state of a three-phase commit protocol. Transactions can progress to ensure a uniform agreement on success or failure, even if the network is partitioned or nodes temporarily crash. 1. Introduction 1.1. Network Computing Network-based computing has several programming frameworks, such as peer-to-peer (P2P), grid, and web service computing [1]. For applications which involve many companies or individual users with their own databases (e.g., network supply chain or distributed health-care monitoring), the P2P approach seems to be a natural infrastructure. Each company or user can set the security on their local databases and decide which data to share with other members of the distributed application, based on an authenticated query sender (i.e., application executor). Some network applications will require the ability to execute actions involving several databases, such as deciding which products to purchase in a supply chain or a battlefield command/control decision on whether or not there are sufficient resources for an attack to succeed. It has been proven [2] that such network-wide decisions can be delayed (i.e., blocked) for an indefinitely long time as the members of a transaction alternately fail and recover, or as the network communications suffer temporary disconnections. It is necessary to make the assumption that eventually all computers and network connections will be working long enough for a decision to be made, even though this assumption may not be true in the real world. In the case of long-term failures, our protocol will usually time out and abort. However, as we see below, there is a small possibility of blocking when the clocks are disabled during the final commit decision. In the P2P environment, it has long been recognized that providing a persistent, consistent distributed commit protocol is a very important and difficult issue [3]. Many e-business systems, such as electronic reservations, funds transfer, and inventory control, have benefited from distributed atomic commit protocol (ACP) technology. These ACP protocols typically work on a multitier architecture on a WAN,
References
[1]
C. Turker, K. Haller, C. Schuler, and H.-J. Schek, “How can we support grid transactions? Towards peer-to-peer transaction processing,” in Proceedings of the Conference on Innovative Data Systems Research (CIDR '05), Asilomar, Calif, USA, 2005.
[2]
M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” Journal of the ACM, vol. 32, no. 2, pp. 374–382, 1985.
[3]
B. Awerbuch and C. Tutu, “Maintaining database consistency in peer to peer networks,” Tech. Rep. CNDS-2002-2, 2002.
[4]
S. Fr？lund and R. Guerraoui, “E-transactions: end-to-end reliability for three-tier architectures,” IEEE Transactions on Software Engineering, vol. 28, no. 4, pp. 378–395, 2002.
[5]
F. Quaglia and P. Romano, “Ensuring e-transaction with asynchronous and uncoordinated application server replicas,” IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 3, pp. 364–378, 2007.
[6]
P. Romano, F. Quaglia, and B. Ciciani, “A lightweight and scalable e-Transaction protocol for three-tier systems with centralized back-end database,” IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 11, pp. 1578–1583, 2005.
[7]
P. Romano and F. Quaglia, “Providing e-Transaction guarantees in asynchronous systems with inaccurate failure detection,” in Proceedings of the 5th IEEE International Symposium on Network Computing and Applications (NCA '06), pp. 155–162, July 2006.
[8]
P. K. Chrysanthis, G. Samaras, and Y. J. Al-Houmaily, “Recovery and performance of atomic commit processing in distributed database systems,” in Recovery Mechanisms in Database Systems, V. Kumar and M. Hsu, Eds., Prentice-Hall, 1998.
[9]
S. B？ttcher, L. Gruenwald, and S. Obermeier, “A failure tolerating atomic commit protocol for mobile environments,” in Proceedings of the 8th International Conference on Mobile Data Management (MDM '07), pp. 158–165, May 2007.
[10]
K. P. Birman, Reliable Distributed Systems Technology, Web Service and Application, Springer, 2005.
[11]
J. Liebeherr, M. Nahas, and W. Si, “Application-layer multicasting with Delaunay triangulation overlays,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 8, pp. 1472–1488, 2002.
[12]
S. Q. Zhuang, B. Y. Zhao, A. D. Joseph, R. H. Katz, and J. D. Kubiatowicz, “Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination,” in Proceedings of the 11th International Workshop on Network and Operating System Support for Digital Audio and Video, June 2001.
[13]
A. Sobeih, J. Wang, and W. Yurcik, “Performance evaluation and comparison of tree and ring application-layer multicast overlay networks,” in Proceedings of the IEEE International Computer Engineering Conference (ICENCO '04), 2004.
[14]
A. Sobeih and W. Yurcik, “A survey of ring-building network protocols suitable for command and control group communications,” in Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defence IV, vol. 5778 of Proceedings of the SPIE, pp. 873–884, April 2005.
[15]
M. Castro, P. Druschel, A. M. Kermarrec, and A. I. T. Rowstron, “Scribe: a large-scale and decentralized application-level multicast infrastructure,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 8, pp. 1489–1499, 2002.
[16]
A. J. Ganesh, A. M. Kermarrec, and L. Massoulié, “Peer-to-peer membership management for gossip-based protocols,” IEEE Transactions on Computers, vol. 52, no. 2, pp. 139–149, 2003.
[17]
M. Portmann and A. Seneviratne, “The cost of application-level broadcast in a fully decentralized peer-to-peer network,” in Proceedings of the 7th International Symposium on Computers and Communications (ISCC '02), 2002.
[18]
S. Antony, D. Agrawal, and A. El Abbadi, “P2P systems with transactional semantics,” in Proceedings of the 11th International Conference on Extending Database Technology (EDBT '08), pp. 4–15, March 2008.
[19]
J. Bose, S. Bottcher, L. Gruenwald, S. Obermeier, H. Schweppe, and T. Steenweg, “An integrated commit protocol for mobile network databases,” in Proceedings of the 9th International Database Engineering & Application Symposium (IDEAS '05), Montreal, Canada, 2005.
[20]
K. Haller, H. Schuldt, and C. Türker, “Decentralized coordination of transactional processes in peer-to-peer environments,” in Proceedings of the 14th ACM International Conference on Information and Knowledge Management (CIKM '05), pp. 28–35, Bremen, Germany, November 2005.
[21]
C.-Y. Wang and D. J. Buehrer, “A ring-based decentralized collaborative non-blocking atomic commit protocol,” in IEEE/WIC/ACM International Conference on Web Intelligence (WI '08) Held in Conjunction with International Conference on Intelligent Agent Technology (IAT '08), Sydney, Australia, December 2008.
[22]
C. K. Yeo, B. S. Lee, and M. H. Er, “A survey of application level multicast techniques,” Computer Communications, vol. 27, no. 15, pp. 1547–1568, 2004.
[23]
D. J. Buehrer, L. O. Tse-Wen, and H. Chih-Ming, “Cadabia: a distributed, intelligent database architecture,” in Intelligent Multimedia, Computing, and Communications, M. Syed and O. Baiocchi, Eds., pp. 96–101, John Wiley and Sons, New York, NY, USA, 2001.
[24]
D. Buehrer and T.-Y. Wang, “The cadabia database project,” in Proceedings of the 14th Workshop on Object-Oriented Technology and Applications, pp. 385–392, Ywan Jr. University, September 2003.
[25]
A. Y. Halevy, Z. G. Ives, J. Madhavan, P. Mork, D. Suciu, and I. Tatarinov, “The piazza peer data management system,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 7, pp. 787–798, 2004.
[26]
A. Kementsietsidis, M. Arenas, and R. J. Miller, “Mapping data in peer-to-peer systems: semantics and algorithmic issues,” in Proceedings of the ACM International Conference on Management of Data (SIGMOD '03), pp. 325–336, June 2003.
[27]
K. Aberer, P. Cudré-Mauroux, A. Datta et al., “P-Grid: a self-organizing structured P2P system,” SIGMOD Record, vol. 32, no. 3, pp. 29–33, 2003.
[28]
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: a scalable peer-to-peer lookup service for internet applications,” in Proceedings of the ACM Applications, Technologies, Architectures, and Protocols for Computers Communications (SIGCOMM '01), pp. 149–160, August 2001.
[29]
R. Guerraoui, HurfinM, A. Mostefaoui, R. Oliveira, M. Raynal, and A. Schiper, “Consensus in asynchronous distributed systems: a concise guided tour,” in Advances in Distributed Systems, vol. 1752 of Lecture Notes in Computer Science, pp. 33–47, Springer, 2000.
[30]
P. Bernstein and E. Newcomer, Principles of Transaction Processing, Morgan Kaufmann, 1997.
[31]
D. A. Agarwal, L. E. Moser, P. M. Melliar-Smith, and R. K. Budhia, “The totem multiple-ring ordering and topology maintenance protocol,” ACM Transactions on Computer Systems, vol. 16, no. 2, pp. 93–132, 1998.
[32]
Y. Amir, L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, and P. Ciarfella, “Totem single-ring ordering and membership protocol,” ACM Transactions on Computer Systems, vol. 13, no. 4, pp. 311–342, 1995.
[33]
A. Schiper, K. Birman, and P. Stephenson, “Lightweight causal and atomic group multicast,” ACM Transactions on Computer Systems (TOCS), vol. 9, no. 3, pp. 272–314, 1991.
