《挑战程序设计竞赛》读书笔记(四)格点问题的证明

《挑战程序设计竞赛》读书笔记(四)格点问题的证明

《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题,该解答给出了结果,但中间过程省略了不少内容。本文补充了相关的证明和解释。
问题描述如下:
格点是指平面坐标系中,横纵坐标都是整数的点。给定平面上两个格点,P1(x1,y1),P2(x2,y2),则线段P1P2上除了P1和P2外,有几个格点?事实上,该问题答案为|x2-x1|和|y2-y1|的最大公约数减1,并给出了一个图示。本文对该结论给出了证明。

Google Spanner论文解读

Google Spanner论文解读

Google Spanner是google在2012年公开的存储系统,它的最大特点就是数据分布在全球范围内,支持外部一致性的分布式事务。本文依据论文解读了该系统的设计和实现。

FLP impossibility证明 阅读笔记

FLP impossibility证明 阅读笔记

分布式系统一致性协议里面有一个FLP impossibility的结论,这个结论是说,在分布式系统中,异步网络(消息延迟可能任意大或丢失,消息可能乱序),只要有一个进程失效(进程死亡或者足够长时间不响应),就不可能设计出一个一致性协议。
该结论由Fisher、Lynch、Paterson三位分布式系统领域的科学家在1985年在论文Impossibility of Distributed Consensus with One Faulty Process证明。本文解读了证明过程。

再读GFS论文

再读GFS论文

再读GFS的一些笔记。主要涉及GFS架构、Chunk大小选择的一些折中考量、元数据管理及锁、写数据流程、GFS一致性模型的理解、快照的实现原理、过期失效副本检测等几个问题。