NDLI: Knowledge, probability, and adversaries

Content Provider	ACM Digital Library
Author	Halpern, Joseph Y. Tuttle, Mark R.
Copyright Year	1993
Abstract	What should it mean for an agent to know or believe an assertion is true with probability 9.99? Different papers [2, 6, 15] give different answers, choosing to use quite different probability spaces when computing the probability that an agent assigns to an event. We show that each choice can be understood in terms of a betting game. This betting game itself can be understood in terms of three types of adversaries influencing three different aspects of the game. The first selects the outcome of all nondeterministic choices in the system; the second represents the knowledge of the agent's opponent in the betting game (this is the key place the papers mentioned above differ); and the third is needed in asynchronous systems to choose the time the bet is placed. We illustrate the need for considering all three types of adversaries with a number of examples. Given a class of adversaries, we show how to assign probability spaces to agents in a way most appropriate for that class, where “most appropriate” is made precise in terms of this betting game. We conclude by showing how different assignments of probability spaces (corresponding to different opponents) yield different levels of guarantees in probabilistic coordinated attack.
Starting Page	917
Ending Page	960
Page Count	44
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/153724.153770
Journal	Journal of the ACM (JACM)
Volume Number	40
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1993-09-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Byzantine generals problem Coordinated attack problem Game theory Knowledge Probabilistic knowledge Probability
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Weak Byzantine Generals Problem

An $\textit{O}(log$ $\textit{n})$ expected rounds randomized byzantine generals protocol

Reasoning about knowledge and probability

Optimal probabilistic fingerprint codes

Space-bounded probabilistic game automata

Corrigendum: “Reasoning about knowledge and probability”

Early stopping in Byzantine agreement

Bounds on information exchange for Byzantine agreement

The Halting Problem for Probabilistic Context-Free Generators

Knowledge, probability, and adversaries

Similar Documents

The Weak Byzantine Generals Problem

An $\textit{O}(log$ $\textit{n})$ expected rounds randomized byzantine generals protocol

Reasoning about knowledge and probability

Optimal probabilistic fingerprint codes

Space-bounded probabilistic game automata

Corrigendum: “Reasoning about knowledge and probability”

Early stopping in Byzantine agreement

Bounds on information exchange for Byzantine agreement

The Halting Problem for Probabilistic Context-Free Generators

Knowledge, probability, and adversaries