{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:54Z","timestamp":1779836754434,"version":"3.53.1"},"reference-count":39,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T00:00:00Z","timestamp":1520812800000},"content-version":"unspecified","delay-in-days":70,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2018]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The most successful systems for \u201cbig data\u201d processing have all adopted functional APIs. We present a new programming model, we call\n                    <jats:italic>function passing<\/jats:italic>\n                    , designed to provide a more principled substrate, or middleware, upon which to build data-centric distributed systems like Spark. A key idea is to build up a persistent functional data structure representing transformations on distributed immutable data by passing well-typed serializable functions over the wire and applying them to this distributed data. Thus, the function passing model can be thought of as a persistent functional data structure that is\n                    <jats:italic>distributed<\/jats:italic>\n                    , where transformations performed on distributed data are stored in its nodes rather than the distributed data itself. One advantage of this model is that failure recovery is simplified by design \u2013 data can be recovered by replaying function applications atop immutable data loaded from stable storage. Deferred evaluation is also central to our model; by incorporating deferred evaluation into our design only at the point of initiating network communication, the function passing model remains easy to reason about while remaining efficient in time and memory. Moreover, we provide a complete formalization of the programming model in order to study the foundations of lineage-based distributed computation. In particular, we develop a theory of safe, mobile lineages based on a subject reduction theorem for a typed core language. Furthermore, we formalize a progress theorem that guarantees the finite materialization of remote, lineage-based data. Thus, the formal model may serve as a basis for further developments of the theory of data-centric distributed programming, including aspects such as fault tolerance. We provide an open-source implementation of our model in and for the Scala programming language, along with a case study of several example frameworks and end-user programs written atop this model.\n                  <\/jats:p>","DOI":"10.1017\/s0956796818000035","type":"journal-article","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T04:18:35Z","timestamp":1520828315000},"source":"Crossref","is-referenced-by-count":6,"title":["A programming model and foundation for lineage-based distributed computation"],"prefix":"10.1017","volume":"28","author":[{"given":"PHILIPP","family":"HALLER","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"HEATHER","family":"MILLER","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"NORMEN","family":"M\u00dcLLER","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2018,3,12]]},"reference":[{"key":"S0956796818000035_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44202-9_13"},{"key":"S0956796818000035_ref38","unstructured":"Yu Y. , Isard M. , Fetterly D. , Budiu M. , Erlingsson \u00da. , Gunda P. K. & Currey J. (2008) DryadLINQ: A system for general-purpose distributed data-parallel computing using a high-level language. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, Draves, Richard, & van Renesse, Robbert (eds). Berkeley, CA, USA: USENIX Association, pp. 1\u201314."},{"key":"S0956796818000035_ref37","unstructured":"Waldo J. , Wyant G. , Wollrath A. & Kendall S. C. (1996) A note on distributed computing. In Proceedings of the International Workshop on Mobile Object Systems, Vitek J. , & Tschudin C. (eds). Berlin, Heidelberg, Germany: Springer-Verlag, pp. 49\u201364."},{"key":"S0956796818000035_ref9","doi-asserted-by":"crossref","unstructured":"Epstein J. , Black A. P. & Jones S. L. P. (2011) Towards Haskell in the cloud. In Proceedings of the Haskell Symposium, pp. 118\u2013129.","DOI":"10.1145\/2034675.2034690"},{"key":"S0956796818000035_ref35","unstructured":"Twitter. (2015) Scalding. Available at: https:\/\/github.com\/twitter\/scalding, accessed January 30, 2018."},{"key":"S0956796818000035_ref3","unstructured":"Apache. (2015) Hadoop. Available at: http:\/\/hadoop.apache.org\/, accessed January 30, 2018."},{"key":"S0956796818000035_ref8","unstructured":"Elsman M. (2005) Type-specialized serialization with sharing. In Proceedings of the Symposium on Trends in Functional Programming, pp. 47\u201362."},{"key":"S0956796818000035_ref36","unstructured":"Typesafe. (2015) Akka. Available at: http:\/\/akka.io\/, accessed January 30, 2018."},{"key":"S0956796818000035_ref30","doi-asserted-by":"crossref","unstructured":"Peyton Jones S. , Gordon A. & Finne S. (1996) Concurrent Haskell. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York, NY, USA: ACM, pp. 295\u2013308.","DOI":"10.1145\/237721.237794"},{"key":"S0956796818000035_ref28","unstructured":"Odersky M. & Zenger M. (2005) Scalable component abstractions. In Proceedings of the ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, Johnson R. E. & Gabriel R. P. (eds). New York, NY, USA: ACM, pp. 41\u201357."},{"key":"S0956796818000035_ref15","unstructured":"Haller P. , Prokopec A. , Miller H. , Klang V. , Kuhn R. & Jovanovic V. (2012) Futures and promises. Available at: http:\/\/docs.scala-lang.org\/overviews\/core\/futures.html, accessed January 30, 2018."},{"key":"S0956796818000035_ref33","doi-asserted-by":"crossref","unstructured":"Sewell P. , Leifer J. J. , Wansbrough K. , Nardelli F. Z. , Allen-Williams M. , Habouzit P. & Vafeiadis V. (2005) Acute: High-level programming language design for distributed computation. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming. New York, NY, USA: ACM, pp. 15\u201326.","DOI":"10.1145\/1086365.1086370"},{"key":"S0956796818000035_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796804005209"},{"key":"S0956796818000035_ref16","unstructured":"He J. , Wadler P. & Trinder P. (2014) Typecasting actors: From Akka to TAkka. In Proceedings of the 5th Scala Workshop. New York, NY, USA: ACM, pp. 23\u201333."},{"key":"S0956796818000035_ref29","volume-title":"Programming in Scala","author":"Odersky","year":"2010"},{"key":"S0956796818000035_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.019"},{"key":"S0956796818000035_ref21","first-page":"5","volume-title":"HotPar","author":"Matsakis","year":"2012"},{"key":"S0956796818000035_ref31","volume-title":"Types and Programming Languages","author":"Pierce","year":"2002"},{"key":"S0956796818000035_ref1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1086.001.0001","volume-title":"ACTORS: A Model of Concurrent Computation in Distributed Systems","author":"Agha","year":"1986"},{"key":"S0956796818000035_ref11","first-page":"75","volume-title":"OSDI","author":"Gunda","year":"2010"},{"key":"S0956796818000035_ref27","unstructured":"NICTA. (2015) Scoobi. Available at: https:\/\/github.com\/nicta\/scoobi, accessed January 30, 2018."},{"key":"S0956796818000035_ref39","unstructured":"Zaharia M. , Chowdhury M. , Franklin M. J. , Shenker S. & Stoica I. (2010) Spark: Cluster computing with working sets. In Proceedings of the USENIX Workshop on Hot Topics in Cloud Computing. HotCloud'10. Berkeley, CA, USA: USENIX Association, pp. 10\u201310."},{"key":"S0956796818000035_ref10","doi-asserted-by":"crossref","unstructured":"Germain G. (2006) Concurrency oriented programming in Termite Scheme. In Proceedings of the 2006 ACM SIGPLAN workshop on Erlang, p. 20.","DOI":"10.1145\/1159789.1159795"},{"key":"S0956796818000035_ref5","doi-asserted-by":"crossref","unstructured":"Chambers C. , Raniwala A. , Perry F. , Adams S , Henry R. R. , Bradshaw R. & Weizenbaum N. (2010) FlumeJava: Easy, efficient data-parallel pipelines. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. New York NY, USA: ACM. pp. 363\u2013375.","DOI":"10.1145\/1806596.1806638"},{"key":"S0956796818000035_ref32","first-page":"79","article-title":"Alice through the looking glass.","volume":"5","author":"Rossberg","year":"2004","journal-title":"Trends Funct. Program."},{"key":"S0956796818000035_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90008-4"},{"key":"S0956796818000035_ref18","doi-asserted-by":"crossref","unstructured":"Hickey R. (2008) The Clojure programming language. In Proceedings of the Dynamic Languages Symposium. New York, NY, USA: ACM, p. 1.","DOI":"10.1145\/1408681.1408682"},{"key":"S0956796818000035_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S095679689700261X"},{"key":"S0956796818000035_ref14","doi-asserted-by":"crossref","unstructured":"Haller P. & Odersky M. (2010) Capabilities for uniqueness and borrowing. In Proceedings of the European Conference on Object-Oriented Programming, Maribor, Slovenia, June 21\u201325, 2010, pp. 354\u2013378.","DOI":"10.1007\/978-3-642-14107-2_17"},{"key":"S0956796818000035_ref12","first-page":"272","volume-title":"OOPSLA","author":"Haller","year":"2016"},{"key":"S0956796818000035_ref7","volume-title":"PLOS@SOSP","author":"Dzik","year":"2013"},{"key":"S0956796818000035_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159881"},{"key":"S0956796818000035_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509516"},{"key":"S0956796818000035_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"S0956796818000035_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509547"},{"key":"S0956796818000035_ref25","unstructured":"Murphy T. VII, Crary, K. & Harper R. (2007) Type-safe distributed programming with ML5. In Proceedings of the International Symposium on Trustworthy Global Computing. Berlin, Heidelberg, Germany: Springer-Verlag, pp. 108\u2013123."},{"key":"S0956796818000035_ref26","unstructured":"Murray D. G. , Schwarzkopf M. , Smowton C. , Smith S. , Madhavapeddy A. & Hand S. (2011) CIEL: A universal execution engine for distributed data-flow computing. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation, Andersen D. G. & Ratnasamy S. (eds). Berkeley, CA, USA: USENIX Association."},{"key":"S0956796818000035_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"S0956796818000035_ref34","first-page":"386","volume-title":"SSS","author":"Shapiro","year":"2011"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796818000035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:36:45Z","timestamp":1779835005000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796818000035\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"references-count":39,"alternative-id":["S0956796818000035"],"URL":"https:\/\/doi.org\/10.1017\/s0956796818000035","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"article-number":"e7"}}