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 / 29Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!