consensus/pdf/theory.bib

%A
@article{archetti12game,
  title={Game theory of public goods in one-shot social dilemmas without assortment},
  author={Archetti, Marco and Scheuring, Istvan},
  journal={Journal of theoretical biology},
  volume={299},
  pages={9--20},
  year={2012},
  publisher={Elsevier}
} 

@article{ alistarh18communication,
	author = {Dan Alistarh and James Aspnes and Valerie King and
			Jared Saia},
	title = {\href{https://link.springer.com/article/10.1007/s00446-017-0315-1}{Communication-efficient randomized consensus}},
	volume = 31,
	pages = {pages489–501},
	month = nov,
	year = 2018,
}

@article{ aspnes03randomized,
	author = {James Aspnes},
	title = {\href{https://link.springer.com/article/10.1007%2Fs00446-002-0081-5}{Randomized protocols for asynchronous consensus}},
	journal = {Distributed Computing},
	volume = 16,
	number = {2--3},
	pages = {165--175},
	month = sep,
	year = 2003,
}

@article{ aspnes15faster,
	author = {James Aspnes},
	title = {\href{https://link.springer.com/article/10.1007%2Fs00446-013-0195-y}{Faster randomized consensus with an oblivious adversary}},
	journal = {Distributed Computing},
	volume = 28,
	number = 1,
	month = feb,
	year = 2015,
	pages = {21-29},
}

@inproceedings{ aumann96efficient,
	author = {Yonatan Aumann and Michael A. Bender},
	title = {\href{https://doi.org/10.1007/3-540-61440-0_164}{Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler}},
	booktitle = {\bibconf[23rd]{ICALP}{International Colloquium on
			Automata, Languages and Programming}},
	month = jul,
	year = 1996,
	location = {Paderborn, Germany},
}

@article{ aumann05efficient,
	author = {Yonatan Aumann and Michael A. Bender},
	title = {\href{https://link.springer.com/article/10.1007%2Fs00446-004-0113-4}{Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler}},
	journal = {Distributed Computing},
	volume = 17,
	number = 3,
	month = mar,
	year = 2005,
	pages = {191-207},
}

@article{avarikioti19divide,
  title={Divide and Scale: Formalization of Distributed Ledger Sharding Protocols},
  author={Avarikioti, Georgia and Kokoris-Kogias, Eleftherios and Wattenhofer, Roger},
  journal={arXiv preprint arXiv:1910.10434},
  year={2019}
}

@article{ awerbuch85complexity,
	author = {Baruch Awerbuch},
	title = {\href{https://dl.acm.org/citation.cfm?id=4227}{Complexity of Network Synchronization}},
	journal = {Journal of the Association for Computing Machinery},
	volume = 32,
	number = 4,
	month = oct,
	year = 1985,
	pages = {804-823},
}


%B

@article{babai2006probability,
  title={The probability of generating the symmetric group when one of the generators is random},
  author={Babai, Laszlo and Hayes, Thomas P.},
  journal={Publ. Math. Debrecen},
  volume={69},
  number={3},
  pages={271--280},
  year={2006},
  publisher={Citeseer}
}

@inproceedings{ bangalore18almost,
	author = {Laasya Bangalore and Ashish Choudhury and Arpita Patra},
	title = {\href{https://dl.acm.org/citation.cfm?id=3212735}{Almost-Surely Terminating Asynchronous Byzantine Agreement Revisited}},
	booktitle = {\bibconf{PODC}{Principles of Distributed Computing}},
	month = jul,
	year = 2018,
	pages = {295-304},
}

@incollection{bellare03forward,
  title={Forward-security in private-key cryptography},
  author={Bellare, Mihir and Yee, Bennet},
  booktitle = {\bibconf['03]{CT-RSA}{Topics in Cryptology - CT RSA  }},
  year={2003},
}

@inproceedings{bellare93defining,
  title={On defining proofs of knowledge},
  author={Bellare, Mihir and Goldreich, Oded},
  booktitle = {\bibconf['92]{CRYPTO}{Advances in Cryptology  }},
  year={1993},
}

@inproceedings{ ben-or83another,
	author = {Michael Ben-Or},
	title = {Another advantage of free choice:
			Completely asynchronous agreement protocols},
	booktitle = {Principles of Distributed Computing (PODC)},
	year = 1983,
}

@inproceedings{ ben-or85fast,
	author = {Michael Ben-Or},
	title = {\href{https://dl.acm.org/citation.cfm?id=323609}{Fast Asynchronous Byzantine Agreement (Extended Abstract)}},
	booktitle = {\bibconf[4th]{PODC}{Principles of Distributed Computing}},
	year = 1985,
	pages = {149-151},
	location = {Minaki, Ontario, Canada},
}

@inproceedings{ bracha84asynchronous,
	author = {Gabriel Bracha},
	title = {\href{https://dl.acm.org/citation.cfm?id=806743}{An asynchronous [(n-1)/3]-Resilient Consensus Protocol}},
	booktitle = {\bibconf[3rd]{PODC}{ACM Symposium on Principles of Distributed Computing}},
	year = 1984,
	location = {Vancouver, British Columbia, Canada},
}
% pages = {154-162},

@article{ bracha85asynchronous,
	author = {Gabriel Bracha and Sam Toueg},
	title = {\href{https://dl.acm.org/citation.cfm?id=214134}{Asynchronous Consensus and Broadcast Protocols}},
	journal = {Journal of the Association for Computing Machinery (JACM)},
	volume = 32,
	number = 4,
	year = 1985,
}
% pages = {824-840},


%C

@book{ cachin11introduction,
	author = {Christian Cachin and Rachid Guerraoui Lu\'is Rodrigues},
	title  = {Introduction to Reliable and Secure Distributed Programming},
	publisher = {Springer},
	month = feb,
	year = 2011,
	isbn = {978-3642152597},
}

@misc{ cachin19asymmetric,
	author = {Christian Cachin and Bj\"orn Tackmann},
	title = {\href{https://arxiv.org/pdf/1906.09314.pdf}{Asymmetric Distributed Trust}},
	month = jun,
	year = 2019,
}

@techreport{ camenisch97proof,
  author = {Jan Camenisch and Markus Stadler},
  title = {Proof Systems for General Statements about Discrete
      Logarithms},
  institution = {Dept. of Computer Science, ETH Zurich},
  year = 1997,
  month = {March},
  number = 260,
}

@inproceedings{ canetti93fast,
	author = {Ran Canetti and Tal Rabin},
	title = {\href{https://dl.acm.org/citation.cfm?id=167105}{Fast Asynchronous Byzantine Agreement with Optimal Resilience}},
	booktitle = {\bibconf[25th]{STOC}{ACM Symposium on Theory of computing}},
	month = may,
	year = 1993,
	location = {San Diego, California, USA},
	pages = {42-51},
}

% long version: unpublished?
@misc{ canetti98fast,
	author = {Ran Canetti and Tal Rabin},
	title = {\href{http://people.csail.mit.edu/canetti/materials/cr93.ps}{Fast Asynchronous Byzantine Agreement with Optimal Resilience}},
	month = sep,
	year = 1998,
	institution = {IBM T.J. Watson Research Center},
}

@inproceedings{ clarkson08civitas ,
	author = {Clarkson, M.R. and Chong, S. and Myers, A.C.},
	booktitle = {IEEE \bibconf{SP}{Symposium on Security and Privacy}},
	title = {Civitas: Toward a Secure Voting System},
	year = {2008},
	month = {may},
}

@article{ cristian95atomic,
	author = {Flaviu Cristian and Houtan Aghili and Ray Strong and
			Danny Dolev},
	title = {\href{https://www.sciencedirect.com/science/article/pii/S0890540185710607}{Atomic Broadcast: From Simple Message Diffusion to Byzantine Agreement}},
	journal = {Information and Computation},
	volume = 118,
	number = 1,
	month = apr,
	year = 1995,
	pages = {158-179},
}

%D

@article{ defago04total,
	author = {Xavier D\'efago and Andr\'e Schiper and P\'eter Urb\'an},
	title = {\href{https://dl.acm.org/doi/abs/10.1145/1041680.1041682}{Total Order Broadcast and Multicast Algorithms:Taxonomy and Survey}},
	journal = {ACM Computing Surveys},
	month = dec,
	year = 2004,
}

%F

@article{ feigenbaum08graph,
	author = {Joan Feigenbaum and Sampath Kannan and Andrew McGregor
			and Siddharth Suri and Jian Zhang},
	title = {Graph Distances in the Data-Stream Model},
	journal = {SIAM Journal on Computing},
	volume = 38,
	year = 2008,
	pages = {1709-1727},
}

@article{ feigenbaum05graph,
	author = {Joan Feigenbaum and Sampath Kannan and Andrew McGregor
			and Siddharth Suri and Jian Zhang},
	title = {On Graph Problems in a Semi-Streaming Model},
	journal = {Theoretical Computer Science},
	volume = 348,
	year = 2005,
	pages = {207-216},
}

@article{ feigenbaum05computing,
	author = {Joan Feigenbaum and Sampath Kannan and Jian Zhang},
	title = {Computing Diameter in the Streaming and Sliding-Window Models},
	journal = {Algorithmica},
	volume = 41,
	year = 2005,
	pages = {25-41},
}

@inproceedings{ feldman88optimal,
	author = {Paul Feldman and Silvio Micali},
	title = {\href{https://dl.acm.org/citation.cfm?id=62225}{Optimal Algorithms for Byzantine Agreement}},
	booktitle = {\bibconf[20th]{STOC}{Symposium on Theory of Computing}},
	month = may,
	year = 1988,
	pages = {148-161},
	location = {Chicago, Illinois, USA},
}

@phdthesis{ feldman88thesis,
	author = {Paul Feldman},
	title = {\href{https://dspace.mit.edu/bitstream/handle/1721.1/14368/20051076-MIT.pdf}{Optimal Algorithms for Byzantine Agreement}},
	school = {Massachusetts Institute of Technology},
	month = may,
	year = 1988,
}

@article{ fischer85impossibility,
  title={\href{https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf}{Impossibility of distributed consensus with one faulty process}},
  author={Fischer, Michael J and Lynch, Nancy A and Paterson, Michael S},
  journal={Journal of the ACM (JACM)},
  volume={32},
  number={2},
  pages={374--382},
  year={1985},
  publisher={ACM}
}

@article{ friedman05simple,
	author = {Roy Friedman and Achour Mostefaoui and Michel Raynal},
	title = {Simple and Efficient Oracle-Based Consensus Protocols
			for Asynchronous {Byzantine} Systems},
	journal = {IEEE Transactions on Dependable and Secure Computing},
	volume = 2,
	number = 1,
	month = jan,
	year = 2005,
}


%J

@book{ johnson77urn,
	author = {Norman Lloyd Johnson},
	title = {Urn models and their application: An approach to modern discrete probability theory},
	publisher = {Wiley},
	year = 1977,
	isbn = {978-0471446309},
}

%K

%L

@book{ lynch96distributed,
	author = {Nancy A. Lynch},
	title = {Distributed Algorithms},
	publisher = {Morgan Kaufmann},
	month = mar,
	year = 1996,
	isbn = {978-1558603486},
}


%M

@book{ mahmoud08polya,
	author = {Hosam Mahmoud},
	title = {P\'olya Urn Models},
	publisher = {Chapman and Hall/CRC},
	month = jun,
	year = 2008,
	isbn = {978-1420059830},
}

@inproceedings{merkle88digital,
  title={\href{https://people.eecs.berkeley.edu/~raluca/cs261-f15/readings/merkle.pdf}{A Digital Signature Based on a Conventional Encryption Function}},
  author={Merkle, Ralph C},
  booktitle={\bibconf{CRYPTO}{Advances in Cryptology}},
  year={1988},
}

@article{ moran58random,
	author = {{P. A. P.} Moran},
	title = {Random Processes in Genetics},
	journal = {\href{https://doi.org/10.1017/S0305004100033193}{Mathematical Proceedings of the Cambridge Philosophical Society}},
	volume = 54,
	number = 1,
	month = jan,
	year = 1958,
	pages = {60-71},
}

@inproceedings{ mostefaoui14signature,
	author = {Achour Most\'efaoui and Hamouma Moumen and Michel Raynal},
	title = {\href{https://dl.acm.org/citation.cfm?id=2611468}{Signature-Free Asynchronous Byzantine Consensus with $t < n/3$ and $O(n^2)$ Messages}},
	booktitle = {\bibconf{PODC}{Principles of Distributed Computing}},
	month = jul,
	year = 2014,
	location = {Paris, France},
}

@inproceedings{munro92detskiplists,
 author = {Munro, J. Ian and Papadakis, Thomas and Sedgewick, Robert},
 title = {\href{http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf}{Deterministic Skip Lists}},
 booktitle = {Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '92},
 year = {1992},
 isbn = {0-89791-466-X},
 location = {Orlando, Florida, USA},
 pages = {367--375},
 numpages = {9},
 url = {http://dl.acm.org/citation.cfm?id=139404.139478},
 acmid = {139478},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 


%N

@book{ nowak06evolutionary,
	author = {Martin A. Nowak},
	title = {Evolutionary Dynamics: Exploring the Equations of Life},
	publisher = {Belknap Press},
	month = sep,
	year = 2006,
	isbn = {978-0674023383},
}


%P

@article{pease80reaching,
	author={Pease, Marshall and Shostak, Robert and Lamport, Leslie},
	title={\href{http://dl.acm.org/citation.cfm?id=322188}{Reaching Agreement in the Presence of Faults}},
	journal={Journal of the ACM (JACM)},
	volume={27},
	number={2},
	pages={228--234},
	month=apr,
	year={1980},
	publisher={ACM}
}

@misc{ propp15polyas,
	author = {James Propp},
	title = {\href{https://mathenchant.wordpress.com/2015/10/16/polyas-urn/}{P\'olya's Urn}},
	month = oct,
	year = 2015,
}

@article{pugh90skiplists,
 author = {Pugh, William},
 title = 
 {\href{http://courses.cs.vt.edu/cs2604/fall05/wmcquain/Notes/Supplemental/PughSkiplistPaper.pdf}{Skip
  Lists: A Probabilistic Alternative to Balanced Trees}},
 journal = {Communications of the ACM},
 issue_date = {June 1990},
 volume = {33},
 number = {6},
 month = jun,
 year = {1990},
 issn = {0001-0782},
 pages = {668--676},
 numpages = {9},
 url = {http://doi.acm.org/10.1145/78973.78977},
 doi = {10.1145/78973.78977},
 acmid = {78977},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {data structures, searching, trees},
} 


%R

@inproceedings{ rabin83randomized,
	author = {Michael O. Rabin},
	title = {Randomized {Byzantine} Generals},
	booktitle = {Symposium on Foundations of Computer Science (SFCS)},
	month = nov,
	year = 1983,
}

@book{rapoport65prisoner,
  title={Prisoner's dilemma: A study in conflict and cooperation},
  author={Rapoport, Anatol and Chammah, Albert M and Orwant, Carol J},
  volume={165},
  year={1965},
  publisher={University of Michigan press}
}

%S

@article{skala13hypergeometric,
  author    = {Matthew Skala},
  title     = {{Hypergeometric Tail Inequalities: Ending the Insanity}},
  journal   = {CoRR},
  volume    = {abs/1311.5939},
  year      = {2013},
  url       = {https://arxiv.org/abs/1311.5939},
}

@inproceedings{ stadler96publicly,
  title={\href{https://link.springer.com/content/pdf/10.1007/3-540-68339-9_17.pdf}{Publicly Verifiable Secret Sharing}},
  author={Stadler, Markus},
  booktitle = {Eurocrypt},
  month=may,
  year={1996},
}

@inproceedings{
CJI09,  author = "R.~Chang and G.~Jiang and F.~Ivan{\v{c}}i{\'{c}} and
	 S.~Sankaranarayanan and V.~Shmatikov",
title = "Inputs of Coma:
	 Static Detection of Denial-of-Serice Vulnerabilities",
year = {2009},
booktitle ={CSF}}

@article(
CMS05, author="R.~Chadha and J.C.~Mitchell and A.~Scedrov and V.~Shmatikov",
title="Contract signing, optimism, and advantage",
journal="J. Logic and Algebraic Programming",
pages="189--218",
volume="64", number="2",
Year="2003")

@inproceedings(
DS,   Author="A.~Serjantov and G.~Danezis",
Title="Towards an information theoretic metric for anonymity",
Booktitle="Proc.\ 2nd International Workshop on
	Privacy-Enhancing Technologies",
Series={LNCS},
Volume={2482},
Pages="41--53",
Year="2002")

@inproceedings(
MS05,   author="A.~Mahimkar and V.~Shmatikov",
title="Game-based analysis of denial-of-service prevention protocols",
booktitle="Proc.\ 18th {IEEE} Computer Security Foundations
	  Workshop ({CSFW})",
publisher="{IEEE}",
year="2005",
pages="287--301")

@article(
NS06,   Author="G.~Norman and V.~Shmatikov",
Title="Analysis of probabilistic contract signing",
Journal="J. Computer Security",
Year="2006",
Pages="561--589",
Volume="14",
Number="6")

@inproceedings(
nymble, author="P.~Johnson and A.~Kapadia and P.~Tsang and S.~Smith",
title="Nymble: anonymous {IP}-address blocking",
booktitle="Proc.\ {PET}",
year="2007")

@article(
S04,    Author="V.~Shmatikov",
Title="Probabilistic model checking of an anonymity system",
Journal="J. Computer Security",
Year="2004",
Pages="355--377",
Volume="12",
Number="3-4")

@article(
SM02,   author="V.~Shmatikov and J.C.~Mitchell",
title="Finite-state analysis of two contract signing protocols",
journal="Theoretical Computer Science",
volume=283, number="2",
pages="419-450",
year=2002)

@inproceedings(
SW-esorics06, author="V.~Shmatikov and M-H.~Wang",
Title="Timing analysis in low-latency mix networks:
      attacks and defenses",
Booktitle="Proc.\ {ESORICS}",
Year="2006")

@inproceedings(
SW-fmse06, author="V.~Shmatikov and M-H.~Wang",
Title="Measuring relationship anonymity in mix networks",
Booktitle="Proc.\ {WPES}",
Year="2006")

@inproceedings(
torsk-attack, author="Q.~Wang and P.~Mittal and N.~Borisov",
title="In Search of an Anonymous and Secure Lookup:
       Attacks on Peer-to-peer Anonymous Communication Systems",
booktitle="Proc.\ {CCS}",
year="2010")

@inproceedings( tsang-ccs07,
	author="P.~Tsang and M.H.~Au and A.~Kapadia and S.~Smith",
	title="Blacklistable anonymous credentials:
	      blocking misbehaving users without {TTPs}",
	booktitle="Proc.\ {CCS}",
	year="2007"
)

@inproceedings(
tsang-ccs08, author="P.~Tsang and M.H.~Au and A.~Kapadia and S.~Smith",
title="{PEREA}: Towards Practical {TTP}-Free Revocation in
      Anonymous Authentication",
booktitle="Proc.\ {CCS}",
year="2008")


@article{ afk,
	author = {Mart\'in Abadi and Joan Feigenbaum and Joe Kilian},
	title = {On Hiding Information from an Oracle},
	journal = {Journal of Computer and System Sciences},
	volume = 39,
	year = 1989,
	pages = {21-50},
	note = {Special issue of selected papers from the 1987
		IEEE Conference on Structure in Complexity Theory}
},

@inproceedings{ bfl,
	author = {Matt Blaze and Joan Feigenbaum and Jack Lacy},
	title = {Decentralized Trust Management},
	booktitle = {Proceedings of the 17th Symposium on Security and Privacy},
	year = 1996,
	pages = {164-173},
}

@inproceedings{ bfs,
	author = {Matt Blaze and Joan Feigenbaum and Martin Strauss},
	title = {Compliance Checking in the {PolicyMaker}
			Trust Management System},
	booktitle = {Proceedings of the 2nd Financial Crypto Conference},
	year = 1998,
}

@article{ ff,
	author = {Joan Feigenbaum and Lance Fortnow},
	title = {Random-Self-Reducibility of Complete Sets},
	journal = {SIAM Journal on Computing},
	volume = 22,
	year = 1993,
	pages = {994-1005},
	note = {Extended abstract appears in Proceedings of the
		1991 IEEE Conference on Structure in Complexity Theory},
}

@article{ fksv,
	author = {Joan Feigenbaum and Sampath Kannan and Martin Strauss
		and Mahesh Viswanathan},
	title = {An Approximate {L1}-Difference Algorithm for
		Massive Data Streams},
	journal = {SIAM Journal on Computing},
	volume = 32,
	year = 2002,
	pages = {131--151},
	note = {Extended abstract appears in Proceedings of the
		1999 IEEE Symposium on Foundations of Computer Science},
}

@article{ fkmsz,
	author = {Joan Feigenbaum and Sampath Kannan and Andrew McGregor
			and Siddharth Suri and Jian  Zhang},
	title = {On Graph Problems in a Semi-Streaming Model},
	journal = {Theoretical Computer Science},
	volume = 348,
	year = 2005,
	pages = {207--216},
	note = {Special issue of selected papers from the 2004 International
		Colloquium on Automata, Languages, and Programming},
}

@article{ fps,
	author = {Joan Feigenbaum and Christos Papadimitriou and Scott Shenker},
	title = {Sharing the Cost of Multicast Transmissions},
	journal = {Journal of Computer and System Sciences},
	volume = 63,
	year = 2001, 
	pages = {21--41},
	note = {Preliminary version appears in Proceedings of the 2000
		ACM Symposium on Theory of Computing},
}

@article{ fpss,
	author = { Joan Feigenbaum and Christos Papadimitriou and Rahul Sami
			and Scott Shenker},
	title = {A {BGP}-based Mechanism for Lowest-Cost Routing},
	journal = {Distributed Computing},
	volume = 18,
	year = 2005,
	pages = {61--72},
	note = {Special issue of selected papers from the 2002 ACM Symposium
		on Principles of Distributed Computing},
}

@inproceedings{shoup00practical,
  title={\href{https://link.springer.com/content/pdf/10.1007/3-540-45539-6_15.pdf}{Practical Threshold Signatures}},
  author={Shoup, Victor},
  booktitle={Eurocrypt},
  month = may,
  year={2000},
}


@book{stinson05crypto,
  author = {Douglas R. Stinson},
  title = {Cryptography: Theory and Practice},
  year = {2005},
}

@inproceedings{guerraoui10next,
  title={\href{http://www.vukolic.com/700-Eurosys.pdf}{The next 700 {BFT} protocols}},
  author={Guerraoui, Rachid and Kne{\v{z}}evi{\'c}, Nikola and Qu{\'e}ma, Vivien and Vukoli{\'c}, Marko},
  booktitle={5th European conference on Computer systems},
  pages={363--376},
  year={2010},
  organization={ACM},
  url={http://www.vukolic.com/700-Eurosys.pdf},
}


%V

@book{ vanderbei13linear,
	author = {Robert J. Vanderbei},
	title = {Linear Programming: Foundations and Extensions},
	publisher = {Springer},
	month = jul,
	year = 2013,
	isbn = {978-1461476290},
}