Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Coordination Avoidance

  • Living reference work entry
  • First Online:
Encyclopedia of Big Data Technologies

  • 538 Accesses

Definitions

Coordination avoidance denotes a class of distributed system methods that minimize the amount of coordination between nodes while maintaining the integrity of the application.

Overview

In many data management systems, data and processing are replicated or distributed across nodes (Kemme et al. 2010; Bernstein and Goodman 1981). This replication and distribution increase the levels of fault tolerance and availability. However, they introduce a coordination cost to maintain the integrity of applications. Since nodes are processing data for the same application simultaneously, there is the possibility of conflicting operations that may overwrite the work of other nodes. To overcome this problem, coordination and synchronization protocols have been developed to ensure the integrity of data. Typically, the coordination protocols strive to ensure a guarantee of correctness, such as serializability (Bernstein et al. 1987) and linearizability (Herlihy and Wing 1990). These are...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

References

  • Agrawal D, Bernstein AJ, Gupta P, Sengupta S (1987) Distributed optimistic concurrency control with reduced rollback. Distrib Comput 2(1):45–59. https://doi.org/10.1007/BF01786254

    Article  Google Scholar 

  • Agrawal D, El Abbadi A, Singh AK (1993) Consistency and orderability: semantics-based correctness criteria for databases. ACM Trans Database Syst (TODS) 18(3):460–486

    Article  Google Scholar 

  • Agrawal D, Bruno JL, El Abbadi A, Krishnaswamy V (1994) Relative serializability (extended abstract): an approach for relaxing the atomicity of transactions. In: Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems. ACM, pp 139–149

    MATH  Google Scholar 

  • Alvaro P, Conway N, Hellerstein JM, Marczak WR (2011) Consistency analysis in bloom: a calm and collected approach. In: CIDR, pp 249–260

    Google Scholar 

  • Badrinath B, Ramamritham K (1992) Semantics-based concurrency control: beyond commutativity. ACM Trans Database Syst (TODS) 17(1):163–199

    Article  Google Scholar 

  • Bailis P, Ghodsi A (2013) Eventual consistency today: limitations, extensions, and beyond. Queue 11(3):20:20–20:32. https://doi.org/10.1145/2460276.2462076

  • Bailis P, Ghodsi A, Hellerstein JM, Stoica I (2013) Bolt-on causal consistency. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data, SIGMOD’13. ACM, New York, pp 761–772. https://doi.org/10.1145/2463676.2465279

    Chapter  Google Scholar 

  • Bailis P, Fekete A, Franklin MJ, Ghodsi A, Hellerstein JM, Stoica I (2014) Coordination avoidance in database systems. Proc VLDB Endow 8(3):185–196

    Article  Google Scholar 

  • Berenson H, Bernstein P, Gray J, Melton J, O’Neil E, O’Neil P (1995) A critique of ansi SQL isolation levels. ACM SIGMOD Rec 24:1–10. https://doi.org/10.1145/223784.223785

    Article  Google Scholar 

  • Bernstein PA, Goodman N (1981) Concurrency control in distributed database systems. ACM Comput Surv (CSUR) 13(2):185–221

    Article  MathSciNet  Google Scholar 

  • Bernstein PA, Hadzilacos V, Goodman N (1987) Concurrency control and recovery in database systems. Addison-Wesley, Reading

    Google Scholar 

  • Cooper BF, Ramakrishnan R, Srivastava U, Silberstein A, Bohannon P, Jacobsen HA, Puz N, Weaver D, Yerneni R (2008) Pnuts: Yahoo!’s hosted data serving platform. Proc VLDB Endow 1(2):1277–1288. https://doi.org/10.14778/1454159.1454167

    Article  Google Scholar 

  • Corbett JC, Dean J, Epstein M, Fikes A, Frost C, Furman JJ, Ghemawat S, Gubarev A, Heiser C, Hochschild P, Hsieh W, Kanthak S, Kogan E, Li H, Lloyd A, Melnik S, Mwaura D, Nagle D, Quinlan S, Rao R, Rolig L, Saito Y, Szymaniak M, Taylor C, Wang R, Woodford D (2012) Spanner: Google’s globally-distributed database, pp 251–264. http://dl.acm.org/citation.cfm?id=2387880.2387905

  • DeCandia G, Hastorun D, Jampani M, Kakulapati G, Lakshman A, Pilchin A, Sivasubramanian S, Vosshall P, Vogels W (2007) Dynamo: Amazon’s highly available key-value store. In: Proceedings of twenty-first ACM SIGOPS symposium on operating systems principles, SOSP’07. ACM, New York, pp 205–220. https://doi.org/10.1145/1294261.1294281

    Chapter  Google Scholar 

  • Du J, Elnikety S, Roy A, Zwaenepoel W (2013) Orbe: scalable causal consistency using dependency matrices and physical clocks. In: Proceedings of the 4th annual symposium on cloud computing, SOCC’13. ACM, New York, pp 11:1–11:14. https://doi.org/10.1145/2523616.2523628

  • Farrag AA, Özsu MT (1989) Using semantic knowledge of transactions to increase concurrency. ACM Trans Database Syst (TODS) 14(4):503–525

    Article  Google Scholar 

  • Garcia-Molina H (1983) Using semantic knowledge for transaction processing in a distributed database. ACM Trans Database Syst (TODS) 8(2):186–213

    Article  MATH  Google Scholar 

  • Herlihy MP, Wing JM (1990) Linearizability: a correctness condition for concurrent objects. ACM Trans Program Lang Syst 12(3):463–492. https://doi.org/10.1145/78969.78972

    Article  Google Scholar 

  • Kemme B, Jimenez-Peris R, Patino-Martinez M (2010) Database replication. Synth Lect Data Manag 2(1):1–153. http://www.morganclaypool.com/doi/abs/10.2200/S00296ED1V01Y201008DTM007

    Article  MATH  Google Scholar 

  • Korth HF (1983) Locking primitives in a database system. J ACM 30(1):55–79. https://doi.org/10.1145/322358.322363

    Article  MathSciNet  MATH  Google Scholar 

  • Korth HK, Speegle G (1988) Formal model of correctness without serializabilty. ACM SIGMOD Rec 17:379–386

    Article  Google Scholar 

  • Lamport L (1976) Towards a theory of correctness for multi-user data base system. Teeh. Rep. Tech. Rep., TRCA-7610-0712, Massachusetts Computer Associates

    Google Scholar 

  • Lamport L (1978) Time, clocks, and the ordering of events in a distributed system. Commun ACM 21(7):558–565. https://doi.org/10.1145/359545.359563

    Article  MATH  Google Scholar 

  • Li C, Porto D, Clement A, Gehrke J, Preguiça NM, Rodrigues R (2012) Making geo-replicated systems fast as possible, consistent when necessary. In: OSDI, vol 12, pp 265–278

    Google Scholar 

  • Lloyd W, Freedman MJ, Kaminsky M, Andersen DG (2011) Don’t settle for eventual: scalable causal consistency for wide-area storage with cops. In: Proceedings of the twenty-third ACM symposium on operating systems principles, SOSP’11. ACM, New York, pp 401–416. https://doi.org/10.1145/2043556.2043593

    Chapter  Google Scholar 

  • Lloyd W, Freedman MJ, Kaminsky M, Andersen DG (2013) Stronger semantics for low-latency geo-replicated storage. In: Proceedings of the 10th USENIX conference on networked systems design and implementation, NSDI’13. USENIX Association, Berkeley, pp 313–328. http://dl.acm.org/citation.cfm?id=2482626.2482657

    Google Scholar 

  • Lynch NA (1983) Multilevel atomicity: a new correctness criterion for database concurrency control. ACM Trans Database Syst (TODS) 8(4):484–502

    Article  MathSciNet  MATH  Google Scholar 

  • Nawab F, Arora V, Agrawal D, El Abbadi A (2015) Chariots: a scalable shared log for data management in multi-datacenter cloud environments. In: Proceedings of the 18th international conference on extending database technology, EDBT 2015, Brussels, pp 13–24. https://doi.org/10.5441/002/edbt.2015.03

  • Preguica N, Marques JM, Shapiro M, Letia M (2009) A commutative replicated data type for cooperative editing. In: 29th IEEE international conference on distributed computing systems, ICDCS’09. IEEE, pp 395–403

    Google Scholar 

  • Roy S, Kot L, Bender G, Ding B, Hojjat H, Koch C, Foster N, Gehrke J (2015) The homeostasis protocol: avoiding transaction coordination through program analysis. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data. ACM, pp 1311–1326

    Google Scholar 

  • Satyanarayanan OT, Agrawal D (1993) Efficient execution of read-only transactions in replicated multiversion databases. IEEE Trans Knowl Data Eng 5(5):859–871. https://doi.org/10.1109/69.243514

    Article  Google Scholar 

  • Schlageter G (1981) Optimistic methods for concurrency control in distributed database systems. In: Proceedings of the seventh international conference on very large data bases, vol 7, VLDB Endowment, VLDB’81, pp 125–130. http://dl.acm.org/citation.cfm?id=1286831.1286844

  • Shapiro M, Preguiça N, Baquero C, Zawirski M (2011) Convergent and commutative replicated data types. Bull Eur Assoc Theor Comput Sci (104):67–88

    MathSciNet  MATH  Google Scholar 

  • Shasha D, Llirbat F, Simon E, Valduriez P (1995) Transaction chopping: algorithms and performance studies. ACM Trans Database Syst (TODS) 20(3):325–363

    Article  Google Scholar 

  • Sovran Y, Power R, Aguilera MK, Li J (2011) Transactional storage for geo-replicated systems. In: Proceedings of the twenty-third ACM symposium on operating systems principles, SOSP’11. ACM, New York, pp 385–400. https://doi.org/10.1145/2043556.2043592

    Chapter  Google Scholar 

  • Weikum G (1985) A theoretical foundation of multi-level concurrency control. In: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on principles of database systems. ACM, pp 31–43

    Google Scholar 

  • Zhang Y, Power R, Zhou S, Sovran Y, Aguilera MK, Li J (2013) Transaction chains: achieving serializability with low latency in geo-distributed storage systems. In: Proceedings of the twenty-fourth ACM symposium on operating systems principles, SOSP’13. ACM, New York, pp 276–291. https://doi.org/10.1145/2517349.2522729

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California, Santa Cruz, CA, USA

    Faisal Nawab

Authors
  1. Faisal Nawab
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Faisal Nawab .

Editor information

Editors and Affiliations

  1. School of Comp. Sci. and Engineering, University of New South Wales School of Comp. Sci. and Engineering, Eveleigh, New South Wales, Australia

    Sherif Sakr

  2. Sch of Info Techno, Building J12, University of Sydney Sch of Info Techno, Building J12, Sydney, Australia

    Albert Zomaya

Section Editor information

  1. No affiliation provided

    Mohammad Sadoghi

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Nawab, F. (2018). Coordination Avoidance. In: Sakr, S., Zomaya, A. (eds) Encyclopedia of Big Data Technologies. Springer, Cham. https://doi.org/10.1007/978-3-319-63962-8_182-1

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-63962-8_182-1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-63962-8

  • Online ISBN: 978-3-319-63962-8

  • eBook Packages: Springer Reference MathematicsReference Module Computer Science and Engineering

Publish with us

Policies and ethics

Search

Navigation