76 Search Results for "Aspnes, James"


Volume

LIPIcs, Volume 221

1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

SAND 2022, March 28-30, 2022, Virtual Conference

Editors: James Aspnes and Othon Michail

Volume

LIPIcs, Volume 95

21st International Conference on Principles of Distributed Systems (OPODIS 2017)

OPODIS 2017, December 18-20, 2017, Lisbon, Portugal

Editors: James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão

Document
Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure

Authors: Gal Amram, Avi Hayoun, Lior Mizrahi, and Gera Weiss

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
We analyze correctness of implementations of the snapshot data structure in terms of linearizability. We show that such implementations can be verified in polynomial time. Additionally, we identify a set of representative executions for testing and show that the correctness of each of these executions can be validated in linear time. These results present a significant speedup considering that verifying linearizability of implementations of concurrent data structures, in general, is EXPSPACE-complete in the number of program-states, and testing linearizability is NP-complete in the length of the tested execution. The crux of our approach is identifying a class of executions, which we call simple, such that a snapshot implementation is linearizable if and only if all of its simple executions are linearizable. We then divide all possible non-linearizable simple executions into three categories and construct a small automaton that recognizes each category. We describe two implementations (one for verification and one for testing) of an automata-based approach that we develop based on this result and an evaluation that demonstrates significant improvements over existing tools. For verification, we show that restricting a state-of-the-art tool to analyzing only simple executions saves resources and allows the analysis of more complex cases. Specifically, restricting attention to simple executions finds bugs in 27 instances, whereas, without this restriction, we were only able to find 14 of the 30 bugs in the instances we examined. We also show that our technique accelerates testing performance significantly. Specifically, our implementation solves the complete set of 900 problems we generated, whereas the state-of-the-art linearizability testing tool solves only 554 problems.

Cite as

Gal Amram, Avi Hayoun, Lior Mizrahi, and Gera Weiss. Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{amram_et_al:LIPIcs.DISC.2022.5,
  author =	{Amram, Gal and Hayoun, Avi and Mizrahi, Lior and Weiss, Gera},
  title =	{{Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.5},
  URN =		{urn:nbn:de:0030-drops-171964},
  doi =		{10.4230/LIPIcs.DISC.2022.5},
  annote =	{Keywords: Snapshot, Linearizability, Verification, Formal Methods}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
Parameterized Safety Verification of Round-Based Shared-Memory Systems

Authors: Nathalie Bertrand, Nicolas Markey, Ocan Sankur, and Nicolas Waldburger

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We consider the parameterized verification problem for distributed algorithms where the goal is to develop techniques to prove the correctness of a given algorithm regardless of the number of participating processes. Motivated by an asynchronous binary consensus algorithm [James Aspnes, 2002], we consider round-based distributed algorithms communicating with shared memory. A particular challenge in these systems is that 1) the number of processes is unbounded, and, more importantly, 2) there is a fresh set of registers at each round. A verification algorithm thus needs to manage both sources of infinity. In this setting, we prove that the safety verification problem, which consists in deciding whether all possible executions avoid a given error state, is PSPACE-complete. For negative instances of the safety verification problem, we also provide exponential lower and upper bounds on the minimal number of processes needed for an error execution and on the minimal round on which the error state can be covered.

Cite as

Nathalie Bertrand, Nicolas Markey, Ocan Sankur, and Nicolas Waldburger. Parameterized Safety Verification of Round-Based Shared-Memory Systems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 113:1-113:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bertrand_et_al:LIPIcs.ICALP.2022.113,
  author =	{Bertrand, Nathalie and Markey, Nicolas and Sankur, Ocan and Waldburger, Nicolas},
  title =	{{Parameterized Safety Verification of Round-Based Shared-Memory Systems}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{113:1--113:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.113},
  URN =		{urn:nbn:de:0030-drops-164541},
  doi =		{10.4230/LIPIcs.ICALP.2022.113},
  annote =	{Keywords: Verification, Parameterized models, Distributed algorithms}
}
Document
Complete Volume
LIPIcs, Volume 221, SAND 2022, Complete Volume

Authors: James Aspnes and Othon Michail

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
LIPIcs, Volume 221, SAND 2022, Complete Volume

Cite as

James Aspnes and Othon Michail. LIPIcs, Volume 221, SAND 2022, Complete Volume. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 1-370, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Proceedings{aspnes_et_al:LIPIcs.SAND.2022,
  title =	{{LIPIcs, Volume 221, SAND 2022, Complete Volume}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{1--370},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022},
  URN =		{urn:nbn:de:0030-drops-159412},
  doi =		{10.4230/LIPIcs.SAND.2022},
  annote =	{Keywords: LIPIcs, Volume 221, SAND 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: James Aspnes and Othon Michail

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

James Aspnes and Othon Michail. Front Matter, Table of Contents, Preface, Conference Organization. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 0:i-0:xvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.SAND.2022.0,
  author =	{Aspnes, James and Michail, Othon},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.0},
  URN =		{urn:nbn:de:0030-drops-159426},
  doi =		{10.4230/LIPIcs.SAND.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Algorithmic Problems on Temporal Graphs (Invited Talk)

Authors: Paul G. Spirakis

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
Research on Temporal Graphs has expanded in the last few years. Most of the results till now, address problems related to the notion of Temporal Paths (and Temporal Connectivity). In this talk, we focus, instead, on problems whose main topic is not on Temporal Paths. In particular, we will discuss Temporal Vertex Covers, the notion of Temporal Transitivity, and also issues and models of stochastic temporal graphs. We believe that several algorithmic graph problems, not directly related to paths, can be raised in the temporal domain. This may motivate new research towards lifting more topics of algorithmic graph theory to the temporal case.

Cite as

Paul G. Spirakis. Algorithmic Problems on Temporal Graphs (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{spirakis:LIPIcs.SAND.2022.2,
  author =	{Spirakis, Paul G.},
  title =	{{Algorithmic Problems on Temporal Graphs}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.2},
  URN =		{urn:nbn:de:0030-drops-159446},
  doi =		{10.4230/LIPIcs.SAND.2022.2},
  annote =	{Keywords: Temporal graph, stochastic temporal graph, vertex cover, temporal transitivity}
}
Document
Invited Talk
Networks, Dynamics, Algorithms, and Learning (Invited Talk)

Authors: Roger Wattenhofer

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
Networks are notoriously difficult to understand, and adding dynamics does not help. Can the current wonder weapon of computation (yes, machine learning) come to the rescue? Unfortunately, learning with networks is generally not well understood. "Neural network networks" (better and less confusingly known as graph neural networks) can learn simple graph patterns, but they are a far cry from their impressive machine learning cousins in the image- or the game-domain. In my opinion, the most astonishing graph neural networks are in fact dealing with dynamic networks: They simulate sand (the granular material, not the symposium) quite naturally. In my talk, I will discuss and compare different computational objects and paradigms: networks, dynamics, algorithms, and learning. What are the differences? And what can they learn from each other? In the technical part of the talk, I will present DropGNN, our new algorithm-inspired approach for handling graph neural networks. But mostly I will vent about misunderstandings and mistakes, and I will propose open questions, and new research directions. DropGNN is joint work with Pál András Papp, Karolis Martinkus, and Lukas Faber, published at NeurIPS, December 2021.

Cite as

Roger Wattenhofer. Networks, Dynamics, Algorithms, and Learning (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{wattenhofer:LIPIcs.SAND.2022.3,
  author =	{Wattenhofer, Roger},
  title =	{{Networks, Dynamics, Algorithms, and Learning}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.3},
  URN =		{urn:nbn:de:0030-drops-159451},
  doi =		{10.4230/LIPIcs.SAND.2022.3},
  annote =	{Keywords: graph neural networks}
}
Document
Atomic Splittable Flow Over Time Games

Authors: Antonia Adamik and Leon Sering

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
In an atomic splittable flow over time game, finitely many players route flow dynamically through a network, in which edges are equipped with transit times, specifying the traversing time, and with capacities, restricting flow rates. Infinitesimally small flow particles controlled by the same player arrive at a constant rate at the player’s origin and the player’s goal is to maximize the flow volume that arrives at the player’s destination within a given time horizon. Here, the flow dynamics are described by the deterministic queuing model, i.e., flow of different players merges perfectly, but excessive flow has to wait in a queue in front of the bottle-neck. In order to determine Nash equilibria in such games, the main challenge is to consider suitable definitions for the players' strategies, which depend on the level of information the players receive throughout the game. For the most restricted version, in which the players receive no information on the network state at all, we can show that there is no Nash equilibrium in general, not even for networks with only two edges. However, if the current edge congestions are provided over time, the players can adapt their route choices dynamically. We show that a profile of those strategies always lead to a unique feasible flow over time. Hence, those atomic splittable flow over time games are well-defined. For parallel-edge networks Nash equilibria exists and the total flow arriving in time equals the value of a maximum flow over time leading to a price of anarchy of 1.

Cite as

Antonia Adamik and Leon Sering. Atomic Splittable Flow Over Time Games. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 4:1-4:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{adamik_et_al:LIPIcs.SAND.2022.4,
  author =	{Adamik, Antonia and Sering, Leon},
  title =	{{Atomic Splittable Flow Over Time Games}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.4},
  URN =		{urn:nbn:de:0030-drops-159462},
  doi =		{10.4230/LIPIcs.SAND.2022.4},
  annote =	{Keywords: Flows Over Time, Deterministic Queuing, Atomic Splittable Games, Equilibria, Traffic, Cooperation}
}
Document
Faster Exploration of Some Temporal Graphs

Authors: Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
A temporal graph G = (G_1, G_2, ..., G_T) is a graph represented by a sequence of T graphs over a common set of vertices, such that at the i-th time step only the edge set E_i is active. The temporal graph exploration problem asks for a shortest temporal walk on some temporal graph visiting every vertex. We show that temporal graphs with n vertices can be explored in O(k n^{1.5} log n) days if the underlying graph has treewidth k and in O(n^{1.75} log n) days if the underlying graph is planar. Furthermore, we show that any temporal graph whose underlying graph is a cycle with k chords can be explored in at most 6kn days. Finally, we demonstrate that there are temporal realisations of sub cubic planar graphs that cannot be explored faster than in Ω(n log n) days. All these improve best known results in the literature.

Cite as

Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster Exploration of Some Temporal Graphs. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 5:1-5:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{adamson_et_al:LIPIcs.SAND.2022.5,
  author =	{Adamson, Duncan and Gusev, Vladimir V. and Malyshev, Dmitriy and Zamaraev, Viktor},
  title =	{{Faster Exploration of Some Temporal Graphs}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.5},
  URN =		{urn:nbn:de:0030-drops-159475},
  doi =		{10.4230/LIPIcs.SAND.2022.5},
  annote =	{Keywords: Temporal Graphs, Graph Exploration}
}
Document
Building Squares with Optimal State Complexity in Restricted Active Self-Assembly

Authors: Robert M. Alaniz, David Caballero, Sonya C. Cirlos, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, Armando Tenorio, and Tim Wylie

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
Tile Automata is a recently defined model of self-assembly that borrows many concepts from cellular automata to create active self-assembling systems where changes may be occurring within an assembly without requiring attachment. This model has been shown to be powerful, but many fundamental questions have yet to be explored. Here, we study the state complexity of assembling n × n squares in seeded Tile Automata systems where growth starts from a seed and tiles may attach one at a time, similar to the abstract Tile Assembly Model. We provide optimal bounds for three classes of seeded Tile Automata systems (all without detachment), which vary in the amount of complexity allowed in the transition rules. We show that, in general, seeded Tile Automata systems require Θ(log^{1/4} n) states. For Single-Transition systems, where only one state may change in a transition rule, we show a bound of Θ(log^{1/3} n), and for deterministic systems, where each pair of states may only have one associated transition rule, a bound of Θ(({log n}/{log log n})^{1/2}).

Cite as

Robert M. Alaniz, David Caballero, Sonya C. Cirlos, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, Armando Tenorio, and Tim Wylie. Building Squares with Optimal State Complexity in Restricted Active Self-Assembly. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 6:1-6:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{alaniz_et_al:LIPIcs.SAND.2022.6,
  author =	{Alaniz, Robert M. and Caballero, David and Cirlos, Sonya C. and Gomez, Timothy and Grizzell, Elise and Rodriguez, Andrew and Schweller, Robert and Tenorio, Armando and Wylie, Tim},
  title =	{{Building Squares with Optimal State Complexity in Restricted Active Self-Assembly}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.6},
  URN =		{urn:nbn:de:0030-drops-159482},
  doi =		{10.4230/LIPIcs.SAND.2022.6},
  annote =	{Keywords: Active Self-Assembly, State Complexity, Tile Automata}
}
Document
Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem

Authors: Petra Berenbrink, Felix Biermeier, Christopher Hahn, and Dominik Kaaser

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
We present a loosely-stabilizing phase clock for population protocols. In the population model we are given a system of n identical agents which interact in a sequence of randomly chosen pairs. Our phase clock is leaderless and it requires O(log n) states. It runs forever and is, at any point of time, in a synchronous state w.h.p. When started in an arbitrary configuration, it recovers rapidly and enters a synchronous configuration within O(n log n) interactions w.h.p. Once the clock is synchronized, it stays in a synchronous configuration for at least poly(n) parallel time w.h.p. We use our clock to design a loosely-stabilizing protocol that solves the adaptive variant of the majority problem. We assume that the agents have either opinion A or B or they are undecided and agents can change their opinion at a rate of 1/n. The goal is to keep track which of the two opinions is (momentarily) the majority. We show that if the majority has a support of at least Ω(log n) agents and a sufficiently large bias is present, then the protocol converges to a correct output within O(n log n) interactions and stays in a correct configuration for poly(n) interactions, w.h.p.

Cite as

Petra Berenbrink, Felix Biermeier, Christopher Hahn, and Dominik Kaaser. Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 7:1-7:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:LIPIcs.SAND.2022.7,
  author =	{Berenbrink, Petra and Biermeier, Felix and Hahn, Christopher and Kaaser, Dominik},
  title =	{{Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.7},
  URN =		{urn:nbn:de:0030-drops-159493},
  doi =		{10.4230/LIPIcs.SAND.2022.7},
  annote =	{Keywords: Population Protocols, Phase Clocks, Loose Self-stabilization, Clock Synchronization, Majority, Adaptive}
}
Document
Complexity of Verification in Self-Assembly with Prebuilt Assemblies

Authors: David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
We analyze the complexity of two fundamental verification problems within a generalization of the two-handed tile self-assembly model (2HAM) where initial system assemblies are not restricted to be singleton tiles, but may be larger pre-built assemblies. Within this model we consider the producibility problem, which asks if a given tile system builds, or produces, a given assembly, and the unique assembly verification (UAV) problem, which asks if a given system uniquely produces a given assembly. We show that producibility is NP-complete and UAV is coNP^{NP}-complete even when the initial assembly size and temperature threshold are both bounded by a constant. This is in stark contrast to results in the standard model with singleton input tiles where producibility is in P and UAV is in coNP for 𝒪(1) bounded temperature and coNP-complete when temperature is part of the input. We further provide preliminary results for producibility and UAV in the case of 1-dimensional linear assemblies with pre-built assemblies, and provide polynomial time solutions.

Cite as

David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie. Complexity of Verification in Self-Assembly with Prebuilt Assemblies. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 8:1-8:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{caballero_et_al:LIPIcs.SAND.2022.8,
  author =	{Caballero, David and Gomez, Timothy and Schweller, Robert and Wylie, Tim},
  title =	{{Complexity of Verification in Self-Assembly with Prebuilt Assemblies}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.8},
  URN =		{urn:nbn:de:0030-drops-159503},
  doi =		{10.4230/LIPIcs.SAND.2022.8},
  annote =	{Keywords: 2-handed assembly, verification, prebuilt}
}
Document
Robustness of Distances and Diameter in a Fragile Network

Authors: Arnaud Casteigts, Timothée Corsini, Hervé Hocquard, and Arnaud Labourel

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
A property of a graph G is robust if it remains unchanged in all connected spanning subgraphs of G. This form of robustness is motivated by networking contexts where some links eventually fail permanently, and the network keeps being used so long as it is connected. It is then natural to ask how certain properties of the network may be impacted as the network deteriorates. In this paper, we focus on two particular properties, which are the diameter, and pairwise distances among nodes. Surprisingly, the complexities of deciding whether these properties are robust are quite different: deciding the robustness of the diameter is coNP-complete, whereas deciding the robustness of the distance between two given nodes has a linear time complexity. This is counterintuitive, because the diameter consists of the maximum distance over all pairs of nodes, thus one may expect that the robustness of the diameter reduces to testing the robustness of pairwise distances. On the technical side, the difficulty of the diameter is established through a reduction from hamiltonian paths. The linear time algorithm for deciding robustness of the distance relies on a new characterization of two-terminal series-parallel graphs (TTSPs) in terms of excluded rooted minor, which may be of independent interest.

Cite as

Arnaud Casteigts, Timothée Corsini, Hervé Hocquard, and Arnaud Labourel. Robustness of Distances and Diameter in a Fragile Network. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.SAND.2022.9,
  author =	{Casteigts, Arnaud and Corsini, Timoth\'{e}e and Hocquard, Herv\'{e} and Labourel, Arnaud},
  title =	{{Robustness of Distances and Diameter in a Fragile Network}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.9},
  URN =		{urn:nbn:de:0030-drops-159514},
  doi =		{10.4230/LIPIcs.SAND.2022.9},
  annote =	{Keywords: Dynamic networks, Longest path, Series-parallel graphs, Rooted minors}
}
Document
Computing Outside the Box: Average Consensus over Dynamic Networks

Authors: Bernadette Charron-Bost and Patrick Lambein-Monette

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
Networked systems of autonomous agents, and applications thereof, often rely on the control primitive of average consensus, where the agents are to compute the average of private initial values. To provide reliable services that are easy to deploy, average consensus should continue to operate when the network is subject to frequent and unpredictable change, and should mobilize few computational resources, so that deterministic, low powered, and anonymous agents can partake in the network. In this stringent adversarial context, we investigate the implementation of average consensus by distributed algorithms over networks with bidirectional, but potentially short-lived, communication links. Inspired by convex recurrence rules for multi-agent systems, and the Metropolis average consensus rule in particular, we design a deterministic distributed algorithm that achieves asymptotic average consensus, which we show to operate in polynomial time in a synchronous temporal model. The algorithm is easy to implement, has low space and computational complexity, and is fully distributed, requiring neither symmetry-breaking devices like unique identifiers, nor global control or knowledge of the network. In the fully decentralized model that we adopt, to our knowledge, no other distributed average consensus algorithm has a better temporal complexity. Our approach distinguishes itself from classical convex recurrence rules in that the agent’s values may sometimes leave their previous convex hull. As a consequence, our convergence bound requires a subtle analysis, despite the syntactic simplicity of our algorithm.

Cite as

Bernadette Charron-Bost and Patrick Lambein-Monette. Computing Outside the Box: Average Consensus over Dynamic Networks. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 10:1-10:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.SAND.2022.10,
  author =	{Charron-Bost, Bernadette and Lambein-Monette, Patrick},
  title =	{{Computing Outside the Box: Average Consensus over Dynamic Networks}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.10},
  URN =		{urn:nbn:de:0030-drops-159521},
  doi =		{10.4230/LIPIcs.SAND.2022.10},
  annote =	{Keywords: average consensus, dynamic networks, distributed algorithms, iterated averaging, Metropolis}
}
  • Refine by Author
  • 9 Aspnes, James
  • 3 Attiya, Hagit
  • 3 Bessani, Alysson
  • 3 Doty, David
  • 3 Esparza, Javier
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Distributed algorithms
  • 5 Theory of computation → Distributed computing models
  • 5 Theory of computation → Graph algorithms analysis
  • 4 Theory of computation
  • 3 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 5 population protocols
  • 3 Distributed Systems
  • 3 distributed algorithms
  • 3 distributed computing
  • 3 dynamic networks
  • Show More...

  • Refine by Type
  • 74 document
  • 2 volume

  • Refine by Publication Year
  • 36 2018
  • 29 2022
  • 3 2014
  • 3 2019
  • 2 2021
  • Show More...

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