Dr. Sebastian Daum
Ph.D. Student (2012 - 2015)
Publications
Years: 2020 |
2016 |
2015 |
2013 |
2012 |
2011 | show all Journal Papers Sebastian Daum, Fabian Kuhn, Yannic MausRumor 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. Conference papers Fabian Kuhn, Sebastian Daum, Yannic MausRumor 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. Conference papers Fabian Kuhn, Sebastian Daum, Yannic MausBrief 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 KuhnTight 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. Conference papers Sebastian Daum, Seth Gilbert, Fabian Kuhn, Calvin NewportBroadcast 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 NewportMaximal 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. Conference papers Sebastian Daum, Fabian Kuhn, Calvin NewportEfficient 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 NewportLeader Election in Shared Spectrum Radio Networks 2012 31st ACM Symp. on Principles of Distributed Computing (PODC), Madeira, Portugal , pages : 215 - 224 Journal Papers Sebastian Daum, Ralf WernerA 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.