Emmanuel Godard - LIS - Pole Calcul
Channel: Pole Calcul
Date: 22/10/2019

Titre: Back to the Coordinated Attack Problem

We consider the well known Coordinated Attack Problem, where two gener-
als have to decide on a common attack, when their messengers can be captured
by the enemy. Informally, this problem represents the difficulties to agree in the
present of communication faults. We consider here only omission faults (loss of
message), but contrary to previous studies, we do not to restrict the way mes-
sages can be lost, i.e. we make no specific assumption, we use no specific failure
metric. In the large subclass of message adversaries where the double simulta-
neous omission can never happen, we characterize which ones are obstructions
for the Coordinated Attack Problem. We give two proofs of this result. One is
combinatorial and uses the classical bivalency technique for the necessary con-
dition. The second is topological and uses simplicial complexes to prove the
necessary condition. We also present two different Consensus algorithms that
are combinatorial (resp. topological) in essence. Finally, we analyze the two
proofs and illustrate the relationship between the combinatorial approach and
the topological approach in the very general case of message adversaries. We
show that the topological characterization gives a clearer explanation of why
some message adversaries are obstructions or not. This result is a convincing
illustration of the power of topological tools for distributed computability.

Joint work with Eloi Perdereau