User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Saturn: A Distributed Metadata Service for Causal Consistency

Primary tabs

download
  • Open access
  • PDF
  • 602.99 K
Van Roy, Peter [UCL] Bravo Gestoso, Angel [UCL]

We provide a lightweight decentralized publishsubscribe framework for supporting large-scale actor communication on edge networks. Our framework, called Loquat, does not depend on any reliable central nodes (e.g., data centers), provides reliability in the face of massive node failures and network partitioning, and provides scalability as the number of nodes increases. We consider that high reliability, i.e., that send operations reach close to 100% of live destination nodes, is a critical property for communication frameworks on edge networks. But reliability is difficult to achieve in a scalable way on edge networks because of the network’s dynamicity, i.e., frequent node failures and partitioning. For example, both Internet of Things networks and mobile phone networks consist of devices that are often offline. To achieve reliability, our framework is based on two hybrid gossip algorithms, namely HyParView and Plumtree. Hybrid gossip algorithms combine gossip with other distributed algorithms to achieve both efficiency and high resilience. Our current implementation is written in Erlang and has demonstrated scalability up to 1024 nodes in Amazon’s cloud computing environment.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès libre
Publication date 2017
Language Anglais
Conference "EuroSys 2017 Conference", Belgrade, Serbia (du 23/04/2017 au 26/04/2017)
Peer reviewed yes
Publication status Publié
Affiliation UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Keywords large-scale ; network partitioning ; scalability ; communication frameworks ; high resilience
Links
  1. Zawirski Marek, Preguiça Nuno, Duarte Sérgio, Bieniusa Annette, Balegas Valter, Shapiro Marc, Write Fast, Read in the Past : Causal Consistency for Client-Side Applications, 10.1145/2814576.2814733
  2. Viswanath Bimal, Mislove Alan, Cha Meeyoung, Gummadi Krishna P., On the evolution of user interaction in Facebook, 10.1145/1592665.1592675
  3. R. Van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation, OSDI '04, 2004.
  4. Terry D.B., Demers A.J., Petersen K., Spreitzer M.J., Theimer M.M., Welch B.B., Session guarantees for weakly consistent replicated data, 10.1109/pdis.1994.331722
  5. Sovran Yair, Power Russell, Aguilera Marcos K., Li Jinyang, Transactional storage for geo-replicated systems, 10.1145/2043556.2043592
  6. Schneider Fred B., Implementing fault-tolerant services using the state machine approach: a tutorial, 10.1145/98163.98167
  7. Schneider Fred B., Byzantine generals in action: implementing fail-stop processors, 10.1145/190.357399
  8. Pujol Josep M., Erramilli Vijay, Siganos Georgos, Yang Xiaoyuan, Laoutaris Nikos, Chhabra Parminder, Rodriguez Pablo, The little engine(s) that could : scaling online social networks, 10.1145/1851182.1851227
  9. Petersen Karin, Spreitzer Mike J., Terry Douglas B., Theimer Marvin M., Demers Alan J., Flexible update propagation for weakly consistent replication, 10.1145/268998.266711
  10. OscaR Team. OscaR: Scala in OR. https://bitbucket.org/oscarlib/oscar.
  11. NTP. The network time protocol. http://www.ntp.org.
  12. S. A. Mehdi, C. Littley, N. Crooks, L. Alvisi, N. Bronson, and W. Lloyd. I can't believe it's not causal! In Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation, NSDI '17, 2017.
  13. P. Mahajan, L. Alvisi, and M. Dahlin. Consistency, availability, and convergence. Technical Report TR-11-21, University of Texas at Austin, Austin, Texas, 2011.
  14. W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Stronger semantics for low-latency geo-replicated storage. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, NSDI '13, pages 313--328, 2013.
  15. Lloyd Wyatt, Freedman Michael J., Kaminsky Michael, Andersen David G., Don't settle for eventual : scalable causal consistency for wide-area storage with COPS, 10.1145/2043556.2043593
  16. C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI '12, pages 265--278, 2012.
  17. Lamport Leslie, Time, clocks, and the ordering of events in a distributed system, 10.1145/359545.359563
  18. Ladin Rivka, Liskov Barbara, Shrira Liuba, Ghemawat Sanjay, Providing high availability using lazy replication, 10.1145/138873.138877
  19. Karp Richard M., Reducibility among Combinatorial Problems, Complexity of Computer Computations (1972) ISBN:9781468420036 p.85-103, 10.1007/978-1-4684-2001-2_9
  20. Jain Sushant, Zhu Min, Zolla Jon, Hölzle Urs, Stuart Stephen, Vahdat Amin, Kumar Alok, Mandal Subhasree, Ong Joon, Poutievski Leon, Singh Arjun, Venkata Subbaiah, Wanderer Jim, Zhou Junlan, B4 : experience with a globally-deployed software defined wan, 10.1145/2486001.2486019
  21. Herlihy Maurice P., Wing Jeannette M., Linearizability: a correctness condition for concurrent objects, 10.1145/78969.78972
  22. C. Gunawardhana, M. Bravo, and L. Rodrigues. Unobtrusive deferred update stabilization for efficient geo-replication. Arxiv preprint arXiv:1702.01786, Feb. 2017.
  23. R. Guerraoui, M. Pavlovic, and D.-A. Seredinschi. Trade-offs in replicated systems. IEEE Data Engineering Bulletin, 39: 14--26, 2016.
  24. Guerraoui Rachid, Schiper André, Genuine atomic multicast in asynchronous distributed systems, 10.1016/s0304-3975(99)00161-9
  25. Greenberg Albert, Hamilton James R., Jain Navendu, Kandula Srikanth, Kim Changhoon, Lahiri Parantap, Maltz David A., Patel Parveen, Sengupta Sudipta, VL2 : a scalable and flexible data center network, 10.1145/1592568.1592576
  26. Gilbert Seth, Lynch Nancy, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, 10.1145/564585.564601
  27. Escriva Robert, Dubey Ayush, Wong Bernard, Sirer Emin Gün, Kronos : the design and implementation of an event ordering service, 10.1145/2592798.2592822
  28. Du Jiaqing, Iorgulescu Călin, Roy Amitabha, Zwaenepoel Willy, GentleRain : Cheap and Scalable Causal Consistency with Physical Clocks, 10.1145/2670979.2670983
  29. Du Jiaqing, Elnikety Sameh, Roy Amitabha, Zwaenepoel Willy, Orbe : scalable causal consistency using dependency matrices and physical clocks, 10.1145/2523616.2523628
  30. M. Dahlin, L. Gao, A. Nayate, A. Venkataramana, P. Yalagandula, and J. Zheng. Practi replication. In Proceedings of the 3rd USENIX Symposium on Networked Systems Design and Implementation, NSDI '06, 2006.
  31. J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google's globally-distributed database. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, pages 251--264, Hollywood, CA, USA, 2012.
  32. Cheriton David R., Skeen Dale, Understanding the limitations of causally and totally ordered communication, 10.1145/168619.168623
  33. Charron-Bost Bernadette, Concerning the size of logical clocks in distributed systems, 10.1016/0020-0190(91)90055-m
  34. M. Castro and B. Liskov. Practical byzantine fault tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, OSDI '99, pages 173--186, New Orleans, Louisiana, USA, 1999.
  35. Brodersen Anders, Scellato Salvatore, Wattenhofer Mirjam, YouTube around the world : geographic popularity of videos, 10.1145/2187836.2187870
  36. E. A. Brewer. Towards robust distributed systems. In Keynote at the ACM Symposium on Principles of Distributed Computing, PODC, 2000.
  37. M. Bravo, N. Diegues, J. Zeng, P. Romano, and L. Rodrigues. On the use of clocks to enforce consistency in the cloud. IEEE Data Engineering Bulleting, 38(1):18--31, 2015.
  38. K. Birman, A. Schiper, and P. Stephenson. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst., 9(3), Aug. 1991.
  39. Benevenuto Fabrício, Rodrigues Tiago, Cha Meeyoung, Almeida Virgílio, Characterizing user behavior in online social networks, 10.1145/1644893.1644900
  40. Basho. Riak core. http://github.com/basho/riak_core,.
  41. Basho. Basho Bench. http://github.com/basho/basho_bench,.
  42. Balegas Valter, Duarte Sérgio, Ferreira Carla, Rodrigues Rodrigo, Preguiça Nuno, Najafzadeh Mahsa, Shapiro Marc, Putting consistency back into eventual consistency, 10.1145/2741948.2741972
  43. Bailis Peter, Fekete Alan, Franklin Michael J., Ghodsi Ali, Hellerstein Joseph M., Stoica Ion, Feral Concurrency Control : An Empirical Investigation of Modern Application Integrity, 10.1145/2723372.2737784
  44. P. Bailis, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Bolton causal consistency. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD '13, pages 761--772, New York, New York, USA, 2013.
  45. Bailis Peter, Fekete Alan, Ghodsi Ali, Hellerstein Joseph M., Stoica Ion, The potential dangers of causal consistency and an explicit solution, 10.1145/2391229.2391251
  46. Attiya Hagit, Ellen Faith, Morrison Adam, Limitations of Highly-Available Eventually-Consistent Data Stores, 10.1145/2767386.2767419
  47. Armstrong Timothy G., Ponnekanti Vamsi, Borthakur Dhruba, Callaghan Mark, LinkBench : a database benchmark based on the Facebook social graph, 10.1145/2463676.2465296
  48. Andersen David G., Franklin Jason, Kaminsky Michael, Phanishayee Amar, Tan Lawrence, Vasudevan Vijay, FAWN : a fast array of wimpy nodes, 10.1145/1629575.1629577
  49. Almeida Sérgio, Leitão João, Rodrigues Luís, ChainReaction : a causal+ consistent datastore based on chain replication, 10.1145/2465351.2465361
  50. Al-Fares Mohammad, Loukissas Alexander, Vahdat Amin, A scalable, commodity data center network architecture, 10.1145/1402958.1402967
  51. Akkoorath Deepthi Devaki, Tomsic Alejandro Z., Bravo Manuel, Li Zhongmiao, Crain Tyler, Bieniusa Annette, Preguica Nuno, Shapiro Marc, Cure: Strong Semantics Meets High Availability and Low Latency, 10.1109/icdcs.2016.98
  52. P. Ajoux, N. Bronson, S. Kumar, W. Lloyd, and K. Veeraraghavan. Challenges to adopting stronger consistency at scale. In Proceeding of the 15th Workshop on Hot Topics in Operating Systems, HotOS '15, 2015.
  53. Ahamad Mustaque, Neiger Gil, Burns James E., Kohli Prince, Hutto Phillip W., Causal memory: definitions, implementation, and programming, 10.1007/bf01784241
Bibliographic reference Van Roy, Peter ; Bravo Gestoso, Angel. Saturn: A Distributed Metadata Service for Causal Consistency.EuroSys 2017 Conference (Belgrade, Serbia, du 23/04/2017 au 26/04/2017).
Permanent URL http://hdl.handle.net/2078.1/196150