2020

• Sebastian Daum, Fabian Kuhn, Yannic Maus
  Rumor spreading with bounded in-degree.
  2020 Theor Comput Sci, volume: 810, pages: 43 - 57
  » show abstract« hide abstract
  Abstract

  In the gossip-based model of communication for disseminating information in a network, in each time unit, every node u can contact a single random neighbor v but can possibly be contacted by many nodes. In the present paper, we consider a restricted model where at each node only one incoming call can be answered in one time unit. We study the implied weaker version of the well-studied pull protocol, which we call restricted pull. We prove an exponential separation of the rumor spreading time between two variants of the protocol (the answered call among a set of calls is chosen adversarially or uniformly at random). Further, we show that if the answered call is chosen randomly, the slowdown of restricted pull versus the classic pull protocol can w.h.p. be upper bounded by , where with Δ and δ being the largest and smallest degree of the network and being the degree of u.

2016

• Fabian Kuhn, Sebastian Daum, Yannic Maus
  Rumor Spreading with Bounded In-Degree
  2016 23rd Int. Coll. on Structural Information and Communication Complexity (SIROCCO), Helsinki, Finland
  » show abstract« hide abstract
  Abstract

  In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, it disperses it to v (known as PUSH) and if it does not, it requests it from v (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by O(Δ/δlogn), where Δ and δ are the largest and smallest degree of the network.

2015

• Fabian Kuhn, Sebastian Daum, Yannic Maus
  Brief Announcement: Rumor Spreading with Bounded In-Degree
  2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan
  » show abstract« hide abstract
  Abstract

  In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, it disperses it to v (known as PUSH) and if it does not, it requests it from v (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by O(Δ/δlogn), where Δ and δ are the largest and smallest degree of the network.
• Sebastian Daum, Fabian Kuhn
  Tight Bounds for MIS in Multichannel Radio Networks
  2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan
  » show abstract« hide abstract
  Abstract

  In [7] an algorithm has been presented that computes a maximal independent set (MIS) within O(log^2 n/F + log n polyloglog n) rounds in an n-node multichannel radio network with F communication channels. The paper uses a multichannel variant of the standard graph-based radio network model without collision detection and it assumes that the network graph is a polynomially bounded independence graph (BIG), a natural combinatorial generalization of well-known geographic families. The upper bound of [7] is known to be optimal up to a polyloglog factor. In this paper, we adapt algorithm and analysis to improve the result of [7] in two ways. Mainly, we get rid of the polyloglog factor in the running time and we thus obtain an asymptotically optimal multichannel radio network MIS algorithm. In addition, our new analysis allows to generalize the class of graphs from those with polynomially bounded local independence to graphs where the local independence is bounded by an arbitrary function of the neighborhood radius.

2013

• Sebastian Daum, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Broadcast in the Ad Hoc SINR Model
  2013 27th Int. Symp. on Distributed Computing (DISC), Jerusalem, Israel , pages: 358 - 372
  » show abstract« hide abstract
  Abstract

  An increasing amount of attention is being turned toward the study of distributed algorithms in wireless network models based on calculations of the signal to noise and interference ratio (SINR). In this paper we introduce the ad hoc SINR model, which, we argue, reduces the gap between theory results and real world deployment. We then use it to study upper and lower bounds for the canonical problem of broadcast on the graph induced by both strong and weak links. For strong connectivity broadcast, we present a new randomized algorithm that solves the problem in O(Dlog(n)polylog(R)) rounds in networks of size n, with link graph diameter D, and a ratio between longest and shortest links bounded by R. We then show that for back-off style algorithms (a common type of algorithm where nodes do not explicitly coordinate with each other) and compact networks (a practice-motivated model variant that treats the distance from very close nodes as equivalent), there exist networks in which centralized algorithms can solve broadcast in O(1) rounds, but distributed solutions require Ω(n) rounds. We then turn our attention to weak connectivity broadcast, where we show a similar Ω(n) lower bound for all types of algorithms, which we (nearly) match with a back-off style O(nlog^2 n)-round upper bound. Our broadcast algorithms are the first known for SINR-style models that do not assume synchronous starts, as well as the first known not to depend on power control, tunable carrier sensing, geographic information and/or exact knowledge of network parameters.
• Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Maximal Independent Sets in Multichannel Radio Networks
  2013 32nd ACM Symp. on Principles of Distributed Computing (PODC), Montreal, Canada , pages: 335 - 344
  » show abstract« hide abstract
  Abstract

  We present new upper bounds for fundamental problems in multichannel wireless networks. These bounds address the benefits of dynamic spectrum access, i.e., to what extent multiple communication channels can be used to improve performance. In more detail, we study a multichannel generalization of the standard graph-based wireless model without collision detection, and assume the network topology satisfies polynomially bounded independence. Our core technical result is an algorithm that constructs a maximal independent set (MIS) in O(log^2(n)/F)+ Õ(log n) rounds, in networks of size n with F channels, where the Õ-notation hides polynomial factors in loglog n. Moreover, we use this MIS algorithm as a subroutine to build a constant-degree connected dominating set in the same asymptotic time. Leveraging this structure, we are able to solve global broadcast and leader election within O(D + log^2(n)/F) + Õ(logn) rounds, where D is the diameter of the graph, and k-message multi-message broadcast in O(D + k + log^2(n)/F)+Õ(logn) rounds for unrestricted message size (with a slow down of only a log factor on the k term under the assumption of restricted message size). In all five cases above, we prove: (a) our results hold with high probability (i.e., at least 1-1/n); (b) our results are within polyloglog factors of the relevant lower bounds for multichannel networks; and (c) our results beat the relevant lower bounds for single channel networks. These new (near) optimal algorithms significantly expand the number of problems now known to be solvable faster in multichannel versus single channel wireless networks.

2012

• Sebastian Daum, Fabian Kuhn, Calvin Newport
  Efficient Symmetry Breaking in Multi-Channel Radio Networks
  2012 26th Int. Symp. on Distributed Computing (DISC), Salvador, Bahia, Brazil , pages: 238 - 252
• Sebastian Daum, Seth Gilbert, Fabian Kuhn, Calvin Newport
  Leader Election in Shared Spectrum Radio Networks
  2012 31st ACM Symp. on Principles of Distributed Computing (PODC), Madeira, Portugal , pages: 215 - 224

2011

• Sebastian Daum, Ralf Werner
  A Novel Feasible Discretization Method for Linear Semi-infinite Programming Applied to Basket Option Pricing
  2011 Optimization, volume: 60, issue: 10, pages: 1379 - 1398
  » show abstract« hide abstract
  Abstract

  In this exposition a novel feasible version of traditional discretization methods for linear semi-infinite programming problems is presented. It will be shown that each – usually infeasible – iterate can be easily supplemented with a feasible iterate based on the knowledge of a Slater point. The effectiveness of the method is demonstrated on the problem of finding model free bounds to basket option prices which has gained a significant interest in the last years. For this purpose a fresh look is taken on the upper bound problem and on some of its structure, which needs to be exploited to yield an efficient solution by the feasible discretization method. The presented approach allows the generalization of the problem setting by including exotic options (like power options, log-contracts, binary options, etc.) within the super-replicating portfolio.