License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.35
URN: urn:nbn:de:0030-drops-113423
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11342/
Go to the corresponding LIPIcs Volume Portal

Avin, Chen ; Salem, Iosif ; Schmid, Stefan

Brief Announcement: On Self-Adjusting Skip List Networks

pdf-format:
LIPIcs-DISC-2019-35.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{avin_et_al:LIPIcs:2019:11342,
  author =	{Chen Avin and Iosif Salem and Stefan Schmid},
  title =	{{Brief Announcement: On Self-Adjusting Skip List Networks}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{35:1--35:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11342},
  URN =		{urn:nbn:de:0030-drops-113423},
  doi =		{10.4230/LIPIcs.DISC.2019.35},
  annote =	{Keywords: self-adjusting networks, skip lists, working set, online algorithms}
}

Keywords: self-adjusting networks, skip lists, working set, online algorithms
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI