芭芭拉·利斯科夫

芭芭拉·利斯科夫（Barbara Liskov）是研究程序设计语言与分布式系统的计算机科学家。她先在加州大学伯克利分校学习数学，后在斯坦福大学研究计算机科学，取得博士学位；在MITRE工作期间领导过Venus操作系统项目，1972年加入麻省理工学院。

她的研究关心如何让大型程序的各部分能够被理解、组合和推理，获得了2008年度图灵奖。CLU、Argus及后来的容错系统并非同一种软件的不同名称，而是围绕数据抽象、分布式执行等不同问题展开的研究。

参考：[1]

利斯科夫与史蒂夫·齐勒斯在1973年共同细化抽象数据类型的思想。CLU以cluster组织一个类型的内部表示与操作实现；外部程序通过规定的操作使用对象，而不直接依赖内部存储细节。CLU的名字也取自cluster的前三个字母。

例如，一个集合可以用数组或链表保存，使用者关心的是插入、删除、查询是否遵守集合的规则。把表示隐藏在实现内部后，只要对外行为约定保持不变，表示方式就有改变的余地。这与单纯给已有表示换一个类型名称不同：语言机制需要限制外部对表示的直接访问。利斯科夫的历史回顾同时说明了相关前人工作和研究团队的参与。

参考：[2]

利斯科夫与珍妮特·温在1994年论文中系统阐述行为子类型：如果依据父类型规格能够证明某种性质，那么以子类型对象替换后，也应保留相应性质。这不是只看类名之间是否写了继承关系，也不是仅检查方法参数与返回类型相容。

栈和队列都可能提供放入、取出操作，但取出顺序不同，不能仅凭相似的方法签名互相替换。对于共享的可变对象，还需考虑状态不变量和随时间保持的约束；别名通过另一接口修改对象，也可能破坏原有推理。论文讨论的是明确规格下的安全性质，而非一句适用于所有程序的无限保证。

参考：[3]

1999年，米格尔·卡斯特罗与利斯科夫共同发表实用拜占庭容错研究。其对象是可能任意出错、甚至发送矛盾消息的副本。算法通过经过认证的消息交换，使正常副本对请求顺序达成一致，再执行相同的确定性状态机操作。

在论文的模型中，容忍最多f个故障副本通常配置3f+1个副本。安全性与活性必须分开：异步延迟不能让正常副本执行彼此冲突的已确认顺序，但最终继续处理请求还依赖一定的网络时序条件。算法也不保证恶意副本不会泄露其持有的数据。与CLU的数据抽象相比，这项合作把关注点转向跨机器的一致行为与明确故障假设。

参考：[4]