Faith Ellen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Faith Ellen has a total of 34 co-authors. Here are the top co-authors by number of shared publications:
- Joan Boyar
Department of Mathematics and Computer Science, University of Southern Denmark, Odense M, Denmark
4 shared publications - Leqi Zhu
University of Toronto
4 shared publications - Rati Gelashvili
University of Toronto
4 shared publications Leqi Zhu
University of Manitoba, Winnipeg R3T 2N2, MB, Canada
3 shared publications- Hagit Attiya
Technion - Israel institute of technology, Haifa, Israel
2 shared publications - Kim S. Larsen
Department of Mathematics and Computer Science, University of Southern Denmark, Odense M, Denmark
2 shared publications
Latest Publications
- Open Access
- 19 October 2026
- Published by Elsevier in Information and Computation
- Vol. 313
Distributed graph algorithms with predictions
- 19 October 2026
- Published by Elsevier in Information and Computation
- Vol. 313
Open AccessDistributed graph algorithms with predictions
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 3-14
Byzantine Agreement with Predictions
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 3-14
Open AccessByzantine Agreement with Predictions
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 322-325
Brief Announcement: Distributed Graph Algorithms with Predictions
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 322-325
Open AccessBrief Announcement: Distributed Graph Algorithms with Predictions
- 1 August 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 53 (4) , 1039-1084
Revisionist Simulations: A New Approach to Proving Space Lower Bounds
Determining the number of registers required for solving obstruction-free (or randomized wait-free) [Formula: see text]-set agreement is an open problem that highlights important gaps in our understanding of the space complexity of synchronization. The best known upper bound on the number of registers needed to solve this problem among [Formula: see text] processes is [Formula: see text] registers. No general lower bound better than 2 was known. We prove that any obstruction-free protocol solving [Formula: see text]-set agreement among [Formula: see text] processes must use at least [Formula: see text] registers. In particular, we get a tight lower bound of exactly [Formula: see text] registers for solving obstruction-free and randomized wait-free consensus. Our main tool is a simulation that serves as a reduction from the impossibility of deterministic wait-free [Formula: see text]-set agreement. In particular, we show that if an obstruction-free protocol for [Formula: see text]-set agreement uses fewer registers, then it is possible for [Formula: see text] processes to simulate the protocol and deterministically solve [Formula: see text]-set agreement in a wait-free manner, which is impossible. An important aspect of the simulation is the ability of simulating processes to revise the past of simulated processes. We introduce an augmented snapshot object, which facilitates this. More generally, our simulation applies to the broad class of colorless tasks. We can use it to prove, for example, a lower bound on the number of registers needed to solve obstruction-free [Formula: see text]-approximate agreement, which matches the best known upper bound to within a factor of 2 when [Formula: see text] is sufficiently small. No general lower bound for this problem was known. Finally, we prove that any lower bound on the number of registers used by obstruction-free protocols applies to protocols that satisfy nondeterministic solo-termination. Hence, our lower bounds for obstruction-free protocols also hold for randomized wait-free protocols.
- 1 August 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 53 (4) , 1039-1084
Revisionist Simulations: A New Approach to Proving Space Lower Bounds
Determining the number of registers required for solving obstruction-free (or randomized wait-free) [Formula: see text]-set agreement is an open problem that highlights important gaps in our understanding of the space complexity of synchronization. The best known upper bound on the number of registers needed to solve this problem among [Formula: see text] processes is [Formula: see text] registers. No general lower bound better than 2 was known. We prove that any obstruction-free protocol solving [Formula: see text]-set agreement among [Formula: see text] processes must use at least [Formula: see text] registers. In particular, we get a tight lower bound of exactly [Formula: see text] registers for solving obstruction-free and randomized wait-free consensus. Our main tool is a simulation that serves as a reduction from the impossibility of deterministic wait-free [Formula: see text]-set agreement. In particular, we show that if an obstruction-free protocol for [Formula: see text]-set agreement uses fewer registers, then it is possible for [Formula: see text] processes to simulate the protocol and deterministically solve [Formula: see text]-set agreement in a wait-free manner, which is impossible. An important aspect of the simulation is the ability of simulating processes to revise the past of simulated processes. We introduce an augmented snapshot object, which facilitates this. More generally, our simulation applies to the broad class of colorless tasks. We can use it to prove, for example, a lower bound on the number of registers needed to solve obstruction-free [Formula: see text]-approximate agreement, which matches the best known upper bound to within a factor of 2 when [Formula: see text] is sufficiently small. No general lower bound for this problem was known. Finally, we prove that any lower bound on the number of registers used by obstruction-free protocols applies to protocols that satisfy nondeterministic solo-termination. Hence, our lower bounds for obstruction-free protocols also hold for randomized wait-free protocols.
- 25 July 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 52 (4) , 913-944
Why Extension-Based Proofs Fail
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve [Formula: see text]-set agreement among [Formula: see text] processes or approximate agreement on a cycle of length 4 among [Formula: see text] processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power.
- 25 July 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 52 (4) , 913-944
Why Extension-Based Proofs Fail
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve [Formula: see text]-set agreement among [Formula: see text] processes or approximate agreement on a cycle of length 4 among [Formula: see text] processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power.
- Open Access
Why Extension-Based Proofs Fail
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k > 1 processes in a wait-free manner in certain asynchronous models. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained for one of these models by an extension-based proof and, hence, extension-based proofs are limited in power.
Open AccessWhy Extension-Based Proofs Fail
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k > 1 processes in a wait-free manner in certain asynchronous models. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained for one of these models by an extension-based proof and, hence, extension-based proofs are limited in power.
- Open Access
- 20 July 2020
- Published by Springer Nature in Theory of Computing Systems
- Vol. 65 (4) , 687-705
Space Lower Bounds for the Signal Detection Problem
Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated by this problem, we define the signal detection problem, which can be studied on a purely combinatorial level. Consider a system with n + 1 processes consisting of n readers and one signaller. The processes communicate through a shared blackboard that can store a value from a domain of size m. Processes are scheduled by an adversary. When scheduled, a process reads the blackboard, modifies its contents arbitrarily, and, provided it is a reader, returns a Boolean value. A reader must return true if the signaller has taken a step since the reader’s preceding step; otherwise it must return false. Intuitively, in a system with n processes, signal detection should require at least n bits of shared information, i.e., m ≥ 2n. But a proof of this conjecture remains elusive. For the general case, we prove a lower bound of m ≥ n2. For restricted versions of the problem, where the processes are oblivious or where the signaller must write a fixed sequence of values, we prove a tight lower bound of m ≥ 2n. We also consider a version of the problem where each reader takes at most two steps. In this case, we prove that m = n + 1 blackboard values are necessary and sufficient.
- 20 July 2020
- Published by Springer Nature in Theory of Computing Systems
- Vol. 65 (4) , 687-705
Open AccessSpace Lower Bounds for the Signal Detection Problem
Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated by this problem, we define the signal detection problem, which can be studied on a purely combinatorial level. Consider a system with n + 1 processes consisting of n readers and one signaller. The processes communicate through a shared blackboard that can store a value from a domain of size m. Processes are scheduled by an adversary. When scheduled, a process reads the blackboard, modifies its contents arbitrarily, and, provided it is a reader, returns a Boolean value. A reader must return true if the signaller has taken a step since the reader’s preceding step; otherwise it must return false. Intuitively, in a system with n processes, signal detection should require at least n bits of shared information, i.e., m ≥ 2n. But a proof of this conjecture remains elusive. For the general case, we prove a lower bound of m ≥ n2. For restricted versions of the problem, where the processes are oblivious or where the signaller must write a fixed sequence of values, we prove a tight lower bound of m ≥ 2n. We also consider a version of the problem where each reader takes at most two steps. In this case, we prove that m = n + 1 blackboard values are necessary and sufficient.
- Open Access
Constant-Length Labeling Schemes for Deterministic Radio Broadcast
Broadcast is one of the fundamental network communication primitives. One node of a network, called the $\mathit{source}$, has a message that has to be learned by all other nodes. We consider the feasibility of deterministic broadcast in radio networks. If nodes of the network do not have any labels, deterministic broadcast is impossible even in the four-cycle. On the other hand, if all nodes have distinct labels, then broadcast can be carried out, e.g., in a round-robin fashion, and hence $O(\log n)$-bit labels are sufficient for this task in $n$-node networks. In fact, $O(\log \Delta)$-bit labels, where $\Delta$ is the maximum degree, are enough to broadcast successfully. Hence, it is natural to ask if very short labels are sufficient for broadcast. Our main result is a positive answer to this question. We show that every radio network can be labeled using 2 bits in such a way that broadcast can be accomplished by some universal deterministic algorithm that does not know the network topology nor any bound on its size. Moreover, at the expense of an extra bit in the labels, we get the additional strong property that there exists a common round in which all nodes know that broadcast has been completed. Finally, we show that 3-bit labels are also sufficient to solve both versions of broadcast in the case where the labeling scheme does not know which node is the source.Open AccessConstant-Length Labeling Schemes for Deterministic Radio Broadcast
Broadcast is one of the fundamental network communication primitives. One node of a network, called the $\mathit{source}$, has a message that has to be learned by all other nodes. We consider the feasibility of deterministic broadcast in radio networks. If nodes of the network do not have any labels, deterministic broadcast is impossible even in the four-cycle. On the other hand, if all nodes have distinct labels, then broadcast can be carried out, e.g., in a round-robin fashion, and hence $O(\log n)$-bit labels are sufficient for this task in $n$-node networks. In fact, $O(\log \Delta)$-bit labels, where $\Delta$ is the maximum degree, are enough to broadcast successfully. Hence, it is natural to ask if very short labels are sufficient for broadcast. Our main result is a positive answer to this question. We show that every radio network can be labeled using 2 bits in such a way that broadcast can be accomplished by some universal deterministic algorithm that does not know the network topology nor any bound on its size. Moreover, at the expense of an extra bit in the labels, we get the additional strong property that there exists a common round in which all nodes know that broadcast has been completed. Finally, we show that 3-bit labels are also sufficient to solve both versions of broadcast in the case where the labeling scheme does not know which node is the source. - 30 April 2019
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 30 (03) , 375-405
Tight Bounds for Restricted Grid Scheduling
- 30 April 2019
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 30 (03) , 375-405
Tight Bounds for Restricted Grid Scheduling