Computacin Distribuida, 2015-2

Tarea 1

Soto Romero Manuel

16 de febrero de 2015

1. El cuarto con un con un foco. En esta situacin, cada uno de los presos est en una celda,

la que no comparte con nadie ms. En la prisin tambin hay un cuarto que tiene un foco y un

apagador que enciende y apaga ese foco. El guardia les dice a los presos lo siguiente: a partir

de maana, cada da, alguno de ustedes pasar el da completo en ese cuarto, los dems presos

no sabrn la identidad del preso que est all; estando en el cuarto, pueden apagar y prender el

foco cuantas veces quieran y dejarlo encendido o apagado, les prometo que yo jams tocar ese

apagador. Tambin les prometo que si repetimos esto hasta el n de los tiempos (suponiendo que

los presos y el guardia son inmortales), cada uno de ustedes estar en el cuarto una innidad de

das. Para ser liberados, alguno de ustedes deber gritar, ya sea desde su celda o desde el cuarto,

'todos ya hemos estado en el cuarto'; si es cierto que cada uno de ustedes ya ha estado en el cuarto

al menos una vez, entonces los liberar, de otra forma todos sern sacricados. Les doy la tarde

de hoy para que hablen entre ustedes y creen su estrategia, y a partir de maana no se volvern a

ver.

El objetivo es mostrar una estrategia en la que los presos son eventualmente liberados. Puedes

asumir que el foco en el cuarto est inicialmente apagado.

Solucin:

Se debe elegir a uno de los presos como el encargado para contarlos a todos. Cuando uno de los

presos entra por primera vez debe prender el foco. A partir de ese momento si entra un preso dis-

tinto del encargado no debe hacer nada con el foco. Cuando entre el encargado, si encuentra el foco

encendido contar al preso que encendi el foco y lo apagar, de manera que el preso que encen-

di el foco no deber mover el interruptor de nuevo. De esta manera ir contando a todos los presos.

Modelo mediante un Sistema Distribuido:

Nodos de la grca: El preso encargado de contar a todos (r), los presos restantes (p1, p2,

... pn) y el cuarto con el foco (f). El nodo raz tendr un atributo llamado contador que ir

sumando el nmero de presos y un total. Los dems nodos tendrn un atributo masDeUna

que ser true s han entrado ms de una vez. El cuarto tendr un atributo llamado encendido

que tendr los valores true o false.

Aristas de la grca: Todos los presos estarn conectados con el cuarto formando una estrella.

1

Tarea 1 Soto Romero Manuel

Ejemplo con 6 nodos:

Algoritmos de solucin:

Iniciar atributos

1 I n i c i a r a t r i bu t o s de r :

2 contador = 1 ; // se cuenta a s mismo

3 TOTAL = n ;

1 I n i c i a r a t r i bu t o s de f :

2 encendido = fa l se ;

1 I n i c i a r a t r i bu t o s de l o s p re so s d i s t i n t o s de r :

2 masDeUna = fa l se ;

Pseudocdigo nicamente para la raz

1 When r e c e i v e encendido from f : // cdigo para e l nodo r

2 i f ( encendido = true )

3 contador += 1 ;

4 send to f ;

5 i f ( contador = TOTAL)

6 say ("Ya entramos todos " ) ;

7 terminate ;

Pseudocdigo nicamente para los prisioneros distintos de r

1 When r e c e i v e encendido from f : // cdigo para l o s nodos pj

2 i f ( ( encendido = fa l se ) and (masDeUna = fa l se ) )

3 send to f ;

4 masDeUna = true ;

Pseudocdigo nicamente para el cuarto con el foco

1 When r e c e i v e from pj : // cdigo para e l nodo f

2 send encendido to pj ;

2

Tarea 1 Soto Romero Manuel

1 When r e c e i v e from pj : // cdigo para e l nodo f

2 encendido = true ;

1 When r e c e i v e from pj : // cdigo para e l nodo f

2 encendido = fa l se ;

2. En la y con sombreros de colores. En este caso, el guardia dice lo siguiente a los presos: el

da de maana, al medio da, los voy a colocar en la, todos viendo hacia el norte, de modo tal que

el primero no podr ver a nadie, el segundo podr ver al primero, y as sucesivamente hasta que

el ltimo en la la ver a todos. No tendrn permitido ver a ninguna otra parte mas que al frente.

Pondr en la cabeza de cada uno de ustedes un sombrero de color rojo o azul, el color lo elegir al

azar. Como ya les dije, slo podrn ver al frente, as es que no tendrn permitido ver el color de su

sombrero. Empezando desde el ltimo de la la, el que ver a todos. Preguntar a cada uno y en

orden, el color de su sombrero; si la respuesta es correcta, ese preso ser liberado, de otra forma

ser ejecutado. Por su puesto, cada preso podr escuchar las respuestas de los dems. Tienen la

tarde de hoy para organizarse.

El objetivo es mostrar una estrategia en la que por lo menos n 1 presos sean liberados.

Solucin:

Claramente el preso que se tendr que sacricar (o por suerte salvar) es el que puede ver a todos

los dems. El preso podr contar cuantos sombreros pares de un color X hay y a partir de eso dir

el color X si es par o Y si es par. De esta manera el preso que est delante de l slo debe hacer

cuentas. Por ejemplo, si ve 6 sombreros rojos, puede decir rojo, pero si ve 5 rojos puede decir azul.

Modelo mediante un Sistema Distribuido:

Nodos de la grca: El preso que est al nal de la la (r) y los prisioneros (p1, p2, ... pn).

Cada nodo tendr tres atributos: azules, rojos y TODOS. Los primeros guardarn el nmero

de sombreros azules y rojos que ve el prisionero. El tercero el total de prisioneros.

Aristas de la grca: Estarn conectados como si fueran una lista, donde la cabeza de sta

ser el preso r.

Ejemplo para 5 nodos:

Algoritmos de solucin:

Iniciar atributos

3

Tarea 1 Soto Romero Manuel

1 I n i c i a r a t r i bu t o s de todos l o s nodos :

2 r o j o s = #de r o j o s que ve

3 azu l e s = #de azu l e s que ve

4 TODOS = n ;

Pseudocdigo nicamente para r

1 Only r :

2 i f ( r o j o s par ) then // ve un nmero par de r o j o s

3 say (" r o j o " ) ;

4 send to p1 ;

5 else // ve un nmero impar de r o j o s

6 say (" azu l ")

7 send to p1 ;

Pseudocdigo nicamente para los pj's.

1 When r e c e i v e from pj

2 i f ( ( r o j o s + x) impar ) // es r o j o

3 say (" r o j o " ) ;

4 i f (TODOS = j+1)

5 terminate ;

6 else

7 send

8 else // es azu l

9 say (" azu l " ) ;

10 i f (TODOS = j+1)

11 terminate ;

12 else

13 send

1 When r e c e i v e from pj

2 i f ( ( r o j o s + x) par ) // es r o j o

3 say (" r o j o " ) ;

4 i f (TODOS = j+1)

5 terminate ;

6 else

7 send

8 else // es azu l

9 say (" azu l " ) ;

10 i f (TODOS = j+1)

11 terminate ;

12 else

13 send

Observacin. Las etiquetas que dicen cosas del tipo send no quieren decir como

tal que estn mandando el mensaje par sino que como el nodo r dijo rojo, el siguiente nodo

interpreta eso como par. (Lo mismo para impar).

4

Tarea 1 Soto Romero Manuel

3. De nuevo los sombreros. En este caso, el guardia simplemente saca a todos los presos al

patio, los coloca en un crculo y le pone a cada uno un sombrero de color rojo o azul (de nuevo

el color es elegido al azar). Cada preso puede ver el color del sombrero de los dems, pero no el

suyo. Esta vez el guardia no deja que los presos hablen entre s para acordar una estrategia. El

guardia les dice: en este momento voy a elegir un color X, rojo o azul, y cada 10 minutos repetir

la siguiente frase por lo menos uno de ustedes tiene en su cabeza un sombrero de color X'. Les

aseguro que si les digo eso es porque es cierto, al meno uno de ustedes tiene un sombrero de color

X. Si los que tienen el sombrero del mismo color quieren ser liberados, todos ellos debern ponerse

de pie y decir en voz alta el color de su sombrero, justo despus de que yo diga mi frase, en alguna

de las muchas veces que estar repitindola; pero tienen que hacerlo todos y al mismo tiempo, de

no ser as, sern sacricados.

Suponiendo que los presos son inteligentes, honestos y quieren ser liberados, cmo deberan actuar

para no ser ejecutados?

Solucin:

La solucin a este problema se da utilizando razonamiento inductivo. El caso base sera cuando

tenemos un prisionero rojo y un prisionero azul. Supongamos que el guardia dice que hay al menos

uno rojo. El prisionero azul no se levanta porque sabe que hay otro rojo, pero no sabe su propio

color por lo que no se puede levantar. Haciendo el mismo razonamiento, el rojo sabe que el azul

sabe que l es rojo pues de lo contrario se hubiera levantado. Por lo tanto el rojo se levanta.

A partir de aqu podemos generalizar el problema. Por ejemplo, si tuviramos 2 prisioneros

rojos y k prisioneros azules. El guardia dira que hay al menos uno rojo. Todos los prisioneros

azules no se levantan pues saben que hay 2 rojos y no saben su color. Los prisioneros rojos saben

que hay k azules y uno rojo. Ambos al mismo tiempo piensan que si ellos fueran el nico rojo

se habra levantado el otro, pero estn viendo a otro rojo, entonces la nica manera de que no se

hayan levantado es que ellos mismos sean rojos, por lo tanto se levantan.

Un ltimo ejemplo, donde se ve ms claro el razonamiento inductivo es cuando se tienen 3

rojos y k azules. El guardia dira que hay al menos uno rojo. Todos los azules no se levantan pues

saben que hay 3 rojos y no saben su color. Los prisioneros rojos saben que hay k azules y dos

rojos. Todos al mismo tiempo piensan que no pueden ser dos rojos pues habran hecho el razo-

namiento del paso anterior. De manera que todos estn viendo a dos rojos, por lo tanto se levantan.

Modelo mediante un Sistema Distribuido:

Nodos de la grca: El guardia que les dice que hay al menos un prisionero de color X (g)

y los prisioneros (p1, p2, ... pn). Cada nodo prisionero tendr dos atributos: azules y rojos.

stos guardarn el nmero de sombreros azules y rojos que ve el prisionero.

Aristas de la grca: Todos los prisioneros estarn conectados con el guardia en forma de

estrella.

Ejemplo con 6 nodos:

5

Tarea 1 Soto Romero Manuel

Algoritmos de solucin:

Iniciar atributos

1 I n i c i a r a t r i bu t o s de todos l o s p r i s i o n e r o s :

2 r o j o s = #ro j o s que ve cada uno

3 azu l e s = #azu l e s que ve cada uno

4 rondas = 0

Pseudocdigo nicamente para g

1 Only g :

2 c o l o r = choose (Rojo , Azul ) ;

3 i f ( c o l o r = ro j o )

4 send ro j o to a l l ne ighbours ;

5 else

6 send azu l to a l l ne ighbours ;

Pseudocdigo nicamente para los pj's... No me sale :(

1 When r e c e i v e from g :

2 i f ( r o j o s = rondas ) // es e l nico

3 say ("Rojo " ) ;

4 terminate ;

5 else

6 rondas++;

1 When r e c e i v e from g :

2 i f ( a zu l e s = rondas ) // es e l nico

3 say ("Azul " ) ;

4 terminate ;

5 else

6 rondas++;

Observacin. Hay que hacer notar que el sistema debe ser sncrono para que todos los prisioneros

rojos o azules se levanten al mismo tiempo.

6