70 Search Results for "Richa, Andr�a"

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.7
Energy-Constrained Programmable Matter Under Unfair Adversaries

Authors: Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Individual modules of programmable matter participate in their system’s collective behavior by expending energy to perform actions. However, not all modules may have access to the external energy source powering the system, necessitating a local and distributed strategy for supplying energy to modules. In this work, we present a general energy distribution framework for the canonical amoebot model of programmable matter that transforms energy-agnostic algorithms into energy-constrained ones with equivalent behavior and an 𝒪(n²)-round runtime overhead - even under an unfair adversary - provided the original algorithms satisfy certain conventions. We then prove that existing amoebot algorithms for leader election (ICDCN 2023) and shape formation (Distributed Computing, 2023) are compatible with this framework and show simulations of their energy-constrained counterparts, demonstrating how other unfair algorithms can be generalized to the energy-constrained setting with relatively little effort. Finally, we show that our energy distribution framework can be composed with the concurrency control framework for amoebot algorithms (Distributed Computing, 2023), allowing algorithm designers to focus on the simpler energy-agnostic, sequential setting but gain the general applicability of energy-constrained, asynchronous correctness.
Cite as

Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude. Energy-Constrained Programmable Matter Under Unfair Adversaries. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{weber_et_al:LIPIcs.OPODIS.2023.7,
  author =	{Weber, Jamison W. and Chhabra, Tishya and Richa, Andr\'{e}a W. and Daymude, Joshua J.},
  title =	{{Energy-Constrained Programmable Matter Under Unfair Adversaries}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.7},
  URN =		{urn:nbn:de:0030-drops-194971},
  doi =		{10.4230/LIPIcs.OPODIS.2023.7},
  annote =	{Keywords: Programmable matter, amoebot model, energy distribution, concurrency}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.6
Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks

Authors: Shunhao Oh, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents reside on graph vertices, where each stimulus is only recognized locally, and agents communicate via token passing along edges to alert other agents to transition to an Aware state when stimuli are present and an Unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. We would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response.
Cite as

Shunhao Oh, Dana Randall, and Andréa W. Richa. Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SAND.2023.6,
  author =	{Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.6},
  URN =		{urn:nbn:de:0030-drops-179424},
  doi =		{10.4230/LIPIcs.SAND.2023.6},
  annote =	{Keywords: Dynamic networks, adaptive stimuli, foraging, self-organizing particle systems, programmable matter}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.51
Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes

Authors: Shunhao Oh, Dana Randall, and Andréa W. Richa

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

Abstract
The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave.
Cite as

Shunhao Oh, Dana Randall, and Andréa W. Richa. Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.DISC.2022.51,
  author =	{Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{51:1--51:3},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.51},
  URN =		{urn:nbn:de:0030-drops-172423},
  doi =		{10.4230/LIPIcs.DISC.2022.51},
  annote =	{Keywords: Foraging, self-organized particle systems, compression, phase changes}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.SWAT.2022.3
Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper)

Authors: Mikkel Thorup

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We consider the numerical taxonomy problem of fitting an S× S distance matrix D with a tree metric T. Here T is a weighted tree spanning S where the path lengths in T induce a metric on S. If there is a tree metric matching D exactly, then it is easily found. If there is no exact match, then for some k, we want to minimize the L_k norm of the errors, that is, pick T so as to minimize ‖D-T‖_k = (∑_{i,j ∈ S} |D(i,j)-T(i,j)|^k) ^{1/k}. This problem was raised in biology in the 1960s for k = 1,2. The biological interpretation is that T represents a possible evolution behind the species in S matching some measured distances in D. Sometimes, it is required that T is an ultrametric, meaning that all species are at the same distance from the root. An evolutionary tree induces a hierarchical classification of species and this is not just tied to biology. Medicine, ecology and linguistics are just some of the fields where this concept appears, and it is even an integral part of machine learning and data science. Fundamentally, if we can approximate distances with a tree, then they are much easier to reason about: many questions that are NP-hard for general metrics can be answered in linear time on tree metrics. In fact, humans have appreciated hierarchical classifications at least since Plato and Aristotle (350 BC). The numerical taxonomy problem is important in practice and many heuristics have been proposed. In this talk we will review the basic algorithmic theory, results and techniques, for the problem, including the most recent result from FOCS'21 [Vincent Cohen-Addad et al., 2021]. They paint a varied landscape with big differences between different moments, and with some very nice open problems remaining. - At STOC'93, Farach, Kannan, and Warnow [Martin Farach et al., 1995] proved that under L_∞, we can find the optimal ultrametric. Almost all other variants of the problem are APX-hard. - At SODA'96, Agarwala, Bafna, Farach, Paterson, and Thorup [Richa Agarwala et al., 1999] showed that for any norm L_k, k ≥ 1, if the best ultrametric can be α-approximated, then the best tree metric can be 3α-approximated. In particular, this implied a 3-approximation for tree metrics under L_∞. - At FOCS'05, Ailon and Charikar [Nir Ailon and Moses Charikar, 2011] showed that for any L_k, k ≥ 1, we can get an approximation factor of O(((log n)(log log n))^{1/k}) for both tree and ultrametrics. Their paper was focused on the L₁ norm, and they wrote "Determining whether an O(1) approximation can be obtained is a fascinating question". - At FOCS'21, Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup [Vincent Cohen-Addad et al., 2021] showed that indeed a constant factor is possible for L₁ for both tree and ultrametrics. This uses the special structure of L₁ in relation to hierarchies. - The status of L_k is wide open for 1 < k < ∞. All we know is that the approximation factor is between Ω(1) and O((log n)(log log n)).
Cite as

Mikkel Thorup. Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper). In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{thorup:LIPIcs.SWAT.2022.3,
  author =	{Thorup, Mikkel},
  title =	{{Reconstructing the Tree of Life (Fitting Distances by Tree Metrics)}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{3:1--3:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.3},
  URN =		{urn:nbn:de:0030-drops-161631},
  doi =		{10.4230/LIPIcs.SWAT.2022.3},
  annote =	{Keywords: Numerical taxonomy, computational phylogenetics, hierarchical clustering}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.12
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

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

Abstract
Mutual exclusion is a classical problem in distributed computing that provides isolation among concurrent action executions that may require access to the same shared resources. Inspired by algorithmic research on distributed systems of weakly capable entities whose connections change over time, we address the local mutual exclusion problem that tasks each node with acquiring exclusive locks for itself and the maximal subset of its "persistent" neighbors that remain connected to it over the time interval of the lock request. Using the established time-varying graphs model to capture adversarial topological changes, we propose and rigorously analyze a local mutual exclusion algorithm for nodes that are anonymous and communicate via asynchronous message passing. The algorithm satisfies mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1) under both semi-synchronous and asynchronous concurrency. It requires 𝒪(Δ) memory per node and messages of size Θ(1), where Δ is the maximum number of connections per node. We conclude by describing how our algorithm can implement the pairwise interactions assumed by population protocols and the concurrency control operations assumed by the canonical amoebot model, demonstrating its utility in both passively and actively dynamic distributed systems.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.SAND.2022.12,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{12:1--12:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.12},
  URN =		{urn:nbn:de:0030-drops-159545},
  doi =		{10.4230/LIPIcs.SAND.2022.12},
  annote =	{Keywords: Mutual exclusion, dynamic networks, message passing, concurrency}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.20
The Canonical Amoebot Model: Algorithms and Concurrency Control

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction (SPAA 2014), a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. Using hexagon formation as a case study, we first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The Canonical Amoebot Model: Algorithms and Concurrency Control. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.DISC.2021.20,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{The Canonical Amoebot Model: Algorithms and Concurrency Control}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.20},
  URN =		{urn:nbn:de:0030-drops-148227},
  doi =		{10.4230/LIPIcs.DISC.2021.20},
  annote =	{Keywords: Programmable matter, self-organization, distributed algorithms, concurrency}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.54
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems

Authors: Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16) that can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.
Cite as

Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cannon_et_al:LIPIcs.APPROX-RANDOM.2019.54,
  author =	{Cannon, Sarah and Daymude, Joshua J. and G\"{o}kmen, Cem and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{54:1--54:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  URN =		{urn:nbn:de:0030-drops-112696},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  annote =	{Keywords: Markov chains, Programmable matter, Cluster expansion}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.DISC.2017
LIPIcs, Volume 91, DISC'17, Complete Volume

Authors: Andréa W. Richa

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

Abstract
LIPIcs, Volume 91, DISC'17, Complete Volume
Cite as

31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{richa:LIPIcs.DISC.2017,
  title =	{{LIPIcs, Volume 91, DISC'17, Complete Volume}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017},
  URN =		{urn:nbn:de:0030-drops-80247},
  doi =		{10.4230/LIPIcs.DISC.2017},
  annote =	{Keywords: Computer-Communication Networks, Distributed Systems, Concurrent Programming, Data Structures, Theory of Computation, Models of Computation, Modes of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.DISC.2017.0
Front Matter, Table of Contents, Preface, Symposium Organization, Awards

Authors: Andréa Richa

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

Abstract
Front Matter, Table of Contents, Preface, Symposium Organization, 2017 Edsger W. Dijkstra Prize in Distributed Computing, and 2017 Principles of Distributed Computing Doctoral Dissertation Award.
Cite as

31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{richa:LIPIcs.DISC.2017.0,
  author =	{Richa, Andr\'{e}a},
  title =	{{Front Matter, Table of Contents, Preface, Symposium Organization, Awards}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{0:i--0:xviii},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.0},
  URN =		{urn:nbn:de:0030-drops-79629},
  doi =		{10.4230/LIPIcs.DISC.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Symposium Organization, Edsger W. Dijkstra Prize in Distributed Computing, Principles of Distributed Computi}
}
Document
Keynote Talk
DOI: 10.4230/LIPIcs.DISC.2017.1
Blockchain Consensus Protocols in the Wild (Keynote Talk)

Authors: Christian Cachin and Marko Vukolic

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

Abstract
A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.
Cite as

Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.DISC.2017.1,
  author =	{Cachin, Christian and Vukolic, Marko},
  title =	{{Blockchain Consensus Protocols in the Wild}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{1:1--1:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.1},
  URN =		{urn:nbn:de:0030-drops-80160},
  doi =		{10.4230/LIPIcs.DISC.2017.1},
  annote =	{Keywords: Permissioned blockchains, consensus, Byzantine fault-tolerance, snake oil, protocol analysis}
}
Document
Keynote Talk
DOI: 10.4230/LIPIcs.DISC.2017.2
Recommenders: from the Lab to the Wild (Keynote Talk)

Authors: Anne-Marie Kermarrec

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

Abstract
Recommenders are ubiquitous on the Internet today: they tell you which book to read, which movie you should watch, predict your next holiday destination, give you advices on restaurants and hotels, they are even responsible for the posts that you see on your favorite social media and potentially greatly influence your friendship on social networks. While many approaches exist, collaborative filtering is one of the most popular approaches to build online recommenders that provide users with content that matches their interest. Interestingly, the very notion of users can be general and span actual humans or software applications. Recommenders come with many challenges beyond the quality of the recommendations. One of the most prominent ones is their ability to scale to a large number of users and a growing volume of data to provide real-time recommendations introducing many system challenges. Another challenge is related to privacy awareness: while recommenders rely on the very fact that users give away information about themselves, this potentially raises some privacy concerns. In this talk, I will focus on the challenges associated to building efficient, scalable and privacy-aware recommenders.
Cite as

Anne-Marie Kermarrec. Recommenders: from the Lab to the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kermarrec:LIPIcs.DISC.2017.2,
  author =	{Kermarrec, Anne-Marie},
  title =	{{Recommenders: from the Lab to the Wild}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{2:1--2:1},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.2},
  URN =		{urn:nbn:de:0030-drops-79652},
  doi =		{10.4230/LIPIcs.DISC.2017.2},
  annote =	{Keywords: Recommenders, Collaborative filtering, Distributed systems}
}
Document
Keynote Talk
DOI: 10.4230/LIPIcs.DISC.2017.3
Phase Transitions and Emergent Phenomena in Random Structures and Algorithms (Keynote Talk)

Authors: Dana Randall

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

Abstract
Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large sets of configurations. The idea is to perform a random walk among the configurations so that even though only a very small part of the space is visited, samples will be drawn from a desirable distribution. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose, building on insights from statistical physics. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they change from being efficient to inefficient as some parameter of the system is modified, also revealing interesting properties of the underlying random structures. We will explore how phase transitions can provide valuable insights in three settings. First, they allow us to understand the limitations of certain classes of sampling algorithms, potentially leading to faster alternative approaches. Second, they reveal statistical properties of stationary distributions, giving insight into various interacting models. Example include colloids, or binary mixtures of molecules, segregation models, where individuals are more likely move when they are unhappy with their local demographics, and interacting particle systems from statistical physics. Last, they predict emergent phenomena that can be harnessed for the design of distributed algorithms for certain asynchronous models of programmable active matter. We will see how these three research threads are closely interrelated and inform one another. The talk will take a random walk through some of the results included in the references.
Cite as

Dana Randall. Phase Transitions and Emergent Phenomena in Random Structures and Algorithms (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{randall:LIPIcs.DISC.2017.3,
  author =	{Randall, Dana},
  title =	{{Phase Transitions and Emergent Phenomena in Random Structures and Algorithms}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{3:1--3:2},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.3},
  URN =		{urn:nbn:de:0030-drops-80212},
  doi =		{10.4230/LIPIcs.DISC.2017.3},
  annote =	{Keywords: Markov chains, phase transitions, sampling, emergent phenomena, programmable matter}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.4
Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors

Authors: Maya Arbel-Raviv and Trevor Brown

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

Abstract
In many lock-free algorithms, threads help one another, and each operation creates a descriptor that describes how other threads should help it. Allocating and reclaiming descriptors introduces significant space and time overhead. We introduce the first descriptor abstract data type (ADT), which captures the usage of descriptors by lock-free algorithms. We then develop a weak descriptor ADT which has weaker semantics, but can be implemented significantly more efficiently. We show how a large class of lock-free algorithms can be transformed to use weak descriptors, and demonstrate our technique by transforming several algorithms, including the leading k-compare-and-swap (k-CAS) algorithm. The original k-CAS algorithm allocates at least k+1 new descriptors per k-CAS. In contrast, our implementation allocates two descriptors per process, and each process simply reuses its two descriptors. Experiments on a variety of workloads show significant performance improvements over implementations that reclaim descriptors, and reductions of up to three orders of magnitude in peak memory usage.
Cite as

Maya Arbel-Raviv and Trevor Brown. Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arbelraviv_et_al:LIPIcs.DISC.2017.4,
  author =	{Arbel-Raviv, Maya and Brown, Trevor},
  title =	{{Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{4:1--4:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.4},
  URN =		{urn:nbn:de:0030-drops-80092},
  doi =		{10.4230/LIPIcs.DISC.2017.4},
  annote =	{Keywords: Concurrency, data structures, lock-free, synchronization, descriptors}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.5
Demand-Aware Network Designs of Bounded Degree

Authors: Chen Avin, Kaushik Mondal, and Stefan Schmid

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

Abstract
Traditionally, networks such as datacenter interconnects are designed to optimize worst-case performance under arbitrary traffic patterns. Such network designs can however be far from optimal when considering the actual workloads and traffic patterns which they serve. This insight led to the development of demand-aware datacenter interconnects which can be reconfigured depending on the workload. Motivated by these trends, this paper initiates the algorithmic study of demand-aware networks (DANs), and in particular the design of bounded-degree networks. The inputs to the network design problem are a discrete communication request distribution, D, defined over communicating pairs from the node set V, and a bound, d, on the maximum degree. In turn, our objective is to design an (undirected) demand-aware network N = (V,E) of bounded-degree d, which provides short routing paths between frequently communicating nodes distributed across N. In particular, the designed network should minimize the expected path length on N (with respect to D), which is a basic measure of the efficiency of the network. We show that this fundamental network design problem exhibits interesting connections to several classic combinatorial problems and to information theory. We derive a general lower bound based on the entropy of the communication pattern D, and present asymptotically optimal network-aware design algorithms for important distribution families, such as sparse distributions and distributions of locally bounded doubling dimensions.
Cite as

Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-Aware Network Designs of Bounded Degree. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{avin_et_al:LIPIcs.DISC.2017.5,
  author =	{Avin, Chen and Mondal, Kaushik and Schmid, Stefan},
  title =	{{Demand-Aware Network Designs of Bounded Degree}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{5:1--5:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.5},
  URN =		{urn:nbn:de:0030-drops-80153},
  doi =		{10.4230/LIPIcs.DISC.2017.5},
  annote =	{Keywords: Network design, reconfigurable networks, datacenter topology, peer-topeer computing, entropy, sparse spanners}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.6
Certification of Compact Low-Stretch Routing Schemes

Authors: Alkida Balliu and Pierre Fraigniaud

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

Abstract
On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g., blocking the delivery of messages between some pairs of nodes, without being detected by any node. In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. In particular, we show how to locally verify the stretch 3 routing scheme by Thorup and Zwick [SPAA 2001] by adding certificates of ~O(sqrt(n)) bits at each node in n-node networks, that is, by keeping the memory size of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size ~O(sqrt(n)) bits. This new routing scheme can be locally verified using certificates on ~O(sqrt(n)) bits. Its stretch is 3 if using handshaking, and 5 otherwise.
Cite as

Alkida Balliu and Pierre Fraigniaud. Certification of Compact Low-Stretch Routing Schemes. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2017.6,
  author =	{Balliu, Alkida and Fraigniaud, Pierre},
  title =	{{Certification of Compact Low-Stretch Routing Schemes}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{6:1--6:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.6},
  URN =		{urn:nbn:de:0030-drops-79807},
  doi =		{10.4230/LIPIcs.DISC.2017.6},
  annote =	{Keywords: Distributed verification, compact routing, local computing}
}
  • Refine by Author
  • 8 Richa, Andréa W.
  • 5 Ghaffari, Mohsen
  • 4 Daymude, Joshua J.
  • 4 Parter, Merav
  • 4 Randall, Dana
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Self-organization
  • 3 Theory of computation → Random walks and Markov chains
  • 2 Theory of computation → Concurrency
  • 2 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Stochastic processes
  • Show More...

  • Refine by Keyword
  • 4 Markov chains
  • 4 programmable matter
  • 3 Distributed Graph Algorithms
  • 3 Programmable matter
  • 3 concurrency
  • Show More...

  • Refine by Type
  • 70 document

  • Refine by Publication Year
  • 61 2017
  • 3 2022
  • 2 2016
  • 1 2019
  • 1 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact