Arrow Research search

Author name cluster

Michael Raskin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
2 author rows

Possible papers

2

Highlights Conference 2024 Conference Abstract

Modular Population Protocols

  • Michael Raskin

Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication opportunities occur nondeterministically, allowing the agents involved to change their states based on each other's states. Population protocols are often studied in terms of reaching a consensus on whether the input configuration satisfied some predicate. A desirable property of a computation model is modularity, the ability to combine existing simpler computations in a straightforward way. In the present paper we present a more general notion of functionality implemented by a population protocol in terms of multisets of inputs and outputs. This notion allows to design multiphase protocols as combinations of independently defined phases. The additional generality also increases the range of behaviours that can be captured in applications (e. g. maintaining the role distribution in a fleet of servers). We show that composition of protocols can be performed in a uniform mechanical way, and that the expressive power is essentially semilinear, similar to the predicate expressive power in the original population protocol setting.

Details

FOCS Conference 2021 Conference Paper

Sharp Thresholds in Random Simple Temporal Graphs

  • Arnaud Casteigts
  • Michael Raskin
  • Malte Renken
  • Viktor Zamaraev

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i. e. , a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdös-Rényi random graph G ~ Gn, p by considering a random permutation π of the edges and interpreting the ranks in π as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that, at p = log $n$ /n, any fixed pair of vertices can a. a. s. reach each other; at 2 log $n$ /n, at least one vertex (and in fact, any fixed vertex) can a. a. s. reach all others; and at 3 log $n$ /n, all the vertices can a. a. s. reach each other, i. e. , the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n + o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n - 4 is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size O(n) in general (Kempe, Kleinberg, Kumar, STOC 2000). In fact, they do not even always admit spanners of size o( $n$ 2 ) (Axiotis, Fotakis, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, any non-negligible obstruction is statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners-i. e. , spanners of size 2n - 2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)-exist a. a. s. at 4 log $n$ / n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n - 4) also exist a. a. s. at p = 4 log $n$ /n, Whether this value is a sharp threshold is open, we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well, and that in some cases, they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson's celebrated results on percolation in weighted graphs.

Details