Source author record

Philipp Czerner

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Networking and Internet Architecture

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Lower Bounds on the State Complexity of Population Protocols

Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial global configuration satisfies a given property, specified as a predicate on the set of configurations. The state complexity of a predicate is the number of states of a smallest protocol that computes it. Previous work by Blondin \textit{et al.} has shown that the counting predicates $x \geq η$ have state complexity $\mathcal{O}(\log η)$ for leaderless protocols and $\mathcal{O}(\log \log η)$ for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of $x \geq η$ is $Ω(\log\log η)$ for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.

preprint2021arXiv

Running Time Analysis of Broadcast Consensus Protocols

Broadcast consensus protocols (BCPs) are a model of computation, in which anonymous, identical, finite-state agents compute by sending/receiving global broadcasts. BCPs are known to compute all number predicates in $\mathsf{NL}=\mathsf{NSPACE}(\log n)$ where $n$ is the number of agents. They can be considered an extension of the well-established model of population protocols. This paper investigates execution time characteristics of BCPs. We show that every predicate computable by population protocols is computable by a BCP with expected $\mathcal{O}(n \log n)$ interactions, which is asymptotically optimal. We further show that every log-space, randomized Turing machine can be simulated by a BCP with $\mathcal{O}(n \log n \cdot T)$ interactions in expectation, where $T$ is the expected runtime of the Turing machine. This allows us to characterise polynomial-time BCPs as computing exactly the number predicates in $\mathsf{ZPL}$ , i.e. predicates decidable by log-space bounded randomised Turing machine with zero-error in expected polynomial time where the input is encoded as unary.

preprint2020arXiv

Compact Oblivious Routing in Weighted Graphs

The space-requirement for routing-tables is an important characteristic of routing schemes. For the cost-measure of minimizing the total network load there exist a variety of results that show tradeoffs between stretch and required size for the routing tables. This paper designs compact routing schemes for the cost-measure congestion, where the goal is to minimize the maximum relative load of a link in the network (the relative load of a link is its traffic divided by its bandwidth). We show that for arbitrary undirected graphs we can obtain oblivious routing strategies with competitive ratio $\tilde{\mathcal{O}}(1)$ that have header length $\tilde{\mathcal{O}}(1)$ , label size $\tilde{\mathcal{O}}(1)$ , and require routing-tables of size $\tilde{\mathcal{O}}(\operatorname{deg}(v))$ at each vertex $v$ in the graph. This improves a result of Räcke and Schmid who proved a similar result in unweighted graphs.

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.