DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2016.15

Design Patterns in Beeping Algorithms

Authors: Arnaud Casteigts, Yves Métivier, John Michael Robson, and Akka Zemmari

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn, which we refer to as the BL variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Stronger variants exist where the nodes can also detect collision while they are beeping (B_{cd}L) or listening (BL_{cd}), or both (B_{cd}L_{cd}). Beeping models are weak in essence and even simple tasks are difficult or unfeasible with them. This paper starts with a discussion on generic building blocks (design patterns) which seem to occur frequently in the design of beeping algorithms. They include multi-slot phases: the fact of dividing the main loop into a number of specialised slots; exclusive beeps: having a single node beep at a time in a neighbourhood (within one or two hops); adaptive probability: increasing or decreasing the probability of beeping to produce more exclusive beeps; internal (resp. peripheral) collision detection: for detecting collision while beeping (resp. listening); and emulation of collision detection: for enabling this feature when it is not available as a primitive. We then provide algorithms for a number of basic problems, including colouring, 2-hop colouring, degree computation, 2-hop MIS, and collision detection (in BL). Using the patterns, we formulate these algorithms in a rather concise and elegant way. Their analyses (in the full version) are more technical, e.g. one of them relies on a Martingale technique with non-independent variables; another improves that of the MIS algorithm (P. Jeavons et al.) by getting rid of a gigantic constant (the asymptotic order was already optimal). Finally, we study the relative power of several variants of beeping models. In particular, we explain how every Las Vegas algorithm with collision detection can be converted, through emulation, into a Monte Carlo algorithm without, at the cost of a logarithmic slowdown. We prove that this slowdown is optimal up to a constant factor by giving a matching lower bound.

Cite as

Arnaud Casteigts, Yves Métivier, John Michael Robson, and Akka Zemmari. Design Patterns in Beeping Algorithms. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.OPODIS.2016.15,
  author =	{Casteigts, Arnaud and M\'{e}tivier, Yves and Robson, John Michael and Zemmari, Akka},
  title =	{{Design Patterns in Beeping Algorithms}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.15},
  URN =		{urn:nbn:de:0030-drops-70840},
  doi =		{10.4230/LIPIcs.OPODIS.2016.15},
  annote =	{Keywords: Beeping models, Design patterns, Collision detection, Colouring, 2-hop colouring, Degree computation, Emulation}
}

Document

DOI: 10.4230/DagSemProc.08431.4

Spanning Trees of Bounded Degree Graphs

Authors: John Michael Robson

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

Abstract

We consider lower bounds on the number of spanning trees of connected graphs with degree bounded by $d$. The question is of interest because such bounds may improve the analysis of the improvement produced by memorisation in the runtime of exponential algorithms. The value of interest is the constant $beta_d$ such that all connected graphs with degree bounded by $d$ have at least $beta_d^mu$ spanning trees where $mu$ is the cyclomatic number or excess of the graph, namely $m-n+1$. We conjecture that $beta_d$ is achieved by the complete graph $K_{d+1}$ but we have not proved this for any $d$ greater than $3$. We give weaker lower bounds on $beta_d$ for $dle 11$. First we establish lower bounds on the factor by which the number of spanning trees is multiplied when one new vertex is added to an existing graph so that the new vertex has degree $c$ and the maximum degree of the resulting graph is at most $d$. In all the cases analysed, this lower bound $f_{c,d}$ is attained when the graph before the addition was a complete graph of order $d$ but we have not proved this in general. Next we show that, for any cut of size $c$ cutting a graph $G$ of degree bounded by $d$ into two connected components $G_1$ and $G_2$, the number of spanning trees of $G$ is at least the product of this number for $G_1$ and $G_2$ multiplied by the same factor $f_{c,d}$. Finally we examine the process of repeatedly cutting a graph until no edges remain. The number of spanning trees is at least the product of the multipliers associated with all the cuts. Some obvious constraints on the number of cuts of each size give linear constraints on the normalised numbers of cuts of each size which are then used to lower bound $beta_d$ by the solution of a linear program. The lower bound obtained is significantly improved by imposing a rule that, at each stage, a cut of the minimum available size is chosen and adding some new constraints implied by this rule.

Cite as

John Michael Robson. Spanning Trees of Bounded Degree Graphs. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{robson:DagSemProc.08431.4,
  author =	{Robson, John Michael},
  title =	{{Spanning Trees of Bounded Degree Graphs}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.4},
  URN =		{urn:nbn:de:0030-drops-17997},
  doi =		{10.4230/DagSemProc.08431.4},
  annote =	{Keywords: Spanning trees, memorisation, cyclomatic number, bounded degree graphs, cut, linear program.}
}

Search Results

Documents authored by Robson, John Michael

Design Patterns in Beeping Algorithms

Abstract

Cite as

Spanning Trees of Bounded Degree Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message