Sequentially consistent versus linearizable counting networks |
| |
Authors: | Marios Mavronicolas Michael Merritt Gadi Taubenfeld |
| |
Affiliation: | (1) Department of Computer Science, University of Cyprus, 1678 Nicosia, Cyprus;(2) AT&T Labs Research, 180 Park Ave., Florham Park, NJ 07932-0971, USA;(3) Department of Computer Science, The Interdisciplinary Center, P.O. Box 167, Kanfai Nesharim St., 46150 Herzliya, Israel |
| |
Abstract: | We compare the impact of timing conditions on implementing sequentially consistent and linearizable counters using (uniform)
counting networks in distributed systems. For counting problems in application domains which do not require linearizability
but will run correctly if only sequential consistency is provided, the results of our investigation, and their potential payoffs,
are threefold: First, we show that sequential consistency and linearizability cannot be distinguished by the timing conditions
previously considered in the context of counting networks; thus, in contexts where these constraints apply, it is possible
to rely on the stronger semantics of linearizability, which simplifies proofs and enhances compositionality. Second, we identify
local timing conditions that support sequential consistency but not linearizability; thus, we suggest weaker, easily implementable
timing conditions that are likely to be sufficient in many applications. Third, we show that any kind of synchronization that
is too weak to support even sequential consistency may violate it significantly for some counting networks; hence, we identify
timing conditions that are to be totally ruled out for specific applications that rely critically on either sequential consistency
or linearizability.
A preliminary version of this work appears in the Proceedings of the 18th annual ACM symposium on principles of distributed computing (PODC 1999), pp. 133–142, May 1999. This work has been partially supported by the IST Program of the European Union under projects DELIS (contract number 001907) and AEOLUS (contract number 15964). |
| |
Keywords: | Counting networks Balancing networks Sequential consistency Linearizability Inconsistency fractions |
本文献已被 SpringerLink 等数据库收录! |
|