Author name cluster

Eric Ruppert

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.

3 papers

1 author row

STOC Conference 2006 Conference Paper

Time-space tradeoffs for implementations of snapshots

Panagiota Fatourou
Faith Ellen
Eric Ruppert

A snapshot object is an abstraction of the fundamental problem of obtaining a consistent view of the contents of the shared memory in a distributed system while other processes may concurrently update those contents. A snapshot object stores an array of m components and can be accessed by two operations: an UPDATE that changes the value of an individual component and a powerful SCAN that returns the contents of the entire array.This paper proves time-space tradeoffs for fault-tolerant implementations of a snapshot object from registers that support only Read and Write operations. For anonymous implementations (where all processes are programmed identically), we prove that a SCAN requires Ω(n/r) time, where n is the number of processes in the system and r is the number of registers used by the implementation. For the general non-anonymous case, we prove that, for any fixed r, the time required to do a SCAN grows without bound as n increases. These tradeoffs hold even in the case where the snapshot object has just two components.This is the first time a lower bound on the tradeoff between time complexity and the number of registers has been proved for any problem in asynchronous shared-memory systems. We introduce a new tool for proving distributed lower bounds: the notion of a shrinkable execution, from which an adversary can remove portions as necessary.

Details

STOC Conference 2003 Conference Paper

A tight time lower bound for space-optimal implementations of multi-writer snapshots

Panagiota Fatourou
Faith Ellen
Eric Ruppert

A snapshot object consists of a collection of m > 1 components, each capable of storing a value, shared by n processes in an asynchronous shared-memory distributed system. It supports two operations: a process can UPDATE any individual component or atomically SCAN the entire collection to obtain the values of all the components. It is possible to implement a snapshot object using m registers so that each operation takes O(mn) time.In a previous paper, we proved that m registers are necessary to implement a snapshot object with m < n-1 components. Here we prove that, for any such space-optimal implementation, Ω(mn) steps are required to perform a SCAN operation in the worst case, matching the upper bound. We also extend our space and time lower bounds to implementations that use single-writer registers in addition to the multi-writer registers. Specifically, we prove that at least m multi-writer registers are still needed, provided the SCANS do not read a large fraction of the single-writer registers. We also prove that any implementation that uses single-writer registers in addition to $m$ multi-writer registers uses Ω(√mn) steps in the worst case. Our proof yields insight into the structure of any implementation that uses only m multi-writer registers, showing that processes must access the multi-writer registers in a very constrained way.

Details

FOCS Conference 2000 Conference Paper

On the Existence of Booster Types

Maurice Herlihy
Eric Ruppert

A data type's consensus number measures its power in asynchronous concurrent models of computation. We characterize the circumstances under which types of high consensus number can be constructed from types with lower consensus numbers, a process called boosting. In settings where boosting is impossible, we can reason about the synchronization power of objects in isolation. We give a new and simple topological condition, called /spl kappa/-solo-connectivity sufficient to ensure that one-shot types cannot be boosted to consensus number /spl kappa/. The booster type need not be one-shot; it can be arbitrary. We also show that, for /spl kappa/>2, any type that is not /spl kappa/-solo-connected can be boosted to consensus number /spl kappa/. For types that can be boosted, we establish an upper bound on the amount the consensus number can be increased. For finite types, these properties and bounds are computable. For deterministic one-shot types, the /spl kappa/-solo-connectivity property also exactly characterizes the types that have consensus number less than /spl kappa/.

Details