Stats for nerds
2recommend
2mentions
2people
2015–2023years
100% recommend
Mentions per year
What Hacker News says
- If you're interested in consensus algorithms, you might be interested in this book that I used in a theoretical course on distributed system called "Reasoning about Knowledge" (https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...).
You have to invest a bit in learning about modal logic, but once you do get past that part, this book provides proofs of why things like Raft or Paxos work that are super intuitive and straightforward. Basically pushing the complexity of proving these algorithms into the logic structure used to form the proof (in an intuitive way). Highly recommend, changed how I think about consensus!
- Epistemic logic would probably be the appropriate tool; at least that's what I thought when I first saw the problem. Epistemic logic is the logic of knowledge and belief: you use a modal operator to express the knowledge of an agent about a certain statement. The statement could be expressed in propositional or first-order logic depending on the expressiveness required (but of course there is a complexity trade-off).
Translating roughly from the problem statement (x being the variable holding Cheryl's birthday):
Not(Know_Albert(x)) and Know_Albert(Not(Know_Bernard(x) etc.
Semantically, the possible birthdays correspond to the possible worlds. A reasoner would be able to solve this by process of elimination, somewhat similarly to a constraint-solver.
Resources:
Wikipedia entry on Epistemic Logic: http://en.wikipedia.org/wiki/Epistemic_modal_logic
Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe (2003). Reasoning about Knowledge: http://www.amazon.com/Reasoning-About-Knowledge-Ronald-Fagin...
I haven't read the entire book, but the first couple of chapters give you an idea and some great examples not too different from this puzzle.
