2026-08-17T03:42:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11342 2024-03-06T10:47:59Z ddc:004 open_access

Brief Announcement: On Self-Adjusting Skip List Networks Avin, Chen Salem, Iosif Schmid, Stefan self-adjusting networks skip lists working set online algorithms This paper explores the design of dynamic network topologies which adjust to the workload they serve, in an online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on skip lists (which serve as the topology) and provide additional interesting properties such as local routing. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chen Avin and Iosif Salem and Stefan Schmid 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.35 urn:nbn:de:0030-drops-113423 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.35 eng https://creativecommons.org/licenses/by/3.0/legalcode