Chapter 8 - Reasoning with Knowledge Notes | EduRev

: Chapter 8 - Reasoning with Knowledge Notes | EduRev

 Page 1


Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Page 2


Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Page 3


Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Page 4


Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Page 5


Chapter 8: Reasoning with Knowledge
Ajay Kshemkalyani and Mukesh Singhal
Distributed Computing: Principles, Algorithms, and Systems
Cambridge University Press
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 1 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Distributed Computing: Principles, Algorithms, and Systems
Muddy Children Puzzle (Scenario A)
n children, all intelligent, can see others but not their own faces
k ( n) have mud on their forehead
Scenario A: Father says:: : "At least one of you has
mud on the forehead."
Father then repeatedly asks (i.e., broadcasts) in
rounds (to model synchronous operation) to the
assembled children:
I
Do you have mud on your
forehead?
How does each child respond in each round,
r = 1; 2;::: k 1; k; k + 1;::: n; n + 1;:::?
An answer is "broadcast" in that round.
Let c = clean child, d= dirty child
k = 0: contradicts 
k = 1: In r = 1, the d answers "Yes".
For r = 2, the c answer "No".
k = 2: In r = 1, no responses.
In r = 2, both d answer "Yes".
In r = 3, the c answer "No"
k = 3: In r = 1; 2, no responses.
In r = 3, the 3 d answer "Yes".
In r = 4, the n 3 c answer "No".
k n: In r < k, no responses.
In r = k, the k d answer "Yes".
In r = k + 1, the n k c answer "No".
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 2 / 29
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!