流式算法总论：数据流模型、频率矩下界与线性 sketch
一遍扫描、内存远小于数据时能算什么：梳理三种流模型、Morris 到 AMS 与 Indyk 的谱系、通信复杂度下界，实测 AMS F2 sketch 误差随计数器数的变化，说明线性 sketch 为何可合并、可删除，并把本系列 30 到 35 篇串成路线图。
lower-bound 标签归档
共 2 篇文章 · 返回首页
【分布式系统百科】05 · 分布式系统的复杂性度量：消息复杂度、轮次复杂度与空间下界
顺序算法用时间复杂度和空间复杂度就能衡量好坏。分布式算法多了消息复杂度、轮次复杂度和容错数量三个维度，三者之间存在不可调和的 trade-off。本文从选主、共识、广播三个典型问题出发，梳理这些度量指标的定义、下界和工程影响。