Scalable eventually consistent counters over unreliable networks

DOI10.1007/S00446-017-0322-2MaRDI QIDQ1733394zbMATH OpenOpenAlexFDO

Authors Paulo Sérgio Almeida, Carlos Baquero

Publication date 21 March 2019

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.3207, http://hdl.handle.net/1822/53777

zbMATH Keywords

eventual consistencyconflict-free replicated data typesdistributed counters

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Abstract: Counters are an important abstraction in distributed computing, and play a central role in large scale geo-replicated systems, counting events such as web page impressions or social network "likes". Classic distributed counters, strongly consistent, cannot be made both available and partition-tolerant, due to the CAP Theorem, being unsuitable to large scale scenarios. This paper defines Eventually Consistent Distributed Counters (ECDC) and presents an implementation of the concept, Handoff Counters, that is scalable and works over unreliable networks. By giving up the sequencer aspect of classic distributed counters, ECDC implementations can be made AP in the CAP design space, while retaining the essence of counting. Handoff Counters are the first CRDT (Conflict-free Replicated Data Type) based mechanism that overcomes the identity explosion problem in naive CRDTs, such as G-Counters (where state size is linear in the number of independent actors that ever incremented the counter), by managing identities towards avoiding global propagation and garbage collecting temporary entries. The approach used in Handoff Counters is not restricted to counters, being more generally applicable to other data types with associative and commutative operations.

Recommendations

• Scalable Byzantine reliable broadcast
• Distributed counting along lossy paths without feedback
• An inherent bottleneck in distributed counting
• Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures
• Scalable synchronization of clocks in distributed environments
• Counting protocols for reliable end-to-end transmission
• Consensus Computation in Unreliable Networks: A System Theoretic Approach
• Accuracy of message counting abstraction in fault-tolerant distributed algorithms
• Tolerating Random Byzantine Failures in an Unbounded Network

Cites work

• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• Connection management without retaining information
• Convergent and commutative replicated data types
• Counting networks
• The counting pyramid: an adaptive distributed counting scheme
• The impossibility of implementing reliable communication in the face of crashes

Cited in

(3)

• Eventual consistency for CRDTs
• Counting protocols for reliable end-to-end transmission
• An inherent bottleneck in distributed counting

Describes a project that uses

Uses Software

• Dynamo
• Cassandra

This page was built for publication: Scalable eventually consistent counters over unreliable networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1733394)