Dis-alg
来自Algorithm Wiki
目录
分布式计算理论
分布谓词检测
// 谓词检测工作的一个通用框架，以及相应的通用算法
@article{Babaoglu96,
author = {Babao\u{g}lu, \"{O}zalp and Fromentin, Eddy and Raynal, Michel},
title = {A unified framework for the specification and run-time detection of dynamic properties in distributed computations},
journal = {J. Syst. Softw.},
volume = {33},
number = {3},
year = {1996},
pages = {287--298},
doi = {http://dx.doi.org/10.1016/0164-1212(96)00027-1 },
publisher = {Elsevier Science Inc.},
}
// 逻辑时钟的讨论，分布式计算领域的奠基性paper
@article{Lamport78,
author = {Leslie Lamport},
title = {Time, clocks, and the ordering of events in a distributed system},
journal = {Commun. ACM},
volume = {21},
number = {7},
year = {1978},
issn = {0001-0782},
pages = {558--565},
doi = {http://doi.acm.org/10.1145/359545.359563 },
publisher = {ACM},
address = {New York, NY, USA},
}
// 逻辑向量时钟的概念，理论与算法实现
@inproceedings{Mattern89,
author = {Friedemann Mattern},
title = {Virtual time and global states of distributed systems},
booktitle = "Proc. International Workshop on Parallel and Distributed Algorithms",
address = "Holland",
year = {1989},
pages = {215--226},
}
分布共享内存与分布数据一致性
atomic register
% 定义linearizability (将Lamport的atomic register定义扩展到更复杂的数据结构)
@article{Herlihy90,
author = {Herlihy, Maurice P. and Wing, Jeannette M.},
title = {Linearizability: a correctness condition for concurrent objects},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {12},
issue = {3},
month = {July},
year = {1990},
pages = {463--492},
url = {http://doi.acm.org/10.1145/78969.78972},
publisher = {ACM},
}
// 分布数据一致性的后验分析
@inproceedings{Golab11,
author = {Golab, Wojciech and Li, Xiaozhou and Shah, Mehul A.},
title = {Analyzing consistency properties for fun and profit},
booktitle = {Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
series = {PODC '11},
year = {2011},
pages = {197--206},
url = {http://doi.acm.org/10.1145/1993806.1993834 },
publisher = {ACM},
}
其它
// consensus的著名impossibility result
@article{Fischer85,
author = {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael S.},
title = {Impossibility of Distributed Consensus with One Faulty Process},
journal = {J. ACM},
issue_date = {April 1985},
volume = {32},
number = {2},
month = apr,
year = {1985},
issn = {0004-5411},
pages = {374--382},
numpages = {9},
url = {http://doi.acm.org/10.1145/3149.214121 },
doi = {10.1145/3149.214121},
acmid = {214121},
publisher = {ACM},
address = {New York, NY, USA},
}
// progress相关性质的本源
@inproceedings{Herlihy2011,
author = {Herlihy, Maurice and Shavit, Nir},
title = {On the Nature of Progress},
booktitle = {Proceedings of the 15th International Conference on Principles of Distributed Systems},
series = {OPODIS'11},
year = {2011},
isbn = {978-3-642-25872-5},
location = {Toulouse, France},
pages = {313--328},
numpages = {16},
url = {http://dx.doi.org/10.1007/978-3-642-25873-2_22 },
}
经典分布式算法
Mutual Exclusion 算法
Consensus 算法
% Lamport's Paxos 算法
@misc{Lamport01,
author = {Leslie Lamport},
title = {Paxos Made Simple},
year = {2001},
month = {nov},
howpublished = {\url{https://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf}}
}
经典分布式系统
分布式存储系统
% Amazon's Dynamo
@inproceedings{DeCandia07,
author = {DeCandia, Giuseppe and Hastorun, Deniz and Jampani, Madan and Kakulapati, Gunavardhan and Lakshman,
Avinash and Pilchin, Alex and Sivasubramanian, Swaminathan and Vosshall, Peter and Vogels, Werner},
title = {Dynamo: Amazon's Highly Available Key-value Store},
booktitle = {Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles},
series = {SOSP '07},
year = {2007},
pages = {205--220},
url = {http://doi.acm.org/10.1145/1294261.1294281},
doi = {10.1145/1294261.1294281},
publisher = {ACM},
}
% Facebook's Tao for social graph
@inproceedings {Bronson13,
author = {Nathan Bronson and Zach Amsden and George Cabrera and Prasad Chakka and Peter Dimov and Hui Ding
and Jack Ferris and Anthony Giardullo and Sachin Kulkarni and Harry Li and Mark Marchukov and Dmitri Petrov
and Lovro Puzar and Yee Jiun Song and Venkat Venkataramani},
title = {TAO: Facebook{\textquoteright}s Distributed Data Store for the Social Graph},
booktitle = {Presented as part of the 2013 USENIX Annual Technical Conference (USENIX ATC 13)},
year = {2013},
pages = {49--60},
url = {https://www.usenix.org/conference/atc13/technical-sessions/presentation/bronson},
publisher = {USENIX},
}
% Yahoo!'s PNUTS
@article{Cooper08,
author = {Cooper, Brian F. and Ramakrishnan, Raghu and Srivastava, Utkarsh and Silberstein, Adam and Bohannon,
Philip and Jacobsen, Hans-Arno and Puz, Nick and Weaver, Daniel and Yerneni, Ramana},
title = {PNUTS: Yahoo!'s Hosted Data Serving Platform},
journal = {Proc. VLDB Endow.},
issue_date = {August 2008},
volume = {1},
number = {2},
month = aug,
year = {2008},
pages = {1277--1288},
url = {http://dx.doi.org/10.14778/1454159.1454167},
doi = {10.14778/1454159.1454167},
publisher = {VLDB Endowment},
}
% Lamport's Paxos implemented by Google
@inproceedings{Chandra07,
author = {Chandra, Tushar D. and Griesemer, Robert and Redstone, Joshua},
title = {Paxos Made Live: An Engineering Perspective},
booktitle = {Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing},
series = {PODC '07},
year = {2007},
pages = {398--407},
url = {http://doi.acm.org/10.1145/1281100.1281103},
publisher = {ACM},
}
% Google's Bigtable
@article{Chang08,
author = {Chang, Fay and Dean, Jeffrey and Ghemawat, Sanjay and Hsieh, Wilson C. and Wallach, Deborah A. and Burrows, Mike and Chandra, Tushar and Fikes, Andrew and Gruber, Robert E.},
title = {Bigtable: A Distributed Storage System for Structured Data},
journal = {ACM Trans. Comput. Syst.},
issue_date = {June 2008},
volume = {26},
number = {2},
month = jun,
year = {2008},
pages = {4:1--4:26},
articleno = {4},
url = {http://doi.acm.org/10.1145/1365815.1365816},
publisher = {ACM},
}
% Google's Megastore: built upon Bigtable, providing transactional semantics
@inproceedings{Baker11,
title = {Megastore: providing scalable, highly available storage for interactive services},
author = {Jason Baker and Chris Bond and James C. Corbett and JJ Furman and Andrey Khorlin and James Larson and Jean-Michel Leon and Yawei Li and Alexander Lloyd and Vadim Yushprakh},
booktitle = {Proc. CIDR'11, Conference on Innovative Data System Research},
year = {2011},
pages = {223--234}
URL = {http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf},
}
% Google's Spanner: Using Paxos and atomic clocks to implement ACID transactions
@inproceedings{Corbett:2012,
author = {Corbett, James C. and Dean, Jeffrey and Epstein, Michael and Fikes, Andrew and Frost, Christopher and Furman, J. J. and Ghemawat, Sanjay and Gubarev, Andrey and Heiser, Christopher and Hochschild, Peter and Hsieh, Wilson and Kanthak, Sebastian and Kogan, Eugene and Li, Hongyi and Lloyd, Alexander and Melnik, Sergey and Mwaura, David and Nagle, David and Quinlan, Sean and Rao, Rajesh and Rolig, Lindsay and Saito, Yasushi and Szymaniak, Michal and Taylor, Christopher and Wang, Ruth and Woodford, Dale},
title = {Spanner: {Google's} globally-distributed database},
booktitle = {Proc. OSDI'12, USENIX Symposium on Operating Systems Design and Implementation},
year = {2012},
pages = {251--264},
url = {http://dl.acm.org/citation.cfm?id=2387880.2387905},
publisher = {USENIX},
}
% Facebook's Cassandra (Open source counterpart of Amazon's Dynamo)
@article{Lakshman10,
author = {Lakshman, Avinash and Malik, Prashant},
title = {Cassandra: A Decentralized Structured Storage System},
journal = {SIGOPS Oper. Syst. Rev.},
issue_date = {April 2010},
volume = {44},
number = {2},
month = apr,
year = {2010},
pages = {35--40},
url = {http://doi.acm.org/10.1145/1773912.1773922},
doi = {10.1145/1773912.1773922},
publisher = {ACM},
}
@misc{Cassandra,
title = {Apache Cassandra project website},
note ={\url{https://cassandra.apache.org}},
key = {Apache Cassandra},
}
% HBase
@misc{HBase,
title = {Apache HBase project website},
note ={\url{https://hbase.apache.org}},
key = {Apache HBase},
}
分布式协同服务
% Google's Chubby: lock service
@inproceedings{Burrows:2006,
author = {Burrows, Mike},
title = {The {Chubby} lock service for loosely-coupled distributed systems},
booktitle = {Proc. OSDI'06, USENIX Symposium on Operating Systems Design and Implementation},
year = {2006},
pages = {335--350},
url = {http://dl.acm.org/citation.cfm?id=1298455.1298487},
publisher = {USENIX},
}
% Yahoo!'s Zookeeper
@inproceedings{Hunt10,
author = {Hunt, Patrick and Konar, Mahadev and Junqueira, Flavio P. and Reed, Benjamin},
title = {{ZooKeeper}: wait-free coordination for Internet-scale systems},
booktitle = {Proc. ATC'10, USENIX Annual Technical Conference},
year = {2010},
location = {Boston, MA},
pages = {145--158},
url = {http://portal.acm.org/citation.cfm?id=1855840.1855851},
publisher = {USENIX},
}
% Zab protocol in Zookeeper: adapted from Paxos
@inproceedings{Junqueira11,
author = {Junqueira, Flavio P. and Reed, Benjamin C. and Serafini, Marco},
title = {Zab: high-performance broadcast for primary-backup systems},
booktitle = {Proc. DSN'11, IEEE/IFIP Conference on Dependable Systems and Networks},
year = {2011},
pages = {245--256},
url = {http://dx.doi.org/10.1109/DSN.2011.5958223},
publisher = {IEEE},
}
附录
分布式计算理论会议：PODC
分布式计算理论期刊：DC(Distributed Computing)
理论会议：STOC，FOCS
理论期刊：JACM，SIAM J. Computing
系统会议：OSDI，SOSP
