iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-030-34992-9_29
Self-adjusting Linear Networks | SpringerLink
Skip to main content

Self-adjusting Linear Networks

  • Conference paper
  • First Online:
Stabilization, Safety, and Security of Distributed Systems (SSS 2019)

Abstract

Emerging networked systems become increasingly flexible, reconfigurable, and “self-\(*\)”. This introduces an opportunity to adjust networked systems in a demand-aware manner, leveraging spatial and temporal locality in the workload for online optimizations. However, it also introduces a tradeoff: while more frequent adjustments can improve performance, they also entail higher reconfiguration costs. This paper initiates the formal study of list networks which self-adjust to the demand in an online manner, striking a balance between the benefits and costs of reconfigurations. We show that the underlying algorithmic problem can be seen as a distributed generalization of the classic dynamic list update problem known from self-adjusting datastructures: in a network, requests can occur between node pairs. This distributed version turns out to be significantly harder than the classical problem it generalizes. Our main results are a \(\varOmega (\log {n})\) lower bound on the competitive ratio, and a (distributed) online algorithm that is \(\mathcal {O}(\log {n})\)-competitive if the communication requests are issued according to a linear order.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    A function f such that \(f(f(x)) = x\) for all x.

References

  1. Albers, S.: A competitive analysis of the list update problem with lookahead. Theoret. Comput. Sci. 197(1–2), 95–109 (1998)

    Article  MathSciNet  Google Scholar 

  2. Albers, S.: Improved randomized on-line algorithms for the list update problem. SIAM J. Comput. 27(3), 682–693 (1998)

    Article  MathSciNet  Google Scholar 

  3. Albers, S., Von Stengel, B., Werchner, R.: A combined bit and timestamp algorithm for the list update problem. Inf. Process. Lett. 56(3), 135–139 (1995)

    Article  Google Scholar 

  4. Albers, S., Westbrook, J.: Self-organizing data structures. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 13–51. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0029563

    Chapter  Google Scholar 

  5. Ambühl, C.: Offline list update is NP-hard. In: Paterson, M.S. (ed.) ESA 2000. LNCS, vol. 1879, pp. 42–51. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45253-2_5

    Chapter  Google Scholar 

  6. Avin, C., van Duijn, I., Schmid, S.: Self-adjusting linear networks. arXiv preprint arXiv:1905.02472 (2019)

  7. Avin, C., Haeupler, B., Lotker, Z., Scheideler, C., Schmid, S.: Locally self-adjusting tree networks. In: 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, pp. 395–406. IEEE (2013)

    Google Scholar 

  8. Avin, C., Hercules, A., Loukas, A., Schmid, S.: Towards communication-aware robust topologies. ArXiv Technical Report (2017)

    Google Scholar 

  9. Avin, C., Loukas, A., Pacut, M., Schmid, S.: Online balanced repartitioning. In: Gavoille, C., Ilcinkas, D. (eds.) DISC 2016. LNCS, vol. 9888, pp. 243–256. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53426-7_18

    Chapter  Google Scholar 

  10. Avin, C., Mondal, K., Schmid, S.: Demand-aware network designs of bounded degree. In: Proceedings International Symposium on Distributed Computing (DISC) (2017)

    Google Scholar 

  11. Avin, C., Mondal, K., Schmid, S.: Demand-aware network design with minimal congestion and route lengths. In: Proceedings of IEEE INFOCOM (2019)

    Google Scholar 

  12. Avin, C., Schmid, S.: Toward demand-aware networking: a theory for self-adjusting networks. In: ACM SIGCOMM Computer Communication Review (CCR) (2018)

    Google Scholar 

  13. Bubeck, S., Cesa-Bianchi, N., et al.: Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends® Mach. Learn. 5(1), 1–122 (2012)

    Article  Google Scholar 

  14. Díaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. (CSUR) 34(3), 313–356 (2002)

    Article  Google Scholar 

  15. Fenz, T., Foerster, K.T., Schmid, S., Villedieu, A.: Efficient non-segregated routing for reconfigurable demand-aware networks. In: Proceedings of IFIP Networking (2019)

    Google Scholar 

  16. Huq, S., Ghosh, S.: Locally self-adjusting skip graphs. In: Proceedings of IEEE 37th International Conference on Distributed Computing Systems (ICDCS), pp. 805–815 (2017)

    Google Scholar 

  17. Ghobadi, M., et al.: Projector: agile reconfigurable data center interconnect. In: Proceedings of ACM SIGCOMM, pp. 216–229 (2016)

    Google Scholar 

  18. Olver, N., Pruhs, K., Schewior, K., Sitters, R., Stougie, L.: The itinerant list update problem. In: 13th Workshop on Models and Algorithms for Planning and Scheduling Problems, p. 163 (2017)

    Google Scholar 

  19. Peres, B., Souza, O., Goussevskaia, O., Schmid, S., Avin, C.: Distributed self-adjusting tree networks. In: Proceedings of IEEE INFOCOM (2019)

    Google Scholar 

  20. Reingold, N., Westbrook, J.: Off-line algorithms for the list update problem. Inf. Process. Lett. 60(2), 75–80 (1996)

    Article  MathSciNet  Google Scholar 

  21. Reingold, N., Westbrook, J., Sleator, D.D.: Randomized competitive algorithms for the list update problem. Algorithmica 11(1), 15–32 (1994)

    Article  MathSciNet  Google Scholar 

  22. Schmid, S., Avin, C., Scheideler, C., Borokhovich, M., Haeupler, B., Lotker, Z.: Splaynet: towards locally self-adjusting networks. IEEE/ACM Trans. Netw. (ToN) 24, 1421–1433 (2016)

    Article  Google Scholar 

  23. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)

    Article  MathSciNet  Google Scholar 

  24. Teia, B.: A lower bound for randomized list update algorithms. Inf. Process. Lett. 47(1), 5–9 (1993)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Ingo van Duijn .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Avin, C., van Duijn, I., Schmid, S. (2019). Self-adjusting Linear Networks. In: Ghaffari, M., Nesterenko, M., Tixeuil, S., Tucci, S., Yamauchi, Y. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2019. Lecture Notes in Computer Science(), vol 11914. Springer, Cham. https://doi.org/10.1007/978-3-030-34992-9_29

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-34992-9_29

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-34991-2

  • Online ISBN: 978-3-030-34992-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics