一句话：提出 function passing 编程模型与类型化核心演算，为基于 lineage 的分布式计算奠定基础并简化容错。
大数据处理系统普遍采用函数式 API，但缺少面向数据中心的分布式编程理论基础。论文提出 function passing 编程模型：将分布式不可变数据上的变换组织为持久函数式数据结构，通过网络传递良类型可序列化函数并应用，使节点保存变换而非分布式数据本身。该设计通过重放函数应用支持故障恢复，并将 deferred evaluation 仅引入网络通信发起处，在保持推理简单的同时兼顾时空效率。作者给出类型化核心语言的完整形式化，证明 subject reduction 以建立安全移动 lineage 理论，并证明 progress 保证远程 lineage 数据的有限物化。最后提供开源 Scala 实现，并通过若干示例框架与终端程序开展案例研究。
Abstract The most successful systems for “big data” processing have all adopted functional APIs. We present a new programming model, we call function passing , 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 distributed , 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 – 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.
@article{paperbot329,
title = {A programming model and foundation for lineage-based distributed computation},
author = {PHILIPP HALLER and HEATHER MILLER and NORMEN MÜLLER},
journal = {Journal of Functional Programming},
volume = {28},
year = {2018},
doi = {10.1017/s0956796818000035}
}