Arrow Research search

Author name cluster

Alex Shvartsman

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.

2 papers
1 author row

Possible papers

2

TCS Journal 1999 Journal Article

Eventually-serializable data services

  • Alan Fekete
  • David Gupta
  • Victor Luchangco
  • Nancy Lynch
  • Alex Shvartsman

Data replication is used in distributed systems to improve availability, increase throughput and eliminate single points of failures. The cost of replication is that significant care and communication is required to maintain consistency among replicas. In some settings, such as distributed directory services, it is acceptable to have transient inconsistencies, in exhange for better performance, as long as a consistent view of the data is eventually established. For such services to be usable, it is important that the consistency guarantees are specified clearly. We present a new specification for distributed data services that trades off immediate consistency guarantees for improved system availability and efficiency, while ensuring the long-term consistency of the data. An eventually-serializable data service maintains the requested operations in a partial order that gravitates over time towards a total order. It provides clear and unambiguous guarantees about the immediate and long-term behavior of the system. We also present an algorithm, based on the lazy replication strategy of Ladin, Liskov, Shrira, and Ghemawat (1992), that implements this specification. Our algorithm provides the external interface of the eventually-serializable data service specification, and generalizes their algorithm by allowing arbitrary operations and greater flexibility in specifying consistency requirements. In addition to correctness, we prove performance and fault-tolerance properties of this algorithm.

Details DOI

TCS Journal 1999 Journal Article

Timing conditions for linearizability in uniform counting networks

  • Nancy Lynch
  • Nir Shavit
  • Alex Shvartsman
  • Dan Touitou

Counting networks are concurrent data structures that serve as building blocks in the design of highly scalable concurrent data structures in a way that eliminates sequential bottlenecks and contention. Linearizable counting networks assure that the order of the values returned by the network reflects the real-time order in which they were requested. Linearizability is an important consistency condition for concurrent data structures, as it simplifies proofs and enhances compositionality. Though most counting networks are not linearizable, this paper presents a precise characterization of the timing conditions under which uniform non-linearizable networks exhibit linearizable behavior. Uniformity is a common structuring property of almost all published counting networks: a uniform network is made of “balancers” and “wires” so that each balancer lies on some path from inputs to outputs, and all paths from inputs to outputs have equal lengths. Our results include the following simple condition: if the time it takes a slow token to traverse a “wire” or “balancer” is no more than twice that of a fast token, the network is linearizable. Surprisingly, the timing measure in this condition is local to the individual “wires” and “balancers” of the network, that is, it is independent of network depth. We use our timing measure to mathematically explain our empirical findings: that in a variety of highly concurrent execution scenarios tested on a simulated shared memory multiprocessor, the Bitonic counting networks of Aspnes, Herlihy, and Shavit exhibit completely linearizable behavior, and when linearizability is violated, the percentage of violations is relatively small. Herlihy, Shavit, and Waarts have shown that counting networks that achieve linearizability under all circumstances must pay the penalty of linear time latency. Our results suggest that for systems in which timing anomalies occur infrequently, such linear delays may be an unnecessary burden on applications that are willing to incur occasional non-linearizability.

Details DOI
v2026.09.13