SPLAYNET : Towards Nearby Self-Adjusting Wireless Networks

Authors(2) :-Gaddipathi Bharathi, Parchuri Kaneeja

This paper starts the investigation of locally self-changing systems: organizes whose topology adjusts progressively and in a decentralized way, to the correspondence design . Our vision can be viewed as a dispersed speculation of the self-altering datastructures presented by Sleator and Tarjan [22]: rather than their spread trees which powerfully upgrade the query costs from a solitary hub (in particular the tree root), we try to limit the steering cost between discretionary correspondence combines in the system. As an initial step, we consider disseminated twofold hunt trees (BSTs), which are appealing for their help of insatiable steering. We present a straightforward model which catches the key tradeoff between the advantages and expenses of self-changing systems. We introduce the SplayNet calculation and formally dissect its execution, and demonstrate its optimality in particular contextual investigations. We additionally present lower bound methods in light of interim cuts and edge development, to think about the restrictions of any request enhanced system. At last, we stretch out our investigation to multi-tree systems, and highlight an interesting contrast amongst great and disseminated spread trees.

Authors and Affiliations

Gaddipathi Bharathi
Department of MCA , St. Mary's Group of Institutions, Guntur, Andhra Pradesh, India
Parchuri Kaneeja
Department of MCA , St. Mary's Group of Institutions, Guntur, Andhra Pradesh, India

BST, Self-Adjusting Wireless Networks, SPLAYNET

  1. B. Allen and I. Munro. Self-organizing binary search trees. J. ACM, 25:526-535, 1978.
  2. J. Aspnes and G. Shah. Skip graphs. ACM Transactions on Algorithms (TALG), 3(4):37-es, 2007.
  3. C. Avin, M. Borokhovich, and S. Schmid. Obst: A self-adjusting peer-to-peer overlay based on multiple bsts. In Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on, pages 1-5. IEEE, 2013.
  4. C. Avin, M. Borokhovich, and S. Schmid. Obst: A self-adjusting peer-to-peer overlay based on multiple bsts. In Proc. 13th IEEE International Conference on Peer-to-Peer Computing (P2P), September 2013.
  5. C. Avin, B. Haeupler, Z. Lotker, C. Scheideler, and S. Schmid. Locally self-adjusting tree networks. In Parallel & Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on, pages 395-406. IEEE, 2013.
  6. C. Avin, B. Haeupler, Z. Lotker, C. Scheideler, and S. Schmid. Locally self-adjusting tree networks. In Proc. 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2013.
  7. E. D. Demaine, D. Harmon, J. Iacono, and M. Patrascu. Dynamic optimality - almost. In Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 484-490, 2004.
  8. J. Dī?az, J. Petit, and M. Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313-356, 2002.
  9. J. Dī?az, J. Petit, and M. Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313-356, 2002.
  10. H. Farvaresh and M. Sepehri. A branch and bound algorithm for bi-level discrete network design problem. Networks and Spatial Economics, 13(1):67-106, 2013.
  11. U. Feige and J. Lee. An improved approximation ratio for the minimum linear arrangement problem. Information Processing Letters, 101(1):26- 29, 2007.
  12. L. H. Harper. Optimal assignment of numbers to vertices. J. SIAM, (12):131-135, 1964.
  13. N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. Skipnet: A scalable overlay network with practical locality properties. In Proc. 4th Conference on USENIX Symposium on Internet Technologies and Systems (USITS), 2003.
  14. S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439- 562, 2006.
  15. D. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098-1101, 1952.
  16. D. Knuth. Optimum binary search trees. Acta informatica, 1(1):14-25, 1971.
  17. K. Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5(4):287-295, 1975.
  18. G. Mitchison and R. Durbin. Optimal numberings of an n n array. SIAM J. Algebraic Discrete Methods, 7(4):571-582, 1986.
  19. R. Ravi, A. Agrawal, and P. N. Klein. Ordering problems approximated: Single-processor scheduling and interval graph completion. In Proc. International Colloquium on Automata, Languages and Programming (ICALP), 1991.
  20. S. Schmid, C. Avin, C. Scheideler, and B. Haeupler. Brief announce-ment: Splaynets (towards self-adjusting distributed data structures). In Proc. 26th International Symposium on Distributed Computing (DISC), 2012.
  21. A. Sinclair and M. Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput., 82(1):93-133, 1989.
  22. D. Sleator and R. Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652-686, 1985.
  23. C. C. Wang, J. Derryberry, and D. D. Sleator. O(log log n)-competitive dynamic binary search trees. In Proc. 17th Annual ACM-SIAM Sympo-sium on Discrete Algorithm (SODA), pages 374-383, 2006.

Publication Details

Published in : Volume 2 | Issue 4 | July-August 2017
Date of Publication : 2017-08-31
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 221-228
Manuscript Number : CSEIT172474
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

Gaddipathi Bharathi, Parchuri Kaneeja, "SPLAYNET : Towards Nearby Self-Adjusting Wireless Networks", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 4, pp.221-228 , July-August.2017
URL : http://ijsrcseit.com/CSEIT172474

Follow Us

Contact Us