Problemas y Paradojas Clásicas de Search Filosofía

Epistemología Interactiva y Search

En el siglo XX algunas sorprendentes reflexiones search filosóficas son publicadas bajo el nombre de Paradojas Generales, siendo encuadradas dentro de lo que de forma general se ha llamado Epistemología Interactiva.

Los problemas planteados en esta disciplina son herederos del modo de razonar Griego. Y fueron reflexionadas por Matemáticos, Lógicos y Analistas de Europa, EE.UU o el Caribe, de forma libre e independiente, con quien mantuve correspondencia, en busca de cierta luz. Intentan dar respuesta a los problemas clásicos pensandos por los Filosofos Griegos, de forma nueva, en intima relacion con la Teoria de Link e Internet o el problema de la Clasificación de todas las Clasificaciones.

Las reflexiones aquí traducidas constituyen uno de los ejemplos mas bellos de la capacidad del Humano por querer solucionar problemas que son infinitos. Y por superar problemas que aun siendo aparentemente inutiles son la esencia de Internet y su naturaleza.

Presentamos aquí algunos de los denominados Problemas Clásicos de la Search Filosofía, como el Problema de la Coordinacion, que reflexiona el canal bidireccional. Y da luz a su importancia epistemológica.

Y de otros problemas que pensamos son de especial interes como el de La Paradoja del Link.

El Problema de la Coordinación en un canal bidireccional

El canal bidireccional permite al Server invocar Servicios del Browser y publicar Eventos en el Browser. * Para comprender que el protocolo commit de dos fases da solución a ciertos problemas es conveniente y util analizar la Paradoja de los Generales, que sigue a continuación.

La Paradoja de los Generales

Hay 2 Generales en una Campaña Militar. Ambos disponen de un Objetivo (la colina) que quieren capturar. Si ambos Generales y de forma simultanea marchan hacia el Objetivo pueden asegurar el éxito de su empresa. Si marcha unicamente uno de ellos, este será aniquilado.

Los Generales están acampados y están unicamente separados por una pequeña distancia, pero a causa de dificultades técnicas unicamente pueden comunicarse a través de Corredores. Estos mensajeros tienen una imperfección. Cada vez que intentan aventurarse fuera del Campo militar tiene la oportunidad de perderse (no son muy listos). El problema es encontrar algun protocolo que permita a los Generales marchan juntos incluso cuando sus mensajeros se han perdido. Hay un sencilla prueba que indica: no existe protocolo de distancia fija: Sea P, el mas corto de los Protocolos. Si suponemos que el ultimo mensajero en P se ha perdido. Entonces o este mensajero es inutil o uno de los Generales no ha conseguido el mensaje que necesita. Por el minimality de P, el ultimo mensaje no es inutil por lo que el General no marcha si el mensajero se ha perdido. Esta contradiccion prueba que no existe el protocolo P. La Paradoja de los Generales (que como puede observar no es una Paradoja) tiene una fuerte analogia con los problemas con los que se enfrenta la Gestion de Recuperacion de Datos (data recovery management). Imagine que uno de los Generales es un ordenador en Tokio y que el otro General es un terminal dispensador de dinero en Fuessen, Alemania, un cajero. El objetivo es el que sigue:

• abrir el cajero que contiene un millon de marcos y
• cargar la cuenta en concreto en el almacen no volatil del ordenador de Tokio

Si unicamente una cosa sucede, ni los Alemanes ni los Japoneses podrán destuir al General que no ha marchado.

Puede encontrarse el texto en:

• James Gray "Notes on Data Base Operating Systems" In Lecture Notes In Computer Science; Vol. 60 "Operating Systems, An Advanced Course" pp 393 - 481 1978 Springer-Verlag London, UK ISBN:3-540-08755-9

Version original:

The Generals Paradox

In order to understand that the two-phase commit protocol solves some problem it is useful to analyze this generals paradox. There are two generals on campaign. They have an objective (a hill) that they want to capture. If they simultaneously march on the objective they are assured of success. If only one marches, he will be annihilated. The generals are encamped only a short distance apart, but due to technical difficulties, they can communicate only via runners. These messengers have a flaw, every time they venture out of camp they stand some chance of getting lost (they are not very smart.) The problem is to find some protocol that allows the generals to march together even though some messengers get lost. There is a simple proof that: no fixed length protocol exists: Let P be the shortest such protocol. Suppose the last messenger in P gets lost. Then either this messenger is useless or one of the generals doesn't get a needed message. By the minimality of P, the last message is not useless so one of the general doesn't march if the last message is lost. This contradiction proves that no such protocol P exists. The generals paradox (which as you now see is not a paradox) has strong analogies to problems faced by a data recovery management when doing commit processing. Imagine that one of the generals is a computer in Tokyo and that the other general is a cash-dispensing terminal in Fuessen Germany. The goal is to * open a cash drawer with a million marks in it (at Fuessen) and * debit the appropriate account in the non-volatile storage of the Tokyo computer. If only one thing happens, either the Germans or the Japanese will destroy the general that did not ”march".

Sobre el término Commit, Wikipedia indica que:

En interconexión de computadores y Base de datos, el protocolo commit de dos fases es un algoritmo distribuido que permite a todos los nodos de un sistema distribuido ponerse de acuerdo para hacer commit a una transacción. El resultado del protocolo en que todos los nodos realizan commit de la transacción o abortan, incluso en el caso de fallos en la red o fallos en nodos. Sin embargo, de acuerdo con el trabajo de Dale Skeen y Michael Stonebraker, el protocolo no manejará más que el fallo de un sitio aleatorio a la vez. Las dos fases del algoritmo son la fase de petición de commit, en el cual el coordinador intenta preparar a todos los demás, y la fase commit, en la cual el coordinador completa las transacciones a todos los demás participantes.

The coordinated GO problem

2 Divisiones Militares estan acampadas en 2 colinas sobre un valle comun. En el valle aguardan al enemigo.

Se asume como cierto que si ambas divisiones atacan al enemigo de forma simultanea, ganaran la batalla; mientras que si una sola division ataca, ésta sera derrotada.

Las divisiones no tienen inicialmente planes para iniciar un ataque contra el enemigo, y el comandante general de la primera division desea coordinar un ataque simultaneo (en algun momento del dia siguiente).

Ningun general atacara a menos que este seguro de que el otro le atacara a él. Y los Generales se pueden comunicar unicamente a traves de un mensajero.

Normalmente al mensajero le lleva 1 hora ir de un campamento a otro. Sin embargo, es posible que se pierda en la oscuridad o peor aun que sea capturado por el enemigo. Afortunadamente en una noche concreta todo se vuelve más fácil.

¿Cuanto tiempo les llevaría coordinar un ataque? Los estandares indican que incluso si todo es facil y no hay problemas, no se podrá llegar nunca a un acuerdo y de este modo ningun general podrá nunca decidirse a atacar.

Tal y como Halpern y Moses indican este es uno de los teoremas virtuales clásicos de la teoria de sistemas operativos. Suponiendo que el General A mandase un mensaje al General B, diciendo "Ataquemos al crepusculo", esto sería suficiente para que B supiese que A quiere atacar al crepusculo.

Sin embarho, B sabe tambien que A no puede saber que él sabe esto porque el mensajero podría no haber llegado. Asi, él envia de vuelta su propio mensajero al enviar una respuesta a B. Podría advertirse que el ataque está ahora coodinado porque ambos a dos, A y B, saben que cada uno de ellos quiere atacar al crespusculo. Y ademas, cada uno de ellos sabe que ambos a dos conocen esta situacion.

El problema es que A no puede saber que su ultimo mensaje a B ha llegado (got through). Así, B debe enviar un soldado de reconocimiento (acknowledgement).

Pero, ¿como sabe B que este mensaje ha llegado?

A debe enviar otro soldado de reconocimiento ...

Este sencillo argumento de induccion muestra así como no hay un número de mensajes suficientes para coordinar el ataque.

The coordinated GO problem

Two divisions of an army are camped on two hilltops overlooking a common valley. In the valley awaits the enemy. It is clear that if both divisions attack the enemy simultaneously, they will win the battle; whereas if only one division attacks, it will be defeated. The divisions do not initially have plans for launching an attack on the enemy, and the commanding general of the first division wishes to coordinate a simultaneous attack (at some time the next day). Neither general will decide to attack unless he is sure that the other will attack with him. The generals can only communicate by means of a messenger. Normally, it takes the messenger one hour to get from one encampment to the other. However, it is possible that he will get lost in the dark or, worse yet, be captured by the enemy. Fortunately, on this particular night, everything goes smoothly. How long will it take them to coordinate an attack? The standard claim is that, even if everything does go smoothly, no agreement can ever be reached and thus neither general can ever decide to attack. As Halpern and Moses point out this is a virtual folk theorem of operating systems theory. Suppose that general A sends a message saying \Let's attack at dawn." to general B. This is enough for B to know that A wants to attack at dawn. But, B also knows that A can't know that he knows this because the messenger might not have arrived. So, he sends back his own messenger telling A of his receipt of the message and his agreement. To indicate that everything is confirmed A acknowledges receipt of this message by sending a response to B. It might seem that the attack is now coordinated because both A and B know that they each want to attack at dawn. And, each of them knows that they both know this. The problem is that A cannot know that his last message to B got through. So B must send an acknowledgement. But how does B know that this message arrived? A must send another acknowledgement . . . . An easy induction argument shows that no number of messages is suficient to coordinate the attack.

Algunas observaciones lógico filosóficas:

I thought this was a pretty well known result - though I admit I haven't worked on such issues in some time. I believe it is easy to understand what's going on with the gangster example. The situation is that the Boss and a lieutenant have agreed on a plan for a heist. They've split up the gang across town, some with the boss and some with the lieutenant. For the plan to come off it is essential that they "coordinate" their action. That is, if one group puts the plan into action without the other group, the plan will fail and group that started will all go to jail. The only communication is by messenger. Such communication by messenger is known to be somewhat unreliable (e.g. attacks by rival gangs). For this example you can assume that the messengers are trustworthy (unlike with the Byzantine Generals problem), but you have to deal with the possibility that the messengers may not be able to successfully deliver their message.

So..., the boss decides the plan is a "GO". Then:

1. He sends a messenger with the "GO" message to the lieutenant.

2. The lieutenant gets the "GO" message. At this point the lieutenant knows that the boss decided on "GO", but of course the boss doesn't know that the lieutenant got the message. The lieutenant can't safely proceed until he knows that the Boss knows he received the message.

3. The lieutenant sends a messenger back to the boss to let him know that he received the message (ack). The boss of course doesn't want to act unless he knows the lieutenant got the message, so he waits for the ack.

4. The Boss gets the acknowledgement. At this point the Boss knows that the lieutenant got the "GO" message. Unfortunately the lieutenant doesn't know whether the boss got the acknowledgement. The lieutenant can't safely start to carry out the plan unless he knows the Boss got the acknowledgement and will carry out his part of the heist, so the lieutenant must wait for an acknowledgement of his ack.

5. The boss can send an ack for the ack to assure the lieutenant but ...

No matter how many acks or what sort of communication, the last one to send a message doesn't know if it was received. That person is always in an ambiguous communication situation. The "coordination" can't be accomplished.

Any network communication has the same problem. For example, with TCP acknowledgements are sent. This means that the sender can know that the receiver got the packets (the message). However, the receiver can't know that the sender received the acknowledgements. Even with the way TCP handles retires it can be that it ultimately times out. Given that possibility (equivalent to a network partition), there is an inevitable ambiguity on one end or the other. This is unavoidable.

I find it interesting to consider the gangster example if they happen to have telephone communication available - or anything interactive (e.g. IM). There the situation is actually the same, but somehow it seems different.

The Boss says (on the telephone), "We're GO!". The lieutenant says back, "OK, got it. We're GO!". That would seem to do it. However, what happens if the telephone goes dead at that point? The lieutenant could say, "Did you hear me Boss? I got it, we're GO!". If he doesn't hear back from the Boss, what does he do?

Even without the telephone going dead the ambiguity is always present. The Boss can hear the acknowledgement and say, "Yeah, I heard you. We agree that we're GO. Do you hear me?", etc. In real human communication the conversation would terminate quickly with both the Boss and the lieutenant satisfied that they've coordinated the heist, but have they? Who spoke last? The one who spoke last doesn't know for sure that the heist is on. If the one who spoke last hangs up and his statement was lost due to a telephone failure at that last instant, what does the one who spoke second to last do? Call back? You're right back into the same situation.

No bogosity. This is a real and unsolvable problem. As I mentioned, the first time I saw this explained was in this paper by Akkoyunlu, Ekanadham, and Huber, "Some Constraints and Tradeoffs in the design of Network Communications", e.g.:

Sobre la Coordinación

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1000699

The first instance I can find of the coordination problem is (Gray, 1978), and was made more explicit by (Rubinstein, 1989) as The Email Game. Two generals are perched with their divisions atop tall hills, with the enemy in the valley between them. When the first general (G1) receives intelligence that the enemy will be unprepared at dawn, he sends a message to the second general (G2) indicating that they should attack at that time. Generals can only communicate via messenger, and there is some positive probability, 0 < a < 1, that the message will not be delivered (he may be lost or captured).

When G2 gets the message from G1 stating that the enemy will be unprepared at dawn and that they should coordinate an attack for that time, G2 sends the messenger back verifying that he received the message, and agreeing that the time is optimal. When he receives the reply, G1 sends the messenger back to notify G2 that he received the reply. But note first that no matter how many times the message is delivered back and forth, the time of attack will never be common knowledge between the two generals. Note also that as the number of times the messenger goes back and forth increases, eventually a = 1.

Nombre	Attack	Don´t Attack
Attack	Pokeball normal	Todas las versiones
Don´t Attack	Mejor que un Pokeball	Todas las versiones

The payoff matrix would be as in Table 1 in the case that the enemy is prepared, and as in Table 2 in the case they they are not prepared. Obviously, if both generals attack, they both get a payoff of 1. If the general does not attack his payoff is 0, regardless of whether the other attacks. If the attack goes badly (either because the enemy is prepared or the other general does not attack), the payo� is -M (where M is some large number). In either case, if there's no perfect coordination, then fDon't Attack, Don't Attackg is the only strategy at equilibrium.

De�ne a coordinated attack as an attack in which (1) the enemy is unprepared, (2) one division never attacks alone, and (3) both divisions sometimes successfully coordinate an attack using the communication protocol and the action protocol. De�ne a communication protocol as a protocol specifying the methods under which a general communicates with another general, and an action protocol as as a protocol which speci�es which general attacks, and under what conditions. We'll refer to the above as the `naive communication protocol.'

But as I have shown above, under these conditions, a coordinated attack is not possible given the naive communication protocol. In fact, a fortiori, for any communication protocol with unreliable information, a coordinated attack is never possible. For a discussion of this fact, see (Morris and Shin, 1997). One solution centers on the fact that player 1 (here, G1) always has the information advantage, viz. he always knows �rst, and then passes that information on. (Dimitri, 2003) argues that giving neither player the information advantage, i.e., introducing an intermediary, may provide a solution to the coordination problem as I've described it. One problem with this strategy may be that it does not take into consideration any new payo� structure of the game which would arise by allowing the \intermediary" to participate as a third player in the game. (Koessler, 2000) follows a similar line of thought: the coordination problem can be avoided by introducing either advertisement or a leader. Leadership may also be valuable to guarantee the Pareto e�cient solution when other, less e�cient, equilibria are available.

Morris and Shin's argument, however, centers on the fact that decision theory might provide us with a solution to the paradox. For a Bayesian, losses are acceptable in su�ciently small probabilities. In particular, let " represent the probability that the messenger will be lost, where a > 0. Let � represent the probability that the enemy is prepared, where (1 &#56256;- de - delta �) is the probability that the enemy is unprepaired. Assume also that " is smaller than �. Let (n,m) represent the event in which G1 has sent n messages, and G2 has sent m messages. The space state is represented in Table 3.

Call an action protocol optimal if it maximizes the generals' payo�s. If " is su�ciently small, the optimal action protocol for G1 is to attack whenever the enemy is ready, and for G2 to attack if he's received at least one message. This will result in a payo�ff of

(1 -delta �)a(- M)+(1 - delta �)(1 - a) = (1 - delta�)(1-(M+1)a). In this case, coordinated attack occurs with probability (1- delta �)(1 - a), and can be achieved in any state in Table 3 (with the exception of (0,0)). Obviously, then, for a Bayesian decision maker, this action protocol is acceptable, thus solving the paradox. This is to say that when " is su�ciently small, there exists a protocol that approaches the expected payo� of a perfect communication protocol (Morris and Shin, 1997, pp. 175-77).

What is not immediately clear is that this solution is applicable to the naive protocol, just in case the generals can be counted upon to follow the rules given them, i.e., the game is non-strategic, rather than a strategic one. Consider our optimal solution again. It works because G2 can always be counted on to attack if he has received (and therefore sent) a message. And this is true if generals can always be counted upon to follow the protocol set out beforehand. But now if this is a strategic game, in which players must decide what course of action to take based on the information available to them, about the situation, and about the rules of the game, it is not so clear that G2 will attack at all. We can imagine him on his hill having sent his reply after getting G1's �rst message. But with not even one reply indicating that G1 knows that G2 has received the message, G2 may be hesitant to commit his own troops to a battle that they are unlikely to win, if forced to fight alone.

Obviously, G1 is fully aware that G2 reasons this way, and so for the same reasons may hesitate to commit his own division under the same circumstances. Quickly the paradox unravels itself again. For any game of incomplete information, with an imperfect communication protocol, if the players act strategically, coordination is impossible, and neither general will ever attack.

El problema de los Gansters

Traduciendo...

Un grupo de gangsters esta maquinando un gran golpe. El plan de acción ha sido preparado hasta su ultimos detalles. Algunos hombres esta escondidos en un almacen de la ciudad, esperando instrucciones precisas. Es esencial que los 2 grupos actuen de forma coordinada en la ejecución del plan. Por supuesto ninguno de ellos ...

1. A un mensajero es enviado a través de la ciudad, con instrucciones del Jefe.
2. El mensajero alcanza su destino. Así y de este modo ambas partes conocen el plan de acción. Sin embargo el Jefe no sabe que su mensaje ha sido enviado (los atracos son un ocurrencia comun) Así el mensajero es enviado de nuevo, para confirmar el mensaje.
3. El mensajero llega al Jefe sano y salvo. De este modo, todo el mundo sabe que el mensaje ha llegado. Desde luego, los hombres del almacen no son conscientes de que el paso 3 ha sucedido. Y deben asegurarse una vez más a pesar de que vaya el mensajero.
4. Así los hombres del almacen saben ahora que el paso 3 ha sido exitoso pero solo si pueden comunicar que son conscientes y estan al corriente.

Adviertase que las necesidades de ambas partes son perfectamente razonables. Ellos unicamente quiero alcanzar un estado en donde:

1. El mensaje original (plan de accion) ha sido enviado de forma exitosa, y
2. Ambas partes saben que hay un acuerdo mutuo que
   1. ha ocurrido

Hecho

1. Aun a pesar de que la secuencia no puede terminar exitosamente

Prueba

(a) De forma clara la secuencia contiene al menos 1 mensaje de importancia. (b) Asumiendo que es posible alcanzar el estado deseado despues de una secuencia de mensajes finita.

Entonces debe existir un numero n > 1 de modo que n es la distancia de la mas pequeña de las secuencias que es aquella que permite que alcancemos este estado.

The Problems of Gansters A group of gangsters are about to pull off a big Job. The plan of action is prepared down to the last detail~ Some of the men are holed up in a warehouse across town, awaiting precise instructions. It is absolutely essential that the two groups act with complete reliance on each other in executing the plan. Of course, they will never get around to putting the plan into action, because the following sequence of events is bound to take place. i. A messenger is dispatched across town, with instructions from the boss. 2. The messenger reaches his destination. At this point both parties know the plan of action. But the boss doesn't know that his message got through (muggings are a common occurrence). So the messenger is sent back, to confirm the message. 3. The messenger reaches the boss safely. Now, everybody knows the message got through. Of course, the men in the warehouse are not aware that step 3 occurred, and must he reassured. Off goes the messenger. 4. Now the men in the warehouse too know that step 3 was successful, but unless they communicate their awareness... . . . . . . . . . . , . . . Note that the needs of both parties are quite reasonable. They simply want to reach a state where

(I) The original message (i.e., the plan of action) is successfully delivered, and (2) Both parties know that they are in mutual agreement that (i) occurred.

Fact The sequence cannot terminate successfully.

Proof (a) Clearly the sequence contains at least one message of importance. (b) Assume that it is possible to reach the desired state after a finite sequence of messages. Then there must exist a number n > 1 such that n is the length of the shortest sequence which gets us to this state.

Since this is the shortest sequence, the last message in it is important: if the n'th message gets lost, the desired state cannot be reached. The sender of the n'th message must receive acknowledgment. This means that the sequence is at least of length n + i. The assumption is contradicted and the sequence cannot be finite.

Note also that the sequence is infinite even when none of the messages are actually lost. At first glance it would seem that if the two processes are in continuous communication, the problem can be solved by including a sequence number [8] as part of each message. But this is not really so: sequence numbers are analogous to the step numbers in the above example. At any time the process receiving the highest numbered message knows the complete state while the other lives in doubt. Thus in practice only sequential events can be controlled but simultaneity cannot he achieved by this means.

Enlaces externos sobre la Naturaleza de Internet

• THE COORDINATION PROBLEM — Twan, James E. (Jed) Donnelley - Financial Cryptography.

• A Distributed Capability Computing System (DCCS) — James E. (Jed) Donnelley. Publication date: August 3, 1976. Last update to this HTML version, August 18, 2006 --Jed

• http://consc.net/mindpapers/7.1j Computationalism in Cognitive Science (Computationalism in Cognitive Science on PhilPapers)