7 Search Results for "Garz�n-Astolfi, Armando"

Document
DOI: 10.4230/DagRep.13.7.34
Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)

Authors: Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid

Published in: Dagstuhl Reports, Volume 13, Issue 7 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23272 "Epistemic and Topological Reasoning in Distributed Systems." The seminar brought together experts in combinatorial topology and epistemic logic interested in distributed systems, with the aim of exploring the directions that the recent interaction between those approaches can take, identifying challenges and opportunities.
Cite as

Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid. Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272). In Dagstuhl Reports, Volume 13, Issue 7, pp. 34-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{castaneda_et_al:DagRep.13.7.34,
  author =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  title =	{{Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)}},
  pages =	{34--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{7},
  editor =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.7.34},
  URN =		{urn:nbn:de:0030-drops-197742},
  doi =		{10.4230/DagRep.13.7.34},
  annote =	{Keywords: combinatorial topology, distributed systems, epistemic logic, multi-agent systems, interpreted systems, dynamic epistemic logic, simplicial semantics, knowledge-based approach, distributed computing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.5
Topological Characterization of Task Solvability in General Models of Computation

Authors: Hagit Attiya, Armando Castañeda, and Thomas Nowak

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
The famous asynchronous computability theorem (ACT) relates the existence of an asynchronous wait-free shared memory protocol for solving a task with the existence of a simplicial map from a subdivision of the simplicial complex representing the inputs to the simplicial complex representing the allowable outputs. The original theorem relies on a correspondence between protocols and simplicial maps in round-structured models of computation that induce a compact topology. This correspondence, however, is far from obvious for computation models that induce a non-compact topology, and indeed previous attempts to extend the ACT have failed. This paper shows that in every non-compact model, protocols solving tasks correspond to simplicial maps that need to be continuous. It first proves a generalized ACT for sub-IIS models, some of which are non-compact, and applies it to the set agreement task. Then it proves that in general models too, protocols are simplicial maps that need to be continuous, hence showing that the topological approach is universal. Finally, it shows that the approach used in ACT that equates protocols and simplicial complexes actually works for every compact model. Our study combines, for the first time, combinatorial and point-set topological aspects of the executions admitted by the computation model.
Cite as

Hagit Attiya, Armando Castañeda, and Thomas Nowak. Topological Characterization of Task Solvability in General Models of Computation. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2023.5,
  author =	{Attiya, Hagit and Casta\~{n}eda, Armando and Nowak, Thomas},
  title =	{{Topological Characterization of Task Solvability in General Models of Computation}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.5},
  URN =		{urn:nbn:de:0030-drops-191315},
  doi =		{10.4230/LIPIcs.DISC.2023.5},
  annote =	{Keywords: task solvability, combinatorial topology, point-set topology}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.6
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-dev.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
DOI: 10.4230/LIPIcs.DISC.2021.16
Fully Read/Write Fence-Free Work-Stealing with Multiplicity

Authors: Armando Castañeda and Miguel Piña

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

Abstract
It is known that any algorithm for work-stealing in the standard asynchronous shared memory model must use expensive Read-After-Write synchronization patterns or atomic Read-Modify-Write instructions. There have been proposed algorithms for relaxations in the standard model and algorithms in restricted models that avoid the impossibility result, but only in some operations. This paper considers work-stealing with multiplicity, a relaxation in which every task is taken by at least one operation, with the requirement that any process can extract a task at most once. Two versions of the relaxation are considered and two fully Read/Write algorithms are presented in the standard asynchronous shared memory model, both devoid of Read-After-Write synchronization patterns in all its operations, the second algorithm additionally being fully fence-free, namely, no specific ordering among the algorithm’s instructions is required, beyond what is implied by data dependence. To our knowledge, these are the first algorithms for work-stealing possessing all these properties. Our algorithms are also wait-free solutions of relaxed versions of single-enqueue multi-dequeuer queues. The algorithms are obtained by reducing work-stealing with multiplicity and weak multiplicity to MaxRegister and RangeMaxRegister, a relaxation of MaxRegister which might be of independent interest. An experimental evaluation shows that our fully fence-free algorithm exhibits better performance than Cilk THE, Chase-Lev and Idempotent Work-Stealing algorithms.
Cite as

Armando Castañeda and Miguel Piña. Fully Read/Write Fence-Free Work-Stealing with Multiplicity. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{castaneda_et_al:LIPIcs.DISC.2021.16,
  author =	{Casta\~{n}eda, Armando and Pi\~{n}a, Miguel},
  title =	{{Fully Read/Write Fence-Free Work-Stealing with Multiplicity}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{16:1--16:20},
  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.16},
  URN =		{urn:nbn:de:0030-drops-148181},
  doi =		{10.4230/LIPIcs.DISC.2021.16},
  annote =	{Keywords: Correctness condition, Linearizability, Nonblocking, Relaxed data type, Set-linearizability, Wait-freedom, Work-stealing}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.13
Relaxed Queues and Stacks from Read/Write Operations

Authors: Armando Castañeda, Sergio Rajsbaum, and Michel Raynal

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Considering asynchronous shared memory systems in which any number of processes may crash, this work identifies and formally defines relaxations of queues and stacks that can be non-blocking or wait-free while being implemented using only read/write operations. Set-linearizability and Interval-linearizability are used to specify the relaxations formally, and precisely identify the subset of executions which preserve the original sequential behavior. The relaxations allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a property multiplicity. The stack implementation is wait-free, while the queue implementation is non-blocking. Interval-linearizability is used to describe a queue with multiplicity, with the additional relaxation that a dequeue operation can return weak-empty, which means that the queue might be empty. We present a read/write wait-free interval-linearizable algorithm of a concurrent queue. As far as we know, this work is the first that provides formalizations of the notions of multiplicity and weak-emptiness, which can be implemented on top of read/write registers only.
Cite as

Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. Relaxed Queues and Stacks from Read/Write Operations. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{castaneda_et_al:LIPIcs.OPODIS.2020.13,
  author =	{Casta\~{n}eda, Armando and Rajsbaum, Sergio and Raynal, Michel},
  title =	{{Relaxed Queues and Stacks from Read/Write Operations}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.13},
  URN =		{urn:nbn:de:0030-drops-134983},
  doi =		{10.4230/LIPIcs.OPODIS.2020.13},
  annote =	{Keywords: Asynchrony, Correctness condition, Linearizability, Nonblocking, Process crash, Relaxed data type, Set-linearizability, Wait-freedom, Work-stealing}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.18
Locally Solvable Tasks and the Limitations of Valency Arguments

Authors: Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, implying that there are no local impossibility proofs for these tasks.
Cite as

Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum. Locally Solvable Tasks and the Limitations of Valency Arguments. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2020.18,
  author =	{Attiya, Hagit and Casta\~{n}eda, Armando and Rajsbaum, Sergio},
  title =	{{Locally Solvable Tasks and the Limitations of Valency Arguments}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.18},
  URN =		{urn:nbn:de:0030-drops-135037},
  doi =		{10.4230/LIPIcs.OPODIS.2020.18},
  annote =	{Keywords: Wait-freedom, Set agreement, Weak symmetry breaking, Impossibility proofs}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2005.658
Analysis of the Parameters of Transfers in Rapid Transit Network Design

Authors: Ricardo García, Armando Garzón-Astolfi, Angel Marín, Juan A. Mesa, and Francisco A. Ortega

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
The rapid transit network design problem consists of the location of train alignments and stations in an urban traffic context. The originality of our study is to incorporate into the location model the decisions about the transportation mode and the route, to be chosen for urban trips. This paper proposes a new design model which includes transfers between train lines. The objective of the model is to maximize the number of expected users in the transit network taking limited budgets into consideration, in addition to location and allocation constraints. Furthermore, the transfer costs are considered in the generalized public costs when the users change lines. Waiting time to take the metro and walking time to transfer is included in the formulation of the costs. The analysis of transfer parameters is carried out using a test network. Some computational experience is included in the paper.
Cite as

Ricardo García, Armando Garzón-Astolfi, Angel Marín, Juan A. Mesa, and Francisco A. Ortega. Analysis of the Parameters of Transfers in Rapid Transit Network Design. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{garcia_et_al:OASIcs.ATMOS.2005.658,
  author =	{Garc{\'\i}a, Ricardo and Garz\'{o}n-Astolfi, Armando and Mar{\'\i}n, Angel and Mesa, Juan A. and Ortega, Francisco A.},
  title =	{{Analysis of the Parameters of Transfers in Rapid Transit Network Design}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.658},
  URN =		{urn:nbn:de:0030-drops-6583},
  doi =		{10.4230/OASIcs.ATMOS.2005.658},
  annote =	{Keywords: Parameter analysis, rapid transit network design, trip choice in urban traffic}
}
  • Refine by Author
  • 5 Castañeda, Armando
  • 2 Attiya, Hagit
  • 2 Rajsbaum, Sergio
  • 1 Alaniz, Robert M.
  • 1 Caballero, David
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Distributed computing models
  • 4 Computing methodologies → Distributed algorithms
  • 3 Computing methodologies → Concurrent algorithms
  • 3 Theory of computation → Concurrent algorithms
  • 3 Theory of computation → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 3 Wait-freedom
  • 2 Correctness condition
  • 2 Linearizability
  • 2 Nonblocking
  • 2 Relaxed data type
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2021
  • 1 2006
  • 1 2022
  • 1 2023
  • 1 2024

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