Arrow Research search

Author name cluster

Faith Ellen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers
2 author rows

Possible papers

15

STOC Conference 2019 Conference Paper

Why extension-based proofs fail

  • Dan Alistarh
  • James Aspnes
  • Faith Ellen
  • Rati Gelashvili
  • Leqi Zhu

It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs , a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k -set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.

Details

FOCS Conference 2013 Conference Paper

A Tight Bound for Set Disjointness in the Message-Passing Model

  • Mark Braverman
  • Faith Ellen
  • Rotem Oshman
  • Toniann Pitassi
  • Vinod Vaikuntanathan

In a multiparty message-passing model of communication, there are k players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in secure multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work [25], [29], [30], strong lower bounds of the form Ω(n·k) were obtained for several functions in the message-passing model; however, a lower bound on the classical set disjointness problem remained elusive. In this paper, we prove a tight lower bound of Ω(n · k) for the set disjointness problem in the message passing model. Our bound is obtained by developing information complexity tools for the message-passing model and proving an information complexity lower bound for set disjointness.

Details

FOCS Conference 2005 Conference Paper

Linear Lower Bounds on Real-World Implementations of Concurrent Objects

  • Faith Ellen
  • Danny Hendler
  • Nir Shavit

This paper proves /spl Omega/(n) lower bounds on the time to perform a single instance of an operation in any implementation of a large class of data structures shared by n processes. For standard data structures such as counters, stacks, and queues, the bound is tight. The implementations considered may apply any deterministic primitives to a base object. No bounds are assumed on either the number of base objects or their size. Time is measured as the number of steps a process performs on base objects and the number of stalls it incurs as a result of contention with other processes.

Details

FOCS Conference 1990 Conference Paper

Permuting

  • Faith Ellen
  • J. Ian Munro
  • Patricio V. Poblete

The fundamental problem of permuting the elements of an array according to some given permutation is addressed. The goal is to perform the permutation quickly using only a polylogarithmic number of bits of extra storage. The main result is an O(n log n)-time, O(log/sup 2/n)-space worst case method. A simpler method is presented for the case in which both the permutation and its inverse can be computed at (amortized) unit cost. This algorithm requires O(n log n) time and O(log n) bits in the worst case. These results are extended to the situation in which a power of the permutation is to be applied. A linear time, O(log n)-bit method is presented for the special case in which the data values are all distinct and are either initially in sorted order or will be when permuted. >

Details