8 citations · 22 across the 13 of their papers we have counts for
18 papers
Comparing the Update Expressivity of Communication Patterns and Action Models
Armando Castañeda, Hans van Ditmarsch, David A. Rosenblueth +1
Any kind of dynamics in dynamic epistemic logic can be represented as an action model. Right? Wrong! In this contribution we prove that the update expressivity of communication pat…
Topological Characterization of Task Solvability in General Models of Computation
Hagit Attiya, Armando Castañeda, Thomas Nowak
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…
Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability
Armando Castañeda, Gilde Valeria Rodríguez
This paper presents a {theoretical study} of the problem of verifying linearizability at runtime, where one seeks for a concurrent algorithm for verifying that the current executio…
Communication Pattern Logic: Epistemic and Topological Views
Armando Castañeda, Hans van Ditmarsch, David A. Rosenblueth +1
We propose communication pattern logic. A communication pattern describes how processes or agents inform each other, independently of the information content. The full-information…
Modular Baskets Queue
Armando Castañeda, Miguel Piña
A modular version of the baskets queue of Hoffman, Shalev and Shavit is presented. It manipulates the head and tail using a novel object called load-link/increment-conditional, whi…
Communication Pattern Models: An Extension of Action Models for Dynamic-Network Distributed Systems
Diego A. Velázquez, Armando Castañeda, David A. Rosenblueth
Halpern and Moses were the first to recognize, in 1984, the importance of a formal treatment of knowledge in distributed computing. Many works in distributed computing, however, st…
Locally Solvable Tasks and the Limitations of Valency Arguments
Hagit Attiya, Armando Castañeda, Sergio Rajsbaum
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…
Fully Read/Write Fence-Free Work-Stealing with Multiplicity
Armando Castañeda, Miguel Piña
Work-stealing is a popular technique to implement dynamic load balancing in a distributed manner. In this approach, each process owns a set of tasks that have to be executed. The o…
Relaxed Queues and Stacks from Read/Write Operations
Armando Castañeda, Sergio Rajsbaum, Michel Raynal
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 no…
Tasks in Modular Proofs of Concurrent Algorithms
Armando Castañeda, Aurélie Hurault, Philippe Quéinnec +1
Proving correctness of distributed or concurrent algorithms is a mind-challenging and complex process. Slight errors in the reasoning are difficult to find, calling for computer-ch…
A Topological Perspective on Distributed Network Algorithms
Armando Castañeda, Pierre Fraigniaud, Ami Paz +3
More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems…
Some Problems in Compact Message Passing
Armando Castañeda, Jonas Lefèvre, Amitabh Trehan
This paper seeks to address the question of designing distributed algorithms for the setting of compact memory i.e. sublinear bits working memory for arbitrary connected networks.…
Unbeatable Set Consensus via Topological and Combinatorial Reasoning
Armando Castañeda, Yannai A. Gonczarowski, Yoram Moses
The set consensus problem has played an important role in the study of distributed systems for over two decades. Indeed, the search for lower bounds and impossibility results for t…
Compact Routing Messages in Self-Healing Trees
Armando Castaneda, Danny Dolev, Amitabh Trehan
Existing compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started.…
Specifying Concurrent Problems: Beyond Linearizability
Armando Castaneda, Michel Raynal, Sergio Rajsbaum
Tasks and objects are two predominant ways of specifying distributed problems. A task is specified by an input/output relation, defining for each set of processes that may run conc…
Unbeatable Consensus
Armando Castañeda, Yannai A. Gonczarowski, Yoram Moses
The unbeatability of a consensus protocol, introduced by Halpern, Moses and Waarts in 2001, is a stronger notion of optimality than the accepted notion of early stopping protocols.…
Good, Better, Best! - Unbeatable Protocols for Consensus and Set Consensus
Armando Castañeda, Yannai A. Gonczarowski, Yoram Moses
While the very first consensus protocols for the synchronous model were designed to match the worst-case lower bound, deciding in exactly t+1 rounds in all runs, it was soon realiz…
An Equivariance Theorem with Applications to Renaming (Preliminary Version)
Armando Castañeda, Maurice Herlihy, Sergio Rajsbaum
In the renaming problem, each process in a distributed system is issued a unique name from a large name space, and the processes must coordinate with one another to choose unique n…