Search Results

Documents authored by Nowak, Thomas

Document
Invited Talk
DOI: 10.4230/LIPIcs.SAND.2024.2
Distributed Computation with Bacteria (Invited Talk)

Authors: Thomas Nowak

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
Computing via synthetically engineered bacteria is a vibrant and active field with numerous applications in bio-production, bio-sensing, and medicine. Motivated by the lack of robustness and by resource limitation inside single cells, distributed approaches with communication among bacteria have recently gained in interest. In this talk, we describe the most important distributed approaches to synthetic biology with bacteria and discuss the crucial task of mathematical modeling of these systems. A particular problem is that of population growth happening concurrently, and possibly interfering, with the desired bio-computation. Specifically, we present a fast protocol in systems with continuous population growth for the majority consensus problem and prove that it correctly identifies the initial majority among two inputs with high probability. We also present a fast protocol that correctly computes the NAND of two inputs with high probability. By combining NAND gates with the majority consensus protocol as an amplifier, it is possible to compute arbitrary Boolean functions. The proposed protocols help set the stage for bio-engineered distributed computation that directly addresses continuous stochastic population growth. Own work presented in this talk is mostly based on joint work with Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, and Quentin Soubeyran.
Cite as

Thomas Nowak. Distributed Computation with Bacteria (Invited Talk). In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nowak:LIPIcs.SAND.2024.2,
  author =	{Nowak, Thomas},
  title =	{{Distributed Computation with Bacteria}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.2},
  URN =		{urn:nbn:de:0030-drops-198807},
  doi =		{10.4230/LIPIcs.SAND.2024.2},
  annote =	{Keywords: Microbiological circuits, chemical reaction networks, birth-death processes}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.5
Topological Characterization of Task Solvability in General Models of Computation

Authors: Hagit Attiya, Armando Castañeda, and Thomas Nowak

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
The famous asynchronous computability theorem (ACT) relates the existence of an asynchronous wait-free shared memory protocol for solving a task with the existence of a simplicial map from a subdivision of the simplicial complex representing the inputs to the simplicial complex representing the allowable outputs. The original theorem relies on a correspondence between protocols and simplicial maps in round-structured models of computation that induce a compact topology. This correspondence, however, is far from obvious for computation models that induce a non-compact topology, and indeed previous attempts to extend the ACT have failed. This paper shows that in every non-compact model, protocols solving tasks correspond to simplicial maps that need to be continuous. It first proves a generalized ACT for sub-IIS models, some of which are non-compact, and applies it to the set agreement task. Then it proves that in general models too, protocols are simplicial maps that need to be continuous, hence showing that the topological approach is universal. Finally, it shows that the approach used in ACT that equates protocols and simplicial complexes actually works for every compact model. Our study combines, for the first time, combinatorial and point-set topological aspects of the executions admitted by the computation model.
Cite as

Hagit Attiya, Armando Castañeda, and Thomas Nowak. Topological Characterization of Task Solvability in General Models of Computation. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2023.5,
  author =	{Attiya, Hagit and Casta\~{n}eda, Armando and Nowak, Thomas},
  title =	{{Topological Characterization of Task Solvability in General Models of Computation}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.5},
  URN =		{urn:nbn:de:0030-drops-191315},
  doi =		{10.4230/LIPIcs.DISC.2023.5},
  annote =	{Keywords: task solvability, combinatorial topology, point-set topology}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.7
Distributed Computation with Continual Population Growth

Authors: Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, and Quentin Soubeyran

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Computing with synthetically engineered bacteria is a vibrant and active field with numerous applications in bio-production, bio-sensing, and medicine. Motivated by the lack of robustness and by resource limitation inside single cells, distributed approaches with communication among bacteria have recently gained in interest. In this paper, we focus on the problem of population growth happening concurrently, and possibly interfering, with the desired bio-computation. Specifically, we present a fast protocol in systems with continuous population growth for the majority consensus problem and prove that it correctly identifies the initial majority among two inputs with high probability if the initial difference is Ω(√{nlog n}) where n is the total initial population. We also present a fast protocol that correctly computes the NAND of two inputs with high probability. We demonstrate that combining the NAND gate protocol with the continuous-growth majority consensus protocol, using the latter as an amplifier, it is possible to implement circuits computing arbitrary Boolean functions.
Cite as

Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, and Quentin Soubeyran. Distributed Computation with Continual Population Growth. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.DISC.2020.7,
  author =	{Cho, Da-Jung and F\"{u}gger, Matthias and Hopper, Corbin and Kushwaha, Manish and Nowak, Thomas and Soubeyran, Quentin},
  title =	{{Distributed Computation with Continual Population Growth}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.7},
  URN =		{urn:nbn:de:0030-drops-130856},
  doi =		{10.4230/LIPIcs.DISC.2020.7},
  annote =	{Keywords: microbiological circuits, majority consensus, birth-death processes}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.29
Byzantine Approximate Agreement on Graphs

Authors: Thomas Nowak and Joel Rybicki

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

Abstract
Consider a distributed system with n processors out of which f can be Byzantine faulty. In the approximate agreement task, each processor i receives an input value x_i and has to decide on an output value y_i such that 1) the output values are in the convex hull of the non-faulty processors' input values, 2) the output values are within distance d of each other. Classically, the values are assumed to be from an m-dimensional Euclidean space, where m >= 1. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to output vertices that are within distance d of each other in G, but still remain in the graph-induced convex hull of the input values. For d=0, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any d >= 1, we show that the task is solvable in asynchronous systems when G is chordal and n > (omega+1)f, where omega is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.
Cite as

Thomas Nowak and Joel Rybicki. Byzantine Approximate Agreement on Graphs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nowak_et_al:LIPIcs.DISC.2019.29,
  author =	{Nowak, Thomas and Rybicki, Joel},
  title =	{{Byzantine Approximate Agreement on Graphs}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{29:1--29:17},
  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.29},
  URN =		{urn:nbn:de:0030-drops-113363},
  doi =		{10.4230/LIPIcs.DISC.2019.29},
  annote =	{Keywords: consensus, approximate agreement, Byzantine faults, chordal graphs, lattice agreement}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.27
Fast Multidimensional Asymptotic and Approximate Consensus

Authors: Matthias Függer and Thomas Nowak

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We study the problems of asymptotic and approximate consensus in which agents have to get their values arbitrarily close to each others' inside the convex hull of initial values, either without or with an explicit decision by the agents. In particular, we are concerned with the case of multidimensional data, i.e., the agents' values are d-dimensional vectors. We introduce two new algorithms for dynamic networks, subsuming classical failure models like asynchronous message passing systems with Byzantine agents. The algorithms are the first to have a contraction rate and time complexity independent of the dimension d. In particular, we improve the time complexity from the previously fastest approximate consensus algorithm in asynchronous message passing systems with Byzantine faults by Mendes et al. [Distrib. Comput. 28] from Omega(d log (d Delta)/epsilon) to O(log Delta/epsilon), where Delta is the initial and epsilon is the terminal diameter of the set of vectors of correct agents.
Cite as

Matthias Függer and Thomas Nowak. Fast Multidimensional Asymptotic and Approximate Consensus. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fugger_et_al:LIPIcs.DISC.2018.27,
  author =	{F\"{u}gger, Matthias and Nowak, Thomas},
  title =	{{Fast Multidimensional Asymptotic and Approximate Consensus}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.27},
  URN =		{urn:nbn:de:0030-drops-98167},
  doi =		{10.4230/LIPIcs.DISC.2018.27},
  annote =	{Keywords: asymptotic consensus, approximate consensus, multidimensional data, dynamic networks, Byzantine processes}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.51
Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks

Authors: Matthias Függer, Thomas Nowak, and Manfred Schwarz

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

Abstract
In this work we study the performance of asymptotic and approximate consensus algorithms in dynamic networks. The asymptotic consensus problem requires a set of agents to repeatedly set their outputs such that the outputs converge to a common value within the convex hull of initial values. This problem, and the related approximate consensus problem, are fundamental building blocks in distributed systems where exact consensus among agents is not required, e.g., man-made distributed control systems, and have applications in the analysis of natural distributed systems, such as flocking and opinion dynamics. We prove new nontrivial lower bounds on the contraction rates of asymptotic consensus algorithms, from which we deduce lower bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented in [Charron-Bost et al., ICALP'16] for certain classes of networks that include classical failure assumptions, and confine the search for optimal bounds in the general case. Central to our lower bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks.
Cite as

Matthias Függer, Thomas Nowak, and Manfred Schwarz. Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fugger_et_al:LIPIcs.DISC.2017.51,
  author =	{F\"{u}gger, Matthias and Nowak, Thomas and Schwarz, Manfred},
  title =	{{Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{51:1--51: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.51},
  URN =		{urn:nbn:de:0030-drops-79921},
  doi =		{10.4230/LIPIcs.DISC.2017.51},
  annote =	{Keywords: Asymptotic Consensus, Dynamic Networks, Contraction Rate, Time Commplexity, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.137
Fast, Robust, Quantizable Approximate Consensus

Authors: Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This results in a drastic drop in decision times, from being exponential in the number n of processes to being polynomial under the assumption that each process knows n. In particular, the amortized midpoint algorithm is the first algorithm that achieves a linear decision time in dynamic rooted networks with an optimal contraction rate of 1/2 at each update step. We then show robustness of the amortized midpoint algorithm under violation of network assumptions: it gracefully degrades if communication graphs from time to time are non rooted, or under a wrong estimate of the number of processes. Finally, we prove that the amortized midpoint algorithm behaves well if processes can store and send only quantized values, rendering it well-suited for the design of dynamic networked systems. As a corollary we obtain that the 2-set consensus problem is solvable in linear time in any dynamic rooted network model.
Cite as

Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Fast, Robust, Quantizable Approximate Consensus. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 137:1-137:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.ICALP.2016.137,
  author =	{Charron-Bost, Bernadette and F\"{u}gger, Matthias and Nowak, Thomas},
  title =	{{Fast, Robust, Quantizable Approximate Consensus}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{137:1--137:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.137},
  URN =		{urn:nbn:de:0030-drops-62812},
  doi =		{10.4230/LIPIcs.ICALP.2016.137},
  annote =	{Keywords: approximate consensus, dynamic networks, averaging algorithms}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact