Dis-alg

来自Algorithm Wiki
跳转至： 导航、 搜索

分布式计算理论

基础理论

% 分布式计算中的“可计算性理论” 

@article{Herlihy91,
author = {Herlihy, Maurice},
title = {Wait-free Synchronization},
journal = {ACM Trans. Program. Lang. Syst.},
issue_date = {Jan. 1991},
volume = {13},
number = {1},
month = jan,
year = {1991},
issn = {0164-0925},
pages = {124--149},
numpages = {26},
url = {http://doi.acm.org/10.1145/114005.102808},
publisher = {ACM},
}

// consensus的著名 FLP 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 },
}

分布谓词检测

// 谓词检测工作的一个通用框架，以及相应的通用算法 

@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},
}

分布共享内存与分布数据一致性

% 分布共享内存 (DSM) 概念 (期刊TOCS版本) 

@article{Li89,
author = {Li, Kai and Hudak, Paul},
title = {Memory Coherence in Shared Virtual Memory Systems},
journal = {ACM Trans. Comput. Syst.},
issue_date = {Nov. 1989},
volume = {7},
number = {4},
month = nov,
year = {1989},
issn = {0734-2071},
pages = {321--359},
numpages = {39},
url = {http://doi.acm.org/10.1145/75104.75105},
doi = {10.1145/75104.75105},
acmid = {75105},
publisher = {ACM},
address = {New York, NY, USA},
}

% Lamport 提出 atomic/regular/safe registers 的概念 (Part I: Basic formalism) 

@article{Lamport86,
author={Lamport, Leslie},
title={On interprocess communication. Part I: Basic formalism},
journal={Distributed Computing},
volume={1},
number={2},
pages={77-85},
year={1986},
url={http://dx.doi.org/10.1007/BF01786227},
publisher={Springer-Verlag},
}

% Lamport 提出 atomic/regular/safe registers 的概念 (Part II: Algorithms) 

@article{Lamport86,
author={Lamport, Leslie},
title={On interprocess communication. Part II: Algorithms},
journal={Distributed Computing},
volume={1},
number={2},
pages={86-101},
year={1986},
url={http://dx.doi.org/10.1007/BF01786228},
publisher={Springer-Verlag},
}

% 存储访问的公理化建模 

@article{Misra86,
author = {Misra, J.},
title = {Axioms for Memory Access in Asynchronous Hardware Systems},
journal = {ACM Trans. Program. Lang. Syst.},
issue_date = {Jan. 1986},
volume = {8},
number = {1},
month = jan,
year = {1986},
issn = {0164-0925},
pages = {142--153},
numpages = {12},
url = {http://doi.acm.org/10.1145/5001.5007},
doi = {10.1145/5001.5007},
acmid = {5007},
publisher = {ACM},
address = {New York, NY, USA},
}


% 定义linearizability (将 Lamport 的 atomic registers 定义扩展到更复杂的数据结构) 

@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},
}

% 在 message-passing 系统上模拟 atomic registers 

@article{Attiya95,
author = {Attiya, Hagit and Bar-Noy, Amotz and Dolev, Danny},
title = {Sharing Memory Robustly in Message-passing Systems},
journal = {J. ACM},
issue_date = {Jan. 1995},
volume = {42},
number = {1},
month = jan,
year = {1995},
issn = {0004-5411},
pages = {124--142},
numpages = {19},
url = {http://doi.acm.org/10.1145/200836.200869},
publisher = {ACM},
}

// 多写的register的regularity的定义 

@article{Shao11,
author = {Shao, Cheng and Welch, Jennifer L. and Pierce, Evelyn and Lee, Hyunyoung},
title = {Multiwriter Consistency Conditions for Shared Memory Registers},
journal = {SIAM J. Comput.},
issue_date = {February 2011},
volume = {40},
number = {1},
month = jan,
year = {2011},
issn = {0097-5397},
pages = {28--62},
numpages = {35},
url = {http://dx.doi.org/10.1137/07071158X},
doi = {10.1137/07071158X},
acmid = {2078669},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
keywords = {multiwriter registers, mutual exclusion, quorum systems, regularity, shared memory consistency},
}


// 分布数据一致性的后验分析 

@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},
}

经典分布式算法

Leader Election 算法

互斥算法

% Lamport's Bakery 算法 

@article{Lamport74,
author = {Lamport, Leslie},
title = {A New Solution of Dijkstra's Concurrent Programming Problem},
journal = {Commun. ACM},
issue_date = {Aug. 1974},
volume = {17},
number = {8},
month = aug,
year = {1974},
issn = {0001-0782},
pages = {453--455},
numpages = {3},
url = {http://doi.acm.org/10.1145/361082.361093},
publisher = {ACM},
}

% 相关趣闻请参阅 http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#lamport-mutual-solved 

@article{Lamport91,
author = {Lamport, Leslie},
title = {The Mutual Exclusion Problem Has Been Solved},
journal = {Commun. ACM},
issue_date = {Jan. 1991},
volume = {34},
number = {1},
month = jan,
year = {1991},
pages = {110--ff.},
url = {http://doi.acm.org/10.1145/99977.278147},
publisher = {ACM},
}

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}}
}

经典分布式系统

基础系统理论

% CAP 定理 (由Eric Brewer在2000年提出; 此处所选是12年后Gilbert和Lynch对CAP定理所作的阐释。) 

@article{Gilbert12,
author = {Seth Gilbert and Nancy A. Lynch},
title = {Perspectives on the CAP Theorem},
journal ={Computer},
volume = {45},
number = {2},
year = {2012},
pages = {30-36},
doi = {http://doi.ieeecomputersociety.org/10.1109/MC.2011.389},
publisher = {IEEE Computer Society},
}

% PACELC 权衡 (可看作CAP定理的扩展) 

@article{Abadi12, 
author={Abadi, Daniel J.}, 
title={Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story}, 
journal={Computer}, 
year={2012}, 
month={Feb},
volume={45}, 
number={2}, 
pages={37-42}, 
doi={10.1109/MC.2012.33}, 
publisher = {IEEE Computer Society},
}

分布式存储系统

% 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},
}

% Google

% 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},
}


// 数据驱动的协同 

@article{Gelernter85,
author = {Gelernter, David},
title = {Generative Communication in Linda},
journal = {ACM Trans. Program. Lang. Syst.},
issue_date = {Jan. 1985},
volume = {7},
number = {1},
month = jan,
year = {1985},
issn = {0164-0925},
pages = {80--112},
numpages = {33},
url = {http://doi.acm.org/10.1145/2363.2433},
doi = {10.1145/2363.2433},
acmid = {2433},
publisher = {ACM},
address = {New York, NY, USA},
}

附录

分布式计算理论会议：PODC

分布式计算理论期刊：DC(Distributed Computing)

理论会议：STOC，FOCS

理论期刊：JACM，SIAM J. Computing

系统会议：OSDI，SOSP

取自“http://www.bigoh.net/wiki/index.php?title=Dis-alg&oldid=1100”