5 Search Results for "Avin, Chen"


Document
Brief Announcement
Brief Announcement: On Self-Adjusting Skip List Networks

Authors: Chen Avin, Iosif Salem, and Stefan Schmid

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


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.

Cite as

Chen Avin, Iosif Salem, and Stefan Schmid. Brief Announcement: On Self-Adjusting Skip List Networks. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 35:1-35:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{avin_et_al:LIPIcs.DISC.2019.35,
  author =	{Avin, Chen and Salem, Iosif and Schmid, Stefan},
  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 =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.35},
  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}
}
Document
Demand-Aware Network Designs of Bounded Degree

Authors: Chen Avin, Kaushik Mondal, and Stefan Schmid

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
Traditionally, networks such as datacenter interconnects are designed to optimize worst-case performance under arbitrary traffic patterns. Such network designs can however be far from optimal when considering the actual workloads and traffic patterns which they serve. This insight led to the development of demand-aware datacenter interconnects which can be reconfigured depending on the workload. Motivated by these trends, this paper initiates the algorithmic study of demand-aware networks (DANs), and in particular the design of bounded-degree networks. The inputs to the network design problem are a discrete communication request distribution, D, defined over communicating pairs from the node set V, and a bound, d, on the maximum degree. In turn, our objective is to design an (undirected) demand-aware network N = (V,E) of bounded-degree d, which provides short routing paths between frequently communicating nodes distributed across N. In particular, the designed network should minimize the expected path length on N (with respect to D), which is a basic measure of the efficiency of the network. We show that this fundamental network design problem exhibits interesting connections to several classic combinatorial problems and to information theory. We derive a general lower bound based on the entropy of the communication pattern D, and present asymptotically optimal network-aware design algorithms for important distribution families, such as sparse distributions and distributions of locally bounded doubling dimensions.

Cite as

Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-Aware Network Designs of Bounded Degree. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 5:1-5:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{avin_et_al:LIPIcs.DISC.2017.5,
  author =	{Avin, Chen and Mondal, Kaushik and Schmid, Stefan},
  title =	{{Demand-Aware Network Designs of Bounded Degree}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.5},
  URN =		{urn:nbn:de:0030-drops-80153},
  doi =		{10.4230/LIPIcs.DISC.2017.5},
  annote =	{Keywords: Network design, reconfigurable networks, datacenter topology, peer-topeer computing, entropy, sparse spanners}
}
Document
Brief Announcement
Brief Announcement: Distributed SplayNets

Authors: Bruna S. Peres, Olga Goussevskaia, Stefan Schmid, and Chen Avin

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
SplayNets are reconfigurable networks which adjust to the communication pattern over time. We present DiSplayNets, a distributed (concurrent and decentralized) implementation of SplayNets.

Cite as

Bruna S. Peres, Olga Goussevskaia, Stefan Schmid, and Chen Avin. Brief Announcement: Distributed SplayNets. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 58:1-58:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{peres_et_al:LIPIcs.DISC.2017.58,
  author =	{Peres, Bruna S. and Goussevskaia, Olga and Schmid, Stefan and Avin, Chen},
  title =	{{Brief Announcement: Distributed SplayNets}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{58:1--58:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.58},
  URN =		{urn:nbn:de:0030-drops-79661},
  doi =		{10.4230/LIPIcs.DISC.2017.58},
  annote =	{Keywords: Decentralization, Concurrency, Reconfigurable Networks}
}
Document
The Cost of Global Broadcast in Dynamic Radio Networks

Authors: Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, and Anisur Rahaman Molla

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)


Abstract
We study the single-message broadcast problem in dynamic radio networks. We show that the time complexity of the problem depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. More formally, we model communication using the standard graph-based radio network model. To model the dynamic network, we use a variant of the synchronous dynamic graph model introduced in [Kuhn et al., STOC 2010]. For integer parameters T >= 1 and k => 1, we call a dynamic graph T-interval k-connected if for every interval of T consecutive rounds, there exists a k-vertex-connected stable subgraph. Further, for an integer parameter tau >= 0, we say that the adversary providing the dynamic network is tau-oblivious if for constructing the graph of some round t, the adversary has access to all the randomness (and states) of the algorithm up to round t-tau. As our main result, we show that for any T >= 1, any k >= 1, and any tau = 1, for a tau-oblivious adversary, there is a distributed algorithm to broadcast a single message in time O((1+n/(k * min(tau,T)) * n *log^3(n)). We further show that even for large interval k-connectivity, efficient broadcast is not possible for the usual adaptive adversaries. For a 1-oblivious adversary, we show that even for any T <= (n/k)^{1-epsilon} (for any constant epsilon > 0) and for any k >= 1, global broadcast in T-interval k-connected networks requires at least Omega(n^2/k^2*log(n)) time. Further, for a 0-oblivious adversary, broadcast cannot be solved in T-interval k-connected networks as long as T < n-k.

Cite as

Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, and Anisur Rahaman Molla. The Cost of Global Broadcast in Dynamic Radio Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.OPODIS.2015.7,
  author =	{Ahmadi, Mohamad and Ghodselahi, Abdolhamid and Kuhn, Fabian and Molla, Anisur Rahaman},
  title =	{{The Cost of Global Broadcast in Dynamic Radio Networks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.7},
  URN =		{urn:nbn:de:0030-drops-65989},
  doi =		{10.4230/LIPIcs.OPODIS.2015.7},
  annote =	{Keywords: radio network, dynamic network, global broadcast, interval connectivity, hitting game}
}
Document
The Price of Local Power Control in Wireless Scheduling

Authors: Magnús M. Halldórsson and Tigran Tonoyan

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Oblivious power schemes are motivated by networking scenarios when power levels must be decided in advance, and not as part of the scheduling computation. We present the first O(log log Delta)-approximation algorithm, which is known to be best possible (in terms of Delta) for oblivious power schemes, where Delta is the longest to shortest link length ratio. We achieve this by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder. Combined, our results resolve the price of local power for wireless scheduling, or the value of allowing unfettered power control.

Cite as

Magnús M. Halldórsson and Tigran Tonoyan. The Price of Local Power Control in Wireless Scheduling. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 529-542, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.FSTTCS.2015.529,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Tonoyan, Tigran},
  title =	{{The Price of Local Power Control in Wireless Scheduling}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{529--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.529},
  URN =		{urn:nbn:de:0030-drops-56243},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.529},
  annote =	{Keywords: Wireless Scheduling, Physical Model, Oblivious Power}
}
  • Refine by Author
  • 3 Avin, Chen
  • 3 Schmid, Stefan
  • 1 Ahmadi, Mohamad
  • 1 Ghodselahi, Abdolhamid
  • 1 Goussevskaia, Olga
  • Show More...

  • Refine by Classification
  • 1 Networks → Topology analysis and generation

  • Refine by Keyword
  • 1 Concurrency
  • 1 Decentralization
  • 1 Network design
  • 1 Oblivious Power
  • 1 Physical Model
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2017
  • 1 2015
  • 1 2016
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail