Ackley Urges Robust Software Design as Efficiency Focus Fuels Crashes

Dave Ackley

Prioritizing efficiency over redundancy makes modern computing dangerously brittle, requiring computer science to embrace decentralized autonomy so systems can survive real-world errors and scale indefinitely.

AI-assisted summary of Robust-first computing: Beyond efficiency — original source. Check the original for full context.

Source published: 2013-09-20

Key ideas

Traditional computer science prioritizes the 'CEO' attitude (Correctness and Efficiency Only), eliminating redundancy and leaving systems engineered to crash at the first unexpected error. (0:01)
Highly optimized sorting algorithms like merge sort rely on proxy comparisons and large positional jumps, creating high leverage that causes catastrophic positional error when comparisons fail. (7:02)
In benchmark tests on a 52-card deck with a 10% rate of random comparison errors, fragile high-efficiency algorithms like merge sort and quicksort are devastated relative to slower, localized approaches like bubble sort. (7:02)
Ackley proposes replacing the centralized CPU-and-RAM 'dictatorship' with decentralized, autonomous units modeled on democratic and market systems to allow computing to scale indefinitely and absorb localized failures. (12:51)

Detailed notes

## Background Published on YouTube by Dave Ackley on September 20, 2013, this video provides a high-level introduction to robust-first computing featuring an interactive sorting demonstration. It sets the stage for his essay in the October 2013 issue of Communications of the ACM, arguing for a fundamental pivot from hardware efficiency to system resilience.

## TL;DR Ackley challenges computer science's prevailing 'CEO' (Correctness and Efficiency Only) mindset, which dangerously treats reliability as someone else's problem by eliminating the redundancy required for robustness. Using an 'alien card deck' demonstration, he shows how high-efficiency sorting algorithms like merge sort rely on heavy leverage that turns catastrophic when comparisons become unreliable, whereas humble algorithms like bubble sort degrade far more gracefully under noise. He critiques standard von Neumann computing as a fragile, centrally planned CPU dictatorship that cannot scale. Ultimately, Ackley advocates organizing computation around decentralized, autonomous units with built-in redundancy, enabling systems to absorb real-world failures and scale indefinitely.

## Atmosphere & style The presentation carries the engaging, slightly eccentric warmth of a hands-on academic demonstration, blending serious foundational philosophy with tactile show-and-tell. The rhythmic, mechanical clatter of the homemade 'alien card' comparator adds a quirky, DIY workshop charm to what could otherwise be an abstract computer science lecture. It feels like an eye-opening, conversational seminar that challenges decades of entrenched engineering dogma with approachable metaphors, dry wit, and accessible common sense.

## Bulletin - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) Traditional computer science prioritizes the 'CEO' attitude (Correctness and Efficiency Only), eliminating redundancy and leaving systems engineered to crash at the first unexpected error. - [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) Highly optimized sorting algorithms like merge sort rely on proxy comparisons and large positional jumps, creating high leverage that causes catastrophic positional error when comparisons fail. - [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) In benchmark tests on a 52-card deck with a 10% rate of random comparison errors, fragile high-efficiency algorithms like merge sort and quicksort are devastated relative to slower, localized approaches like bubble sort. - [12:51](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=771s) Ackley proposes replacing the centralized CPU-and-RAM 'dictatorship' with decentralized, autonomous units modeled on democratic and market systems to allow computing to scale indefinitely and absorb localized failures.

## Key takeaways - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) Robustness requires redundancy, whereas efficiency actively strives to eliminate redundancy, creating a fundamental structural conflict in system design. - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) Computers typically crash because they are intentionally engineered under the assumption of absolute reliability, freezing immediately when design assumptions are violated. - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) The historic contract assigned hardware the role of creating deterministic logic and software the role of maximizing output per cycle, giving rise to the 'CEO' (Correctness and Efficiency Only) mindset. - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) Because hardware is now cheap and software is inherently buggy, computer science must prioritize robustness first rather than viewing efficiency as an inherent virtue. - [04:09](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=249s) Bubble sort is widely derided for its inefficiency, but its localized, step-by-step swaps prevent single errors from causing massive structural damage. - [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) Positional error measures the total displacement of elements from their correct locations, offering a metric to evaluate sorting performance under unreliable conditions. - [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) Merge sort achieves efficiency through proxy comparisons and large positional jumps, but this high algorithmic leverage turns disastrous if comparisons become unreliable. - [12:00](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=720s) High-efficiency algorithms behave like 'prima donna' software requiring perfect operating conditions, whereas robust systems act as 'team players' capable of absorbing friction. - [12:51](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=771s) Conventional CPU-RAM architecture operates like a centrally planned dictatorship, hitting severe physical scaling limits and creating a single point of failure. - [12:51](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=771s) Redundant, autonomous computational units modeled on market economies or democracies appear inefficient on paper but can survive localized failure and scale indefinitely.

## Detailed walkthrough ### [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) Efficiency vs. Robustness and the "CEO" Attitude

Dave Ackley argues that both the safety of human society and the goal of building massive computers require embracing "robust-first computing." A system can be defined as robust if it manages to perform sensible actions even when its original design assumptions are stressed or outright violated. While robustness frequently appears as an attractive buzzword on feature checklists, traditional computer science has overwhelmingly focused on hardware efficiency. This creates an unavoidable structural conflict: robustness fundamentally requires redundancy, whereas efficiency actively strives to eliminate redundancy. Because computers now inhabit the real world and shoulder critical responsibilities, the priorities must flip. As Ackley summarizes: “So for computers out in the real world, for systems meant to have actual responsibility, we should put robustness first, and view maximizing efficiency not as an inherent virtue, but more as a regrettable sometimes necessity.” This argument serves as an introduction to an essay he authored for the October issue of *Communications of the ACM* (CACM).

```mermaid flowchart TD accTitle: The Efficiency versus Robustness Conflict accDescr: Diagram illustrating how efficiency eliminates the redundancy that robustness inherently requires. subgraph CoreTension["The Fundamental Conflict"] R["Robustness"] -->|"Requires"| RED["Redundancy"] E["Efficiency"] -->|"Eliminates"| RED end subgraph Outcome["System Design Impact"] RED -.->|"Safety under stress"| RF["Robust-First Systems"] E -->|"Zero tolerance for faults"| CEO["Brittle 'CEO' Design"] end ```

Ackley investigates why computers crash in the first place, noting that when he posed the question across the country over the preceding eighteen months, people routinely blamed bad hardware, software bugs, user mistakes, or malware. Ackley counters that the root cause is intentional design: computers are engineered to completely freeze up at the first unexpected event. Programmers designed them this way because they operated under the assumption of absolute reliability, chaining logical instructions together without planning for failure.

This mindset traces directly back to an implicit historical contract established at the dawn of digital computing between hardware engineers and software creators: - Hardware was assigned the duty of turning the messy, unruly physical realm into deterministic logic. - Software was tasked with transforming that logic into valuable, revenue-generating functions. - Because early hardware was extraordinarily weak and prohibitively expensive, software faced intense economic pressure to maximize usefulness out of every machine cycle. - This dynamic birthed the prevailing "CEO" software attitude—standing for Correctness and Efficiency Only—which remains the core foundation of algorithmic design.

Today, however, the landscape has inverted: hardware is inexpensive and vastly more powerful than necessary for many tasks, while bugs saturate software to the point where defining absolute "correctness" is often impossible. Ackley asserts that continuing to cling to the outdated CEO attitude is dangerous, urging computer science to develop a disciplined foundation for putting robustness first.

[04:09](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=249s) The Alien Card Deck and the Bubble Sort Demonstration

To illustrate the concrete differences between algorithmic philosophies, Ackley introduces a physical demonstration centered on sorting—specifically pairwise comparison sorting. He pulls out what he jokingly refers to as an alien card deck from Roswell, New Mexico, covered in cryptic symbols like suns, colored shapes, and abstract markings that make human ordering impossible by sight. To order the deck, one must rely on an accompanying "alien card comparison device."

Ackley inserts pairs of cards into the mechanical comparison gadget, which calculates which card is higher. When comparing two cards, if the device determines one is greater, Ackley can shift it down the row. By repeatedly comparing adjacent cards and sliding the larger ones toward the back, he demonstrates bubble sort. At one point during the demo, the comparison device produces an unexpected result, registering two different cards as equal before settling, hinting at mechanical unreliability.

Bubble sort works by repeatedly sweeping through the sequence: if two adjacent elements are out of order, they swap positions. Repeating this sweep enough times guarantees that an item starting entirely at the wrong edge has enough steps to bubble over to its correct location. Despite functioning reliably, bubble sort has long been treated with contempt across the discipline: “Now, computer scientists love to hate bubble sort because it's so inefficient.”

[07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) Positional Error and the Peril of High-Leverage Algorithms

Ackley introduces the central problem: what happens if the comparison device is unreliable and occasionally makes mistakes? In a setting where comparisons are not guaranteed to be strictly correct, obtaining an objectively correct sort in the traditional mathematical sense is impossible. To evaluate how badly an algorithm fails under these conditions, Ackley introduces the metric of *positional error*.

Ackley contrasts bubble sort with merge sort, an algorithm widely celebrated for its efficiency and ubiquitously deployed across modern personal computers and smartphones. Merge sort operates by recursively dividing elements into halves until it reaches pairs, sorting those pairs, and then merging progressively larger sorted sublists—from groups of two into fours, fours into eights, and so forth.

```mermaid flowchart TD accTitle: Merge Sort Recursive Merging Process accDescr: Shows the bottom-up merge steps from pairs to fours to eights, illustrating long-distance item travel. subgraph Pairs["Base Comparisons"] P1["Pairs of 2"] end subgraph Merging["Recursive Merging"] F1["Groups of 4"] E1["Final Group of 8"] end Pairs -->|"Merge sorted halves"| F1 F1 -->|"Long-distance swaps"| E1 ```

Merge sort achieves its high algorithmic efficiency through two clever mechanisms: - **Proxy comparisons:** When merging two pre-sorted lists, the algorithm only inspects the front items (`Is A less than B?`). Because the rest of each list is already sorted, that single comparison acts as a proxy for every remaining item in the group. - **Large positional jumps:** When elements are placed into merged blocks—especially in later stages—items jump large distances across the array in single operations, reducing positional error rapidly.

However, this structural strength becomes a critical liability in an imperfect world. Ackley emphasizes that the very leverage that gives merge sort its high speed turns disastrous when comparisons fail: “And the increased efficiency implies increased leverage and so if that's the case that the comparison routine might fail sometimes, then that leverage which just helped us so much, can now come around and hurt us so much.”

To quantify this, Ackley presents benchmark data sorting a 52-card deck where the comparison device functions correctly 90% of the time, but generates completely random outputs for the remaining 10%. Under these noisy conditions, highly optimized algorithms like merge sort and quicksort are utterly devastated in terms of total positional error compared to less "efficient" approaches.

[12:00](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=720s) Moving Past the "Software CEO" Mindset

Reflecting on the sorting demo results, Dave Ackley notes that depending on how the shuffling operates in practice, some individual runs turn out worse and some turn out better; the reported numbers reflect overall averages. Looking closely at bubble sort under these conditions, Ackley acknowledges that many observers immediately assume the algorithm's vulnerability is trivial to patch. Programmers reflexively think that one can simply sample multiple times before committing to a swap or introduce similar workarounds—nuances he covers more extensively in his written essay. However, patch-based thinking misses the deeper structural critique Ackley wants to emphasize.

The prevailing paradigm in computer science operates under an executive mindset obsessed with driving down operational margins without taking responsibility for the underlying environment. Dave Ackley argues that our foundational philosophy must change: “The point I want to make is just this: That because we have the software CEO mindset, that says 'Reliability is someone else's problem!' and we can feel free to screw the efficiency down as hard as we can, and feel like it's a good day's work -- maybe that's not the best approach anymore.” Instead of engineering high-strung, prima donna software that collapses the moment ideal hardware assumptions slip, Ackley suggests that computer scientists should strive for team-player software designed to give better than it gets.

- Programmers often try to rescue bubble sort in noisy environments by retrying comparisons multiple times before swapping, treating fragility as an afterthought rather than a core design flaw. - High-efficiency computing produces "prima donna" programs that demand absolute environmental perfection to function. - Robust-first software acts as a "team player," absorbing friction and maintaining integrity even when the underlying substrate falters.

[12:51](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=771s) Central Dictatorships vs. Robust Decentralized Systems

Turning toward the broader future of computing, Dave Ackley challenges the physical and conceptual architecture that has dominated modern machines: the pairing of a single central processing unit (CPU) with random-access memory (RAM). He describes a standard computer as essentially a centrally planned dictatorship. In this model, the CPU lords over the system, dictating every single action, while all the peons sit cowering in the memory array doing nothing until they receive explicit commands. While this centralized paradigm made intuitive sense early on and remains easy to conceptualize, it is inherently fragile and faces severe physical scaling limits: the lone coordinator in the center simply cannot run any faster, nor can it manage an ever-expanding volume of state on its own.

As an alternative, Ackley proposes modeling computation after systems with distributed autonomy, such as free-market capitalism or democracy. In the real world, having three coffee shops on a single block looks wildly inefficient on paper; they do not operate at peak utilization the way a centrally planned schedule dictating exactly when every citizen should drink coffee would. Yet this redundancy provides resilience: if one coffee shop closes or accidentally poisons its clientele, the surrounding shops step in and absorb the demand without halting society. Framing computer architecture around localized independence allows computation to endure localized failures. Dave Ackley explains the ultimate promise of this shift: “And if we think about organizing computation on a sort of democratic capitalist, individual autonomy kinda basis, then potentially, we can make a computer system that scales indefinitely.” Concluding the presentation, Ackley stresses that this insight sits at the very heart of the robust-first paradigm: once you truly grasp why autonomy and redundancy matter more than fragile efficiency, the path forward becomes clear.

```mermaid flowchart TD accTitle: Comparison of Centralized Dictatorship and Robust-First Computing accDescr: Diagram contrasting traditional CPU-RAM architecture against decentralized robust-first computation.

subgraph Centralized ["Traditional von Neumann Dictatorship"] CPU["Central CPU (Single Dictator)"] RAM["Passive RAM (Subservient Memory)"] CPU -->|"Strict step-by-step commands"| RAM Bottleneck["Fragile Bottleneck: CPU cannot run faster"] CPU -.-> Bottleneck end

- The classical von Neumann setup relies on a single CPU dictating operations to passive RAM, creating an unscalable bottleneck and an intolerant failure domain. - Redundant entities, such as multiple neighborhood coffee shops, appear inefficient compared to centrally scheduled systems, but their redundancy prevents catastrophic system failure. - Shifting to democratic, autonomous units allows computing systems to transcend the physical clock-speed limits of central controllers and scale indefinitely.

## Notable quotes > [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) So for computers out in the real world, for systems meant to have actual responsibility, we should put robustness first, and view maximizing efficiency not as an inherent virtue, but more as a regrettable sometimes necessity. — Dave Ackley

> [12:51](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=771s) And if we think about organizing computation on a sort of democratic capitalist, individual autonomy kinda basis, then potentially, we can make a computer system that scales indefinitely. — Dave Ackley

## Mentioned Dave Ackley, Communications of the ACM, Roswell, New Mexico, bubble sort, merge sort, quicksort

## Video description A high-level introduction to robust-first computing, with a sorting demo.

[Source](https://www.youtube.com/watch?v=7hwO8Q_TyCA)

中文简报

阿克利呼吁采用鲁棒软件设计，直指过分追求效率加剧系统崩溃优先考虑效率而非冗余使现代计算变得极其脆弱；计算机科学需拥抱去中心化自主性，以便系统能承受现实中的错误并实现无限扩展。阿克利对计算机科学界盛行的“CEO”（仅关注正确性与效率）思维提出质疑，指出这种思维通过消除鲁棒性所需的冗余，危险地将可靠性视为他人的责任。他借助“外星人扑克牌”演示，展示了归并排序等高效排序算法如何依赖巨大的杠杆作用，而在比较变得不可靠时演变成灾难性的结果；相比之下，冒泡排序等不起眼的算法在噪声影响下的退化要平缓得多。他批评标准冯·诺依曼计算是一种脆弱的、中央计划式的CPU专制结构，无法无限扩展。最终，阿克利主张围绕具有内置冗余的去中心化自主单元来组织计算，使系统能够抵御现实中的故障并实现无限扩展。传统计算机科学优先考虑“CEO”态度（仅关注正确性与效率），消除了冗余，导致系统在遭遇第一个意外错误时便走向崩溃。 (0:01) 像归并排序这样高度优化的排序算法依赖代理比较和大幅度位置跳跃，产生了极高的杠杆效应，一旦比较出错就会引发灾难性的位置误差。 (7:02) 在包含10%随机比较错误率的52张扑克牌基准测试中，相较于冒泡排序等更慢的局部化方法，归并排序和快速排序等脆弱的高效算法遭到了破坏性打击。 (7:02) 阿克利提议用仿照民主与市场体系构建的去中心化自主单元，取代中心化的CPU与内存“专制”结构，使计算能够吸收局部故障并无限扩展。 (12:51)

Reading summary

Dave Ackley argues that computer science must abandon its historical obsession with efficiency in favor of a robust-first design philosophy, warning that optimizing systems for perfection leaves them dangerously brittle in the real world. The Conflict Between Redundancy and the CEO Mindset (0:01) Ackley identifies a fundamental conflict in computer science: robustness requires redundancy, whereas efficiency actively eliminates it. He traces modern software fragility to an early historical division of labor where hardware engineers promised deterministic logic from messy physical components, leaving software developers to extract maximum utility from scarce, costly machine cycles. This gave rise to what Ackley calls the "software CEO" attitude—standing for Correctness and Efficiency Only—which assumes underlying reliability is someone else's problem. While hardware has become inexpensive and vastly more capable, software remains saturated with bugs, rendering assumptions of absolute correctness unrealistic. Ackley argues that systems intentionally freeze at the first unexpected event because they were engineered under the flawed expectation of zero faults. Instead of building high-strung, "prima donna" programs that demand perfect operating conditions, he advocates for "team-player" software designed to absorb friction and perform sensibly even when original design assumptions fail. Algorithmic Leverage and Positional Error Under Stress (7:02) To evaluate algorithmic performance in imperfect environments, Ackley introduces the metric of positional error, measuring how far items end up from their correct slots when comparisons cannot be guaranteed. He contrasts the widely disliked bubble sort against merge sort, an industry standard praised for its speed. Merge sort gains its efficiency through algorithmic leverage, utilizing proxy comparisons and large positional jumps to organize sublists rapidly. However, Ackley demonstrates that this leverage becomes destructive when the environment is noisy. In a benchmark sorting a 52-card deck where the comparison mechanism fails completely at random 10% of the time, highly optimized algorithms like merge sort and quicksort suffer devastating positional error. A single faulty comparison causes entire pre-sorted blocks to be misplaced across large distances. By contrast, bubble sort's localized, step-by-step swaps limit the fallout of bad data, illustrating that efficiency mechanisms can dramatically increase vulnerability under real-world stress. Decentralized Autonomy Versus Centralized von Neumann Bottlenecks (12:51) Ackley extends his critique to the standard hardware architecture pairing a central processing unit (CPU) with random-access memory (RAM), characterizing it as a centrally planned dictatorship. In this paradigm, a lone CPU orchestrates every command while memory remains entirely passive. Ackley contends that this model is not only fragile but physically bounded, as a single central coordinator cannot run indefinitely faster nor manage ever-increasing volumes of state. As an alternative, Ackley proposes organizing computation around decentralized autonomy, drawing an analogy to market economies and democracies. While having multiple coffee shops on a single block appears inefficient compared to a centrally planned schedule, this redundancy prevents systemic collapse if one shop fails. He asserts that computing architectures built on localized independence and redundancy can absorb localized failures and achieve indefinite scalability without relying on a single, fragile point of control. Ackley concludes that maximizing efficiency should be treated as a regrettable occasional necessity rather than an inherent virtue, asserting that indefinite scalability and real-world safety will remain out of reach until computing embraces redundancy and autonomous fault tolerance.

精炼阅读摘要

Dave Ackley 指出，传统计算机科学长期受制于“仅关注正确性与效率”（CEO）的陈旧思维，通过极力消除冗余追求性能，导致系统在面对物理现实扰动时极易发生灾难性崩溃。他主张确立“鲁棒优先计算”（robust-first computing）范式，将容错冗余与局部自主性置于首位，从而构建能够适应现实环境并实现无限扩展的计算系统。效率与鲁棒性的冲突与“CEO”思维 (0:01) Ackley 将系统的鲁棒性定义为在原有设计假设受到压力或遭到完全破坏时，仍能执行合理操作的能力。实现鲁棒性本质上依赖冗余，而传统计算对效率的追求却在竭力消除冗余，两者存在根本性的结构冲突。在数字计算初期，硬件极其昂贵且孱弱，促成了软硬件之间的历史契约：硬件负责将混乱的物理世界抽象为确定性逻辑，软件则必须榨干每一个时钟周期以实现业务价值。这种背景催生了“仅限正确与效率”（Correctness and Efficiency Only，简称 CEO）的软件思维模式，软件被默认运行在绝对可靠的环境中，一旦遇到未预料事件便立即彻底锁死。Ackley 认为，如今硬件成本大幅降低且性能过剩，而软件缺陷普遍存在；继续固守 CEO 思维不仅过时，而且对承担现实关键职责的系统构成了严重安全隐患。高杠杆算法的脆弱性与位置误差 (7:02) 为了评估算法在不可靠环境中的表现，Ackley 提出了“位置误差”（positional error）指标，用以量化排序结果偏离理想状态的距离。在演示中，Ackley 对比了以高效著称并广泛应用于现代设备中的归并排序（Merge Sort）与长期因低效备受贬低的冒泡排序（Bubble Sort）。归并排序之所以高效，依赖于“代理比较”（单次比较决定整个有序子序列的归属）与“跨距离跳跃”两项机制。然而，Ackley 强调高效率意味着高杠杆，这种杠杆在理想环境下能成倍提升速度，在面对故障时却会造成成倍的破坏。在 52 张卡牌、比较机制存在 10% 随机错误的基准测试中，由于单次比较失效会导致整个分支大范围错位，高度优化的归并排序与快速排序的总位置误差急剧恶化，其容错表现远逊于那些仅进行局部相邻比较的“低效”算法。摒弃“打补丁”逻辑与大牌软件倾向 (12:00) 面对排序在噪声环境中暴露出的脆弱性，许多程序员习惯性地倾向于采用局部“打补丁”的方式进行补救，例如在执行交换前多次重复采样比较。Ackley 指出，这种修补思维并未触及深层的设计哲学缺陷。当前计算科学盛行的软件 CEO 心态将可靠性推诿为外部环境的责任，热衷于将效率指标推向极限，由此制造出对运行环境要求苛刻、容不得半点瑕疵的“大牌独奏家”（prima donna）式程序。Ackley 呼吁计算机科学应当摆脱这种逃避责任的开发文化，转向构建具有“团队合作精神”（team player）的软件体系，使其不仅能在底层基质失效时吸收物理摩擦，更能主动维持系统整体功能的连续性。从中央集权架构转向去中心化自治 (12:51) Ackley 进一步批判了以单颗 CPU 与 RAM 结合为核心的经典冯·诺依曼架构，将其比喻为一种高度脆弱的“中央集权专制”：核心调度器统揽一切决策，被动的内存阵列只能机械听命，这种中心化模式面临着主频无法继续提升的物理极限与单点失效风险。作为替代方案，Ackley 提出借鉴自由市场与民主体制中的分布式自治原则。正如一个街区设立三家咖啡店在集中规划的日程表上看极为低效，但这种冗余能保证单家店铺歇业甚至发生食品安全事故时，周围店铺可以迅速分担需求而维持社会运转。Ackley 认为，基于局部自主性和冗余容错构建的计算体系，能够彻底克服中心控制器的物理瓶颈，实现具有高度韧性且理论上可无限扩展的计算机系统。 Ackley 总结认为，理解冗余与个体自主性对系统弹性的价值是计算科学实现代际跨越的核心。在计算机深度融入物理世界的当下，应当将鲁棒性确立为第一准则，而将最大化效率视为一种偶尔不得不妥协的次要需求，以此推动计算架构实现无限规模的扩展与根本性的安全变革。

Detailed notes — zh

## Background 该视频由计算机科学家 Dave Ackley 于 2013 年 9 月 20 日发布在 YouTube 频道上。页面描述指出，这是一期关于“鲁棒优先计算”（robust-first computing）的高级概念介绍，并配有卡牌排序演示，探讨计算如何超越对效率的单一追求。 ## TL;DR Dave Ackley 批判了计算机科学长期以来将极致效率置于一切之上的“CEO 心态”，指出这种将可靠性完全寄托于底层硬件的传统契约导致了软件在面对现实扰动时极其脆弱。通过“外星卡牌比较仪”的排序实验，他演示了归并排序等高效算法如何因高杠杆机制在存在 10% 比较噪声时造成严重的位置误差扩散，而低效的冒泡排序反而具备局部韧性。Ackley 进而抨击了 CPU 与内存构成的“中央计划独裁制”冯·诺依曼架构，主张借鉴自由市场中个体自治与动态冗余的模式，构建能够容忍缺陷、实现无限横向扩展的鲁棒优先计算系统。 ## Atmosphere & style 视频兼具学术思辨的锐度与生动幽默的极客气质。Dave Ackley 运用“外星卡牌”、街角咖啡店等形象比喻，将晦涩的系统架构与容错哲学讲得深入浅出且发人深省。整场演讲透露出一种颠覆主流范式的先锋感与批判反思精神，既有严谨的算法数据推演，又充满对未来计算体系宏大图景的探索激情。 ## Bulletin - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) Dave Ackley 提出“鲁棒优先计算”（robust-first computing），主张打破计算机科学长期将效率置于一切之上的传统，将鲁棒性而非极致效率视为现实系统的核心诉求。 - [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) 在比较操作存在 10% 错误率的非理想实验中，归并排序等高效算法由于高杠杆代理机制导致位置误差大面积扩散，而低效的冒泡排序反而展现出更平缓的容错特性。 - [12:55](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=775s) 传统单机冯·诺依曼架构形同“中央计划独裁制”，单点 CPU 调度限制了系统的横向扩展与容错能力。 - [12:55](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=775s) 未来的计算系统应借鉴自由市场冗余与自治机制，以牺牲部分峰值利用率为代价换取系统的韧性与理论上的无限扩展能力。 ## Key takeaways - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) 鲁棒性定义为系统在设计假设受到破坏或面临压力时，仍倾向于做出合乎情理的明智行为。 - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) 效率与鲁棒性之间存在根本性对抗：鲁棒性需要冗余来容错，而效率的核心则是消除一切冗余。 - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) 计算机容易崩溃死机并非偶然，而是早期硬件昂贵背景下形成的“硬件负责绝对正确、软件专注变现与效率（CEO 态度）”的分工契约所致。 - [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) 当硬件成本极低且性能过剩时，软件仍固守“仅讲求正确与效率”的思维已不再适应真实世界的需求。 - [04:06](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=246s) 冒泡排序因执行效率低而在计算机科学中被视为“害群之马”，但在底层比较操作不完美时其局部低杠杆特性展现出不同的鲁棒行为。 - [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) 引入“位置误差”可以定量评估数据偏离正确顺序的整体严重程度，而非仅采用二元判定。 - [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) 归并排序依赖“先导元素代理”与“长距离跃迁”获得极高效率，但其高杠杆机制在底层出现错误时会成倍放大并扩散误差。 - [12:00](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=720s) 对算法脆弱性的局部参数修补无法解决根源问题，软件行业必须转变将可靠性全盘外包给底层的思维定势。 - [12:00](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=720s) 计算系统需要从脆弱敏感的“独奏大牌”式软件转向具备容错与自愈能力的“团队协作型”软件。 - [12:55](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=775s) CPU 与内存的关系本质上是一种脆弱且难以无限扩展的“中央计划独裁制”架构。 - [12:55](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=775s) 如同街区分布多家咖啡店的商业冗余，去中心化自治与结构冗余是构建能够无限横向扩展的鲁棒计算系统的关键途径。 ## Detailed walkthrough ### [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) 鲁棒优先计算的核心主张与历史契约计算科学界长期将效率奉为圭臬，然而 Dave Ackley 认为，为了社会安全以及构建真正超大规模的计算机，整个行业必须转向“鲁棒优先计算”（robust-first computing）。所谓鲁棒性，是指系统在设计假设受到压力甚至遭到破坏时，依然倾向于做出合乎情理、明智的行为。虽然“鲁棒”一词频繁出现在各类功能清单中，但计算机科学的绝大部分精力都在追求高效利用硬件，而效率与鲁棒性之间存在天然的对抗：鲁棒性依赖于冗余，而效率的第一要务恰恰是消除冗余。面对真实世界中承担实际责任的系统，计算范式必须重塑。对此，Dave Ackley 明确指出： > “So for computers out in the real world, for systems meant to have actual responsibility, we should put robustness first, and view maximizing efficiency not as an inherent virtue, but more as a regrettable sometimes necessity.” ```mermaid flowchart TD accTitle: 传统与鲁棒计算模式对比 accDescr: 展示传统CEO模式与鲁棒优先模式在硬件与软件职责上的区别 subgraph TRAD["传统模式 (CEO观念)"] H1["硬件承担绝对可靠性 (消除物理混乱为精确逻辑)"] S1["软件追求单向目标 (仅正确性与极致效率)"] H1 --> S1 end subgraph ROBUST["鲁棒优先模式"] H2["不可靠/存在故障的现实硬件"] S2["鲁棒优先软件架构 (保留必要冗余与容错)"] H2 --> S2 end ``` 这种将效率置于一切之上的思维，根源于计算机诞生初期的软硬件契约。回顾半个多世纪以来的计算架构，计算机之所以一遇意外就崩溃死机，本质上是“我们特意设计成那样的”。程序员习惯了预设底层完全可靠，只需将步骤按顺序堆叠，从未深入考虑过如果某一步骤出错该如何自处。在数字计算初期，硬件极其昂贵且孱弱，因而形成了明确的分工契约：硬件负责提供绝对的可靠性，把不受控的物理世界规整为清晰的逻辑；软件的职责则是将逻辑转化为具有经济价值的功能，从而赚取收益弥补硬件和软件的高昂成本。这种经济重压催生了软件必须“仅讲求正确与效率”（Correctness and Efficiency Only，简称 CEO 态度）的信条。如今硬件不仅极其廉价且往往性能过剩，软件缺陷却无处不在，甚至许多场景下连“什么是绝对正确”都难以界定。然而计算机科学依然背负着早期的 CEO 态度，必须将思维转变到鲁棒优先的科研与工程实践中。 - 论文背景：该核心论点发表在《Communications of the ACM》（CACM）2013年10月刊。 - 死机常见归因：坏硬件、程序 Bug、用户误操作、恶意软件；但深层原因在于系统被设计为“遇到第一个意外就直接冻结卡死”。 --- ### [04:06](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=246s) 外星卡牌排序与冒泡排序的“黑羊”特质为了具体展示鲁棒性与效率的博弈，Dave Ackley 选用成对比较排序（pairwise comparison sorting）作为演示切入点。他拿出了一副仿佛来自新墨西哥州罗斯威尔（Roswell）的“外星卡牌”，牌面上印着双太阳等奇特外星符号，肉眼完全无法凭直觉判断大小前后。与这副卡牌配套的是一台“外星卡牌比较仪”，只要将两张卡牌放入其中，仪器就会运算并判定孰大孰小，甚至偶尔会给出两张牌相等的判定结果。通过移动比较仪器在相邻卡牌间进行比对与交换，最底部的卡牌逐步就位，相邻元素不断调整，这正是经典的冒泡排序（bubble sort）。在计算机科学界，冒泡排序一直被视作该领域的“害群之马”（black sheep）而饱受诟病，原因就在于其效率极度低下——它仅仅在相邻位置不断对比并置换逆序元素，然后一遍遍从头重复，直到最右端的元素一步步“冒泡”挪动到最左端。然而，当假定这台外星比较仪并非绝对完美、偶尔也会出错甚至给出错误判定时，整个评判排序算法优劣的逻辑便迎来了戏剧性的转折。 ```mermaid flowchart LR accTitle: 冒泡排序的相邻比较流程 accDescr: 展示外星卡牌通过相邻比较逐步交换冒泡的过程 A["卡牌 A"] <-->|"外星比较仪判定"| B["卡牌 B"] B <-->|"逆序则相邻交换"| C["卡牌 C"] C <-->|"小步迭代移动"| D["卡牌 D"] ``` --- ### [07:02](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=422s) 位置误差概念与归并排序的“高杠杆”困境当比较操作无法保证百分之百正确时，任何排序算法都无法保证输出传统意义上“严格正确”的绝对顺序。为了衡量错误程度究竟有多严重，Dave Ackley 引入了“位置误差”（positional error）的概念。如果数据完全有序（如 1、2、3、4），每个元素距离应在位置的偏差均为 0，总误差为 0；如果相邻元素发生对调（如 2、1、3、4），位置误差各为 1，累计误差为 2；若数组彻底逆序（4、3、2、1），则各元素均大幅度偏离，达到最大的位置误差。与被鄙视的冒泡排序相对立的是计算机科学几十年来的骄傲——归并排序（merge sort）等高效算法。归并排序几乎无处不在，从手机到通用 PC 的各类现代底层软件中均有其身影。其高效性主要依赖两大精妙设计： 1. **先导元素代理机制**：在合并两组已经排好序的子序列时，算法只需比较两个小组的带头元素，一旦确定大小，就能代表其整组剩余元素的相对大小，从而省去大量比较。 2. **长距离跃迁交换**：在算法后期将大块数据合并时，一次判定就能将元素在数组中移动极长的距离，极速降低潜在的位置误差。 ```mermaid flowchart TD accTitle: 归并排序高效机制与脆弱性 accDescr: 阐述归并排序通过高杠杆换取高效的同时放大了错误传播 subgraph EFFICIENCY["高效核心机制"] DIV["分治至小分组"] --> COMP["仅比对先导代理元素"] COMP --> JUMP["跨越长距离大幅归位"] end subgraph RISK["错误发生时的连锁反应"] ERR["比较仪10%概率随机报错"] --> LEV["高杠杆将错误放大"] LEV --> POSERR["严重的位置误差扩散至大范围"] end EFFICIENCY -.->|"一旦底层失真"| RISK ``` 然而，高效的代价是巨大的杠杆风险（leverage）。归并排序为了效率，将单次比较的结果作为信任基石，直接赋予其撬动大跨度移动的权力。关于这种高效率所蕴含的隐患，Dave Ackley 警告道： > “And the increased efficiency implies increased leverage and so if that's the case that the comparison routine might fail sometimes, then that leverage which just helped us so much, can now come around and hurt us so much.” 实验数据揭示了这一残酷事实：假设拿一副 52 张的扑克牌进行洗牌并排序，外星比较仪有 90% 的概率给出正确结果（小于、大于或等于），但有 10% 的概率随机给出荒谬答案。在这种充满噪声与故障的非理想环境下，归并排序以及同样高效的快速排序（quick sort）在 Y 轴所示的“总卡牌位置误差”指标上惨遭重创，其原本引以为傲的高杠杆反而导致了严重系统性错误的大面积扩散。 ### [12:00](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=720s) 告别独奏大牌：从压榨效率到“团队协作”软件在评估算法在扰动下的实际表现时，洗牌机制的具体实现会导致结果上下波动，有时更好，有时更差，呈现出来的数据均是统计平均值。观察冒泡排序（bubble sort）等传统算法时，许多人的第一反应往往是认为问题很容易修补，比如只需在决定是否交换位置之前多尝试几次。Dave Ackley 指出，相关的详细分析已在专门的文章中展开，但他最想强调的并不是具体的修补技巧，而是整个软件行业长期以来的思维定势。长期以来，软件行业普遍抱着一种“CEO 心态”，认为可靠性是底层硬件或其他人的事情，程序员的职责就是尽可能把运行效率压榨到极限。Dave Ackley 尖锐地批评了这种视角：“Because we have the software CEO mindset, that says 'Reliability is someone else's problem!' and we can feel free to screw the efficiency down as hard as we can, and feel like it's a good day's work -- maybe that's not the best approach anymore.” 他强调，未来的计算体系需要的不再是那种极其敏感、脆弱且容不得丝毫偏差的“独奏大牌”（prima donna）式软件，而是能够给予多于索取、具备韧性的“团队协作型”（team player）软件。 - 传统软件开发倾向于将系统可靠性外包给底层架构，一味追求执行效率的极限指标。 - 面对噪声和物理扰动，微调重试等局部修补无法从根本上消除脆弱性。 - “鲁棒优先”（Robust-first）理念主张软件应像团队合作者一样容忍缺陷，并主动维护整体系统的健康。 ### [12:55](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=775s) 中央独裁与分散自治：鲁棒优先计算的未来图景这番讨论最终落脚于对计算未来的终极想象。Dave Ackley 直言不讳地指出，当今单台计算机内部的 CPU 与内存（RAM）结构，本质上就是一种高度集权的“中央计划独裁制”（centrally planned dictatorship）。在冯·诺依曼架构下，中央处理器掌控着全局的所有指令调度，而内存中的数据和状态就像在角落里瑟瑟发抖的平民，只能毫无自主性地被动等待指令。这种架构虽然容易被人理解和制造，但极其脆弱，而且扩展能力极其有限——一旦处于核心地位的那个“独裁者”无法跑得更快，整个系统的性能与规模就碰到了无法逾越的物理天花板。 ```mermaid flowchart TD accTitle: 集中式与分布式计算架构对比 accDescr: 对比 CPU 居中调度的脆弱结构与类似自由市场的去中心化自治冗余结构 subgraph Centralized["传统架构：中央计划集权制"] CPU["中央 CPU (单一协调核心)"] -->|"分发指令"| M1["受控单元 1"] CPU -->|"分发指令"| M2["受控单元 2"] CPU -->|"分发指令"| M3["受控单元 3"] end subgraph Decentralized["鲁棒优先：市场自治与冗余"] N1["自治节点 A"] <-->|"相互补位"| N2["自治节点 B"] N2 <-->|"相互补位"| N3["自治节点 C"] N1 <-->|"相互补位"| N3 end ``` 为了突破这一瓶颈，Dave Ackley 提出了一种截然不同的设计哲学：将计算组织成类似于自由市场资本主义或民主自治的生态系统。他以现实生活中的咖啡店为例进行类比：每条街区可能都有三家咖啡店，从绝对资源利用率的角度看，这显然存在大量的冗余，效率远不如统一排期让每个人按计划喝咖啡来得精准；然而，一旦其中某家咖啡店倒闭或出现食品安全问题，其他咖啡店立刻就能接手客流，填补空白。正是这种冗余赋予了系统抵御风险的鲁棒性。Dave Ackley 总结道：“And if we think about organizing computation on a sort of democratic capitalist, individual autonomy kinda basis, then potentially, we can make a computer system that scales indefinitely.” 这种立足于个体自治与动态冗余的“鲁棒优先计算”（robust-first computing），正是让计算系统摆脱脆弱、迈向无限扩展的关键所在。 - 传统冯·诺依曼架构的核心瓶颈在于单点依赖：中央 CPU 无法无限制地提升时钟频率与控制范围。 - 绝对的效率往往以牺牲冗余为代价，一旦出现局部失效，整个系统便会面临崩溃风险。 - 去中心化的个体自治与功能冗余虽牺牲了部分峰值效率，却换来了极强的容错自愈能力与理论上无限横向扩展的可能。 ## Notable quotes > [00:01](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=1s) So for computers out in the real world, for systems meant to have actual responsibility, we should put robustness first, and view maximizing efficiency not as an inherent virtue, but more as a regrettable sometimes necessity. — Dave Ackley > [12:55](https://www.youtube.com/watch?v=7hwO8Q_TyCA&t=775s) And if we think about organizing computation on a sort of democratic capitalist, individual autonomy kinda basis, then potentially, we can make a computer system that scales indefinitely. — Dave Ackley ## Mentioned Dave Ackley, Communications of the ACM, 冯·诺依曼架构 ## Video description A high-level introduction to robust-first computing, with a sorting demo. [Source](https://www.youtube.com/watch?v=7hwO8Q_TyCA)

Source quotes

[0:01] Dave Ackley: So for computers out in the real world, for systems meant to have actual responsibility, we should put robustness first, and view maximizing efficiency not as an inherent virtue, but more as a regrettable sometimes necessity. [12:55] Dave Ackley: And if we think about organizing computation on a sort of democratic capitalist, individual autonomy kinda basis, then potentially, we can make a computer system that scales indefinitely.

Source quotes

[0:01] Dave Ackley: So for computers out in the real world, for systems meant to have actual responsibility, we should put robustness first, and view maximizing efficiency not as an inherent virtue, but more as a regrettable sometimes necessity. [12:51] Dave Ackley: And if we think about organizing computation on a sort of democratic capitalist, individual autonomy kinda basis, then potentially, we can make a computer system that scales indefinitely.

Original transcript

[0:01] For the safety of society, and to build [0:03] really big computers, we should pursue robust-first computing. [0:08] A system is robust if it tends to do something sensible even when its design [0:13] assumptions are [0:14] under stress or violated. Which sounds like a good thing -- [0:17] you see 'Robust' on feature checklists -- but at the same time, a lot of computer [0:21] science is about using computer hardware [0:24] efficiently. And that also sounds like a good thing, [0:27] but efficiency and robustness are at odds over redundancy [0:32] which robustness requires, but efficiency [0:35] eliminates. So for computers [0:38] out in the real world, for systems meant to have actual [0:41] responsibility, we should put robustness first, [0:45] and view maximizing efficiency not as an inherent virtue, [0:50] but more as a regrettable sometimes necessity. [0:53] So that's the core message of an essay I've got [0:57] in the October issue of CACM, and this is a little video [1:02] intro. So I want to start with a [1:08] Why do computers crash? [1:10] I've been asking that question around the country over the last year [1:14] and a half [1:15] and people say: bad hardware, bugs, user errors, [1:20] malware. But the deeper reason [1:23] is: we made 'em that way. We design computers to freeze up [1:29] at the first surprise. Why do we do that? [1:32] Well, as computer programmers, [1:36] we were counting on there being no surprises-- [1:39] everything being completely reliable, so that we could just put all the steps [1:43] that we needed in a row, and [1:44] we basically never gave a second thought to what would happen [1:49] if any of those steps went wrong. [1:55] That attitude goes all the way back to the earliest days [1:58] of digital computing. And at the very beginning it's like there was a contract [2:02] between the [2:03] computer engineers and manufacturers on one side and the computer scientists and [2:08] programmers [2:09] on the other side -- though they weren't really called that -- and the idea was: [2:13] Hardware shall provide reliability. It takes the unruly physical world and [2:19] turns it into [2:20] logic. Software's job is to take [2:23] logic and turn it into functions that are valuable; [2:28] turn into something that's desirable enough to provide enough [2:31] revenue to pay for the hardware and the software and everything together. [2:35] And that's the way the deal worked. At first, [2:40] hardware was incredibly expensive and [2:43] really weak. And that created incredible pressure on the software [2:48] to get as much desirability as possible out of the sunk cost [2:53] of whatever hardware you were dealing with. And so there was incredible [2:56] pressure to be correct for whatever [2:59] desirability meant, and then to be as efficient [3:02] as possible. And this sort of 'CEO' idea -- that software's about [3:07] Correctness and Efficiency Only -- is still the backbone [3:10] of computer science -- algorithm design and so forth. The world has changed [3:18] from then. Hardware is now much much cheaper, [3:22] it's often more powerful than we need for some given task, [3:26] and there are bugs [3:30] everywhere. Correctness -- it's not even clear what correctness means, [3:36] in most cases. So the world has changed [3:40] but in many ways we're still carrying this [3:44] original software CEO attitude with us. [3:47] For the safety of society, and to let us build really big computers, [3:53] we should change that attitude, and think about putting robustness first [3:57] and figuring out what that would mean. Building a body of science and [4:01] engineering knowledge [4:02] around computing robust-first. So, that's the pitch [4:06] Let's do a demo and then [4:09] wrap-up. So the example I do is [4:12] sorting, specifically, pairwise comparison sorting. [4:16] So let's, let's see what that is quickly. Alright, [4:19] I've got a deck of cards here.. We've got [4:23] cards, they're sort of magic cards. And we can %uh [4:26] shuffle them and square them up %uh [4:30] like that, okay? So if we take some of these cards [4:33] and [4:37] whups.. The thing that makes these cards weird [4:42] is they are like [4:45] alien cards from Roswell New Mexico, [4:49] something like that. So if we were to try to put these [4:52] in order, how would we do it? You know, is the two suns, with the thing, better [4:57] than the green and the red.. [4:59] Who knows? Well it turns out, in addition to this alien card deck, we got an [5:05] alien card comparison device. And that's what this thing up here is. [5:08] And the way it works is, we stick a couple of cards in it, and it crunches over them and [5:12] it decides. Okay this one is higher [5:14] than this one. So then we can stick this one in and compare it to [5:19] that guy. Alright well this one's higher, and so on. [5:23] Do this, and alright this one's higher. [5:27] Alright so in fact that guy.. this guy just kind of worked his way down to the bottom [5:33] So now do we know that these guys are all in order yet? Well we don't exactly because [5:37] we haven't compared [5:37] all of them to all of them, but we can try that. It's easier to move the comparison thing. [5:42] Alright, those guys seem all right. [5:45] These guys [5:48] see they also wanted to swap. And finally these guys.. [5:52] Alright, they're happy the way they are. [5:56] So is that it? Are we done? [6:03] Now it said they're both equal. Well, let's say it's all right. [6:07] Those guys are still [6:10] in order and [6:14] those guys are still in order, OK. So there it is. So what we've done here [6:18] is what's called 'bubble sort'. or sort of a part of the bubble sort algorithm. [6:22] And bubble sort is kind of the black sheep [6:26] of sorting algorithms. All we do [6:29] is, well we take our comparison thing and we compare adjacent cards, and if they come out [6:33] out of order we swap them. Then we go back to the beginning and we do it again, and we do it [6:36] enough times until we've gotten [6:38] everyone, so that's enough time for -- if this guy on the right-hand end [6:42] actually belonged all the way on the other end, he has time to bubble one by one [6:45] up to the other side: [6:47] Bubble sort. Now, [6:51] computer scientists love to hate bubble sort because [6:55] it's so inefficient. But here's the twist: [7:02] What if it's the case that our alien card comparison device [7:07] fails sometimes? Sometimes gets it wrong. [7:11] Kind of saw where things go up, and then they were equal [7:16] If our comparison routine is not guaranteed to be right, [7:19] we can't guarantee that we're actually going to get the correct answer in the [7:22] 'strict correct' sense. [7:24] So we need some kinda way of saying: Well if you got it wrong, did you get it [7:28] _really_ wrong? [7:30] And so we made up this thing which we called 'positional error'. [7:34] Okay? And so the idea is, if we were sorting just these few numbers. [7:37] 1234, and those are in correct order: 1 is where it's supposed to be, 23 and so on. [7:42] So one is off by zero positions, 2 is off by zero positions, and so on, they [7:46] all add up. [7:46] Here, 2 and 1 have been swapped, so 2 is one position off, it wants to be here. [7:52] 1 is also one position off--wants to be there, the others are fine, and so on. [7:55] OK? If we get 'em exactly backwards that's one of the cases were it's the [7:58] worst possible [7:59] positional error. The four wants to go 1,2,3 spots, [8:03] the 1 wants to go 1,2,3 spots. The 2 are 3 want to reverse. [8:07] Okay? So we could take our [8:10] alien comparison device -- which in fact did act a little bit strange, [8:15] we had that case where it seemed to [8:19] score things differently when we tried it times, now it seems like it's all right now. [8:25] And suppose instead of doing bubble sort we did a [8:28] more efficient sorting algorithm, in this case. [8:31] And the one I want to look at -- oops -- the one I want to look at is called [8:35] 'merge sort'. And merge sort is one of the [8:38] class a very efficient algorithms the computer science has developed over the [8:42] decades [8:43] %um, and it's, it's being used a lot, in fact it's still [8:47] getting more popular lately. almost surely, if you have a general-purpose [8:51] computer or phone, [8:53] what-have-you, in your house there's probably [8:56] an example of merge sort in your software someplace [9:00] and the idea is: You take whatever you need to sort you break them into two groups you [9:03] break those into two groups, until you get down to tiny groups of two. [9:07] You sort those, just sorting them by swapping if need be, [9:10] and then you start merging the little groups of two into groups of four [9:14] and then groups of four into groups of eight and so on until you get all the way to the [9:18] end. [9:18] Okay? Now this is a clever idea for at least two reasons. So the [9:22] efficiency win #1 is once you have these sorted groups that you're [9:27] putting together [9:28] you only have to check the lead guy. "Is this guy less than that guy?" [9:32] Because you know all the rest of them are bigger. So you can use the front guy as [9:36] sort of a proxy for comparing against [9:38] all the rest of each group. It's very clever. [9:41] Second win is, especially when we're getting to the end to the algorithm, is we've [9:45] got these big groups that we're merging together [9:48] when we decide to take this guy and then this guy and then this guy, [9:51] we're moving those items long distances [9:54] in the array. So if you think in terms of positional error, like is this guy way [9:58] out of position, [10:00] well when we make a long swap, we're reducing the positional error [10:04] a lot. And that's what makes it efficient. [10:07] All of the efficient sorting algorithms for pairwise comparisons [10:11] are based on that idea. But on the other hand, [10:15] the flip side of making it efficient is: What if it doesn't work right? [10:19] What if there's a failure in the comparison? So here's a case where it [10:22] works. [10:23] We have, we've split them and now we're comparing the twos. 7 is less than 8. [10:28] 2 is going to be less than 4 so it goes first. That ends the round of [10:31] twos. Now we're merging twos into fours. [10:34] And then we'll do two twos into a four, another two twos into a four [10:39] and then finally we will take two fours and merged them into an eight. [10:42] Now, especially in this last round here, the 2 was going a [10:45] long distance over the ways. OK? [10:49] So the increased efficiency [10:53] comes from the fact that merge sort is designed so that it can end up making [10:58] these [10:58] long distance moves. It does one comparison then moves guys a long [11:03] way so it has a large leverage. [11:08] And the increased efficiency implies [11:11] increased leverage and so if that's the case [11:15] that the comparison routine might fail [11:19] sometimes, then that leverage which just helped us so much, [11:23] can now come around and hurt us so much. And here's the [11:26] data that we got: [11:30] Imagine shuffling a deck of 52 cards and trying to sort them using the alien [11:35] comparison device, [11:36] which gets the comparison right -- less than, greater than, or equal -- [11:40] ninety percent of the time but in this example 10 percent of the time it just [11:44] gives a crazy random answer. [11:47] If we look at merge sort -- that's the guy in the middle -- or quick sort -- [11:50] another one of these efficient algorithms -- they get pretty well slaughtered by this. [11:55] And on the y-axis going up and down we have the total card positional error. [12:00] Now, depending on how the shuffling actually works, sometimes it's worse and [12:03] sometime it's better, so these are averages. [12:06] But, look at bubble sort. [12:09] People look at this and they think: Well, you know, this is easy to fix. [12:12] We can just, you know, try it a buncha times before deciding whether to swap or not, [12:16] and so on. [12:17] There's more details in the essay [12:21] The point I want to make is just this: That [12:24] because we have the software CEO mindset, [12:28] that says "Reliability is someone else's problem!" [12:31] and we can feel free to screw the efficiency down as hard as we can, and feel [12:36] like it's a good day's work -- [12:38] maybe that's not the best approach anymore. Maybe we have to say what we're [12:42] really looking for is not the high-strung prima donna piece of software [12:46] but [12:47] team player software that gives better than they get. [12:51] So OK. It comes down to a question [12:55] about what do we imagine the future of computing? [12:58] And not to put too fine a point on it but [13:02] what we have now, inside a single computer, a CPU and [13:05] RAM, is essentially sort of centrally planned dictatorship. [13:09] The CPU was there controlling everything and all [13:12] the peons are just cowering in the memory, doing nothing, until they're told [13:17] exactly what to do [13:18] and then they do it or they don't. And it's easy to understand how to [13:22] make such a thing; it seems logical from one point of view, [13:26] but it's very fragile, and it only gets so big. [13:30] Eventually you can't have that one guy in the center saying what to do. [13:34] He can't go any faster. The alternative is something more like [13:39] free-market capitalism, something more like democracy. [13:43] Now I mean if you know, we look at in the world and there's like three coffee [13:47] shops on every block. [13:48] That's clearly redundant. Most those coffee shops [13:52] are not operating at the peak efficiency that they could if we scheduled when [13:57] everybody was supposed to go get their cup of coffee. [14:00] But on the other hand, if one of those coffee shops goes out of [14:03] business, or poisons some of its customers or whatever [14:06] the other coffee shops are more than happy to pick up the slack. [14:09] The redundancy makes it robust. And if we think about organizing [14:14] computation on a sort of democratic [14:17] capitalist, individual autonomy kinda basis, [14:22] then potentially, we can make a computer system that scales [14:26] indefinitely. [14:29] All right. That's it. That's the robust-first [14:33] computing concept. If you get it, you got it. [14:37] Thanks for watching.