In algorithm is lock free. An algorithm is wait

In today’s CPU design instead of trying to increase the throughput using multi-threaded process the architecture is focused on increasing the number of processes cover by per CPU. So when multiple threads of multiple processes trying to execute operations like compare-and-swap one thread block the others and thus throughput decreases. So in this research paper they provide the algorithm for fast concurrent lock-free operations here concurrent means more than one thread can perform atomic operation like compare-and-swap, bit-test-and-test by not blocking the others. For guaranteed that this algorithm is non-blocking, the algorithm should be obstruction free, lock free and wait free. If any process finishes in finite steps we can say that it is obstruction free and if one thread of any process running even other are starve the algorithm is lock free. An algorithm is wait free if every process executes every operation in finite steps. This algorithm provides the mechanism for search, insert and delete operation. The key is always stored on the leaf nodes instead of internal nodes. The internal nodes are used for access the key when ever new key is to be inserted first create the internal nodes then key becomes its child. The algorithm start with a seek phase in which it traverse the tree from root node to leaf node. The path traversed in the seek phase is called the access path in this path last three nodes called the grandparent, parent and child. For searching a key the operation compares the given key with the key stored on the leaf node in that path which traverse during the seek phase. It gives true result if the key matches otherwise it returns false. If we are inserting the value then in seek phase if that key is already in the tree it gives false because this algorithm does not work on the duplicate values but  if that key is not present in the tree the algorithm moves on the next phase which is the execution phase. In this phase to add the key in the tree in creates two nodes in the tree one is internal node and other is leaf node the key is stored on the leaf node and the children of the new internal node are the leafs node on that access path  and the new leaf node. After that the pointer is moved on the parent node which is the new internal node in the tree. For delete operation in the seek phase if the two keys do not match it returns false but if match then in execution phase it deletes the leaf node which containing the  key and also its parent which was the internal node and then the pointer moves to the grandparent.This algorithm is different from other lock-free algorithms because it works on the edges level rather than node level to perform an operation on the node which is the leaf node because it contains the key the operation first owns the ownership of that leaf node by marking the edge and now every edge has a tail node and a head node if operation performs on the both node then marking edge is called flagged and if only performs on the tail like in search then that marking edge is called tagging.This algorithms shows better performance than others because of it allocates fewer objects thus less operation to perform to modify as key is at leaf node no need to modify whole tree. The insert and delete operation can also perform as atomic operations.1 Aravind Natarajan and Neeraj Mittal.2014. Fast concurrent lock-free binary search trees. In  Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP’14).ACM,NewYork,USA,317-328. DOI: Arunmoezhi Ramachandran and Neeraj Mittal. 2015. A Fast Lock-Free Internal Binary Search Tree. In Proceedings of the 2015 International Conference on Distributed Computing and Networking(ICDCN ’15). ACM, New York, NY, USA, Article 37, 10 pages. DOI: Aravind Natarajan, Lee Savoie, and Neeraj Mittal. 2012. Brief announcement: concurrent wait-free red-black trees. In Proceedings of the 26th international conference on Distributed Computing (DISC’12). Springer-Verlag, Berlin, Heidelberg, 421-422. DOI: Shane V. Howley and Jeremy Jones. 2012. A non-blocking internal binary search tree. In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures (SPAA ’12). ACM, New York, NY, USA, 161-171. DOI: 5  Bogdan Nicolae, Gabriel Antoniu, Luc Bougé. 2008. Enabling lock-free concurrent fine-grain access to massive distributed data: Application to supernovae detection . IEEE international conference on clustered computing, 21 (October 2011), IEEE, Taskuba, Japan. DOI: 10.1109/CLUSTR.2008.46637876 Zhisheng Li, Ken C. K. Lee, Baihua Zheng, Wang-Chien Lee, Dik Lee, and Xufa Wang. 2011. IR-Tree: An Efficient Index for Geographic Document Search. IEEE Trans. on Knowl. and Data Eng.23, 4 (April 2011), 585-599.7 Xiao Liang, Hongyu Yang, Yanci Zhang, Jun Yin, and Yue Cao. 2016. Efficient kd-tree construction for ray tracing using ray distribution sampling. IEEE Trans. On  Multimedia Tools Appl. 75, 23 (December 2016), 15881-15899.8 Adil Alpkocak, Taner Danisman, and Tuba Ulker. 2001. A Parallel Similarity Search in High Dimensional Metric Space Using M-Tree. In Proceedings of the NATO Advanced Research Workshop on Advanced Environments, Tools, and Applications for Cluster Computing-Revised Papers (IWCC ’01).