BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Thomas Nowak

Thomas Nowak appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODistributed, Parallel, and Cluster ComputingDiscrete MathematicsSystems and ControlOther Computer Sciencemath.DSmath.PRmath.RA

Catalog footprint

What is connected

15works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2020arXiv

Distributed Computation with Continual Population Growth

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 $Ω(\sqrt{n\log 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank

Building on the weak CSR approach developed in a previous paper by Merlet, Nowak and Sergeev, we establish new bounds for the periodicity threshold of the powers of a tropical matrix. According to that approach, bounds on the ultimate periodicity threshold take the form of T=max(T_1,T_2), where T_1 is a bound on the time after which the weak CSR expansion starts to hold and T_2 is a bound on the time after which the first CSR term starts to dominate. The new bounds on T_1 and T_2 established in this paper make use of the cyclicity of the associated graph and the (tropical) factor rank of the matrix, which leads to much improved bounds in favorable cases. For T_1, in particular, we obtain new extensions of bounds of Schwarz, Kim and Gregory-Kirkland-Pullman, previously known as bounds on exponents of digraphs. For similar bounds on T_2, we introduce the novel concept of walk reduction threshold and establish bounds on it that use both cyclicity and factor rank.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Tightness of Bounds for Transients of Weak CSR Expansions and Periodicity Transients of Critical Rows and Columns of Tropical Matrix Powers

We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by $\max\{T_1,T_2\}$, where $T_1$ is the weak CSR threshold and $T_2$ is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for $T_1$ and $T_2$, naturally leading to the question which matrices, if any, attain these bounds. In the present paper we characterize the matrices attaining two particular bounds on $T_1$, which are generalizations of the bounds of Wielandt and Dulmage-Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Multidimensional Asymptotic Consensus in Dynamic Networks

We study the problem of asymptotic consensus as it occurs in a wide range of applications in both man-made and natural systems. In particular, we study systems with directed communication graphs that may change over time. We recently proposed a new family of convex combination algorithms in dimension one whose weights depend on the received values and not only on the communication topology. Here, we extend this approach to arbitrarily high dimensions by introducing two new algorithms: the ExtremePoint and the Centroid algorithm. Contrary to classical convex combination algorithms, both have component-wise contraction rates that are constant in the number of agents. Paired with a speed-up technique for convex combination algorithms, we get a convergence time linear in the number of agents, which is optimal. Besides their respective contraction rates, the two algorithms differ in the fact that the Centroid algorithm's update rule is independent of any coordinate system while the ExtremePoint algorithm implicitly assumes a common agreed-upon coordinate system among agents. The latter assumption may be realistic in some man-made multi-agent systems but is highly questionable in systems designed for the modelization of natural phenomena. Finally we prove that our new algorithms also achieve asymptotic consensus under very weak connectivity assumptions, provided that agent interactions are bidirectional.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Amortized Averaging Algorithms for Approximate Consensus

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 allows their decision time to drop from being exponential in the number $n$ of processes to being linear under the assumption that each process knows $n$. In particular, the amortized midpoint algorithm, which achieves a linear decision time, works in completely anonymous dynamic rooted networks where processes can exchange and store continuous values, and under the assumption that the number of processes is known to all processes. We then study the way amortized averaging algorithms degrade when communication graphs are from time to time non rooted, or with a wrong estimate of the number of processes. Finally, we analyze the amortized midpoint algorithm under the additional constraint that processes can only store and send quantized values, and get as a corollary that the 2-set consensus problem is solvable in linear time in any rooted dynamic network model when allowing all decision values to be in the range of initial values.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymptotic Consensus Without Self-Confidence

This paper studies asymptotic consensus in systems in which agents do not necessarily have self-confidence, i.e., may disregard their own value during execution of the update rule. We show that the prevalent hypothesis of self-confidence in many convergence results can be replaced by the existence of aperiodic cores. These are stable aperiodic subgraphs, which allow to virtually store information about an agent's value distributedly in the network. Our results are applicable to systems with message delays and memory loss.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms

In this paper, we investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both synchronous and partially synchronous systems, approximate consensus is solvable if and only if the communication graph in each round has a rooted spanning tree, i.e., there is a coordinator at each time. The striking point in this result is that the coordinator is not required to be unique and can change arbitrarily from round to round. Interestingly, the class of averaging algorithms, which are memoryless and require no process identifiers, entirely captures the solvability issue of approximate consensus in that the problem is solvable if and only if it can be solved using any averaging algorithm. Concerning the time complexity of averaging algorithms, we show that approximate consensus can be achieved with precision of $\varepsilon$ in a coordinated network model in $O(n^{n+1} \log\frac{1}{\varepsilon})$ synchronous rounds, and in $O(Δn^{nΔ+1} \log\frac{1}{\varepsilon})$ rounds when the maximum round delay for a message to be delivered is $Δ$. While in general, an upper bound on the time complexity of averaging algorithms has to be exponential, we investigate various network models in which this exponential bound in the number of nodes reduces to a polynomial bound. We apply our results to networked systems with a fixed topology and classical benign fault models, and deduce both known and new results for approximate consensus in these systems. In particular, we show that for solving approximate consensus, a complete network can tolerate up to 2n-3 arbitrarily located link faults at every round, in contrast with the impossibility result established by Santoro and Widmayer (STACS '89) showing that exact consensus is not solvable with n-1 link faults per round originating from the same node.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Faithful Glitch Propagation in Binary Circuit Models

Modern digital circuit design relies on fast digital timing simulation tools and, hence, on accurate binary-valued circuit models that faithfully model signal propagation, even throughout a complex design. Unfortunately, it was recently proved [Függer et al., ASYNC'13] that no existing binary-valued circuit model proposed so far, including the two most commonly used pure and inertial delay channels, faithfully captures glitch propagation: For the simple Short-Pulse Filtration (SPF) problem, which is related to a circuit's ability to suppress a single glitch, we showed that the quite broad class of bounded single-history channels either contradict the unsolvability of SPF in bounded time or the solvability of SPF in unbounded time in physical circuits. In this paper, we propose a class of binary circuit models that do not suffer from this deficiency: Like bounded single-history channels, our involution channels involve delays that may depend on the time of the previous output transition. Their characteristic property are delay functions which are based on involutions, i.e., functions that form their own inverse. A concrete example of such a delay function, which is derived from a generalized first-order analog circuit model, reveals that this is not an unrealistic assumption. We prove that, in sharp contrast to what is possible with bounded single-history channels, SPF cannot be solved in bounded time due to the nonexistence of a lower bound on the delay of involution channels, whereas it is easy to provide an unbounded SPF implementation. It hence follows that binary-valued circuit models based on involution channels allow to solve SPF precisely when this is possible in physical circuits. To the best of our knowledge, our model is hence the very first candidate for a model that indeed guarantees faithful glitch propagation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Generalizations of Bounds on the Index of Convergence to Weighted Digraphs

We study sequences of optimal walks of a growing length, in weighted digraphs, or equivalently, sequences of entries of max-algebraic matrix powers with growing exponents. It is known that these sequences are eventually periodic when the digraphs are strongly connected. The transient of such periodicity depends, in general, both on the size of digraph and on the magnitude of the weights. In this paper, we show that some bounds on the indices of periodicity of (unweighted) digraphs, such as the bounds of Wielandt, Dulmage-Mendelsohn, Schwarz, Kim and Gregory-Kirkland-Pullman, apply to the weights of optimal walks when one of their ends is a critical node.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Unfaithful Glitch Propagation in Existing Binary Circuit Models

We show that no existing continuous-time, binary value-domain model for digital circuits is able to correctly capture glitch propagation. Prominent examples of such models are based on pure delay channels (P), inertial delay channels (I), or the elaborate PID channels proposed by Bellido-Díaz et al. We accomplish our goal by considering the solvability/non-solvability border of a simple problem called Short-Pulse Filtration (SPF), which is closely related to arbitration and synchronization. On one hand, we prove that SPF is solvable in bounded time in any such model that provides channels with non-constant delay, like I and PID. This is in opposition to the impossibility of solving bounded SPF in real (physical) circuit models. On the other hand, for binary circuit models with constant-delay channels, we prove that SPF cannot be solved even in unbounded time; again in opposition to physical circuit models. Consequently, indeed none of the binary value-domain models proposed so far (and that we are aware of) faithfully captures glitch propagation of real circuits. We finally show that these modeling mismatches do not hold for the weaker eventual SPF problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Weak CSR expansions and transience bounds in max-plus algebra

This paper aims to unify and extend existing techniques for deriving upper bounds on the transient of max-plus matrix powers. To this aim, we introduce the concept of weak CSR expansions: A^t=CS^tR + B^t. We observe that most of the known bounds (implicitly) take the maximum of (i) a bound for the weak CSR expansion to hold, which does not depend on the values of the entries of the matrix but only on its pattern, and (ii) a bound for the CS^tR term to dominate. To improve and analyze (i), we consider various cycle replacement techniques and show that some of the known bounds for indices and exponents of digraphs apply here. We also show how to make use of various parameters of digraphs. To improve and analyze (ii), we introduce three different kinds of weak CSR expansions (named after Nachtigall, Hartman-Arguelles, and Cycle Threshold). As a result, we obtain a collection of bounds, in general incomparable to one another, but better than the bounds found in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

New Transience Bounds for Long Walks

Linear max-plus systems describe the behavior of a large variety of complex systems. It is known that these systems show a periodic behavior after an initial transient phase. Assessment of the length of this transient phase provides important information on complexity measures of such systems, and so is crucial in system design. We identify relevant parameters in a graph representation of these systems and propose a modular strategy to derive new upper bounds on the length of the transient phase. By that we are the first to give asymptotically tight and potentially subquadratic transience bounds. We use our bounds to derive new complexity results, in particular in distributed computing.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Transience of Linear Max-Plus Dynamical Systems

We study the transients of linear max-plus dynamical systems. For that, we consider for each irreducible max-plus matrix A, the weighted graph G(A) such that A is the adjacency matrix of G(A). Based on a novel graph-theoretic counterpart to the number-theoretic Brauer's theorem, we propose two new methods for the construction of arbitrarily long paths in G(A) with maximal weight. That leads to two new upper bounds on the transient of a linear max-plus system which both improve on the bounds previously given by Even and Rajsbaum (STOC 1990, Theory of Computing Systems 1997), by Bouillard and Gaujal (Research Report 2000), and by Soto y Koelemeijer (PhD Thesis 2003), and are, in general, incomparable with Hartmann and Arguelles' bound (Mathematics of Operations Research 1999). With our approach, we also show how to improve the latter bound by a factor of two. A significant benefit of our bounds is that each of them turns out to be linear in the size of the system in various classes of linear max-plus system whereas the bounds previously given are all at least quadratic. Our second result concerns the relationship between matrix and system transients: We prove that the transient of an NxN matrix A is, up to some constant, equal to the transient of an A-linear system with an initial vector whose norm is quadratic in N. Finally, we study the applicability of our results to the well-known Full Reversal algorithm whose behavior can be described as a min-plus linear system.

0 citations0 reviewsNo code linkedOpen access