[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

69.0. "British Soldiers Problem" by HARE::STAN () Tue May 22 1984 17:25

This problem has been bothering me for years.  Maybe someone
here can solve it.  I believe it was originally proposed by Conway.
It is called the British Soldiers problem.

You have n British soldiers in a line.  Each soldier is initially
ar rest.  Each soldier is identical and his actions can be described
by a finite state automaton.  A soldier's new state depends only
on his previous state and the previous state of the two soldiers
next to him. (The two soldiers on the end have fictitious neihbors
to one side who are always in the fictitious state.)

Your problem is to design the states (e.g. rest, at ease, ready, attention,
etc.) and the state transitions, so that it is possible for a sargeant to come
over and order one guy on the end into the attention state and so that
this will eventually cause all the soldiers to fire their guns
simultaneously.  No gun may fire prior to this occurrence.
You may only specify a finite number of states.  Your solution must
work regardless of the value of n. (In particular, I may line up
more soldiers than you have states.)
T.RTitleUserPersonal
Name		DateLines
69.1HARE::STANFri May 25 1984 00:53142
Gilbert and I have finally found a solution with 14 states.
The breakthrough came when Peter suggested sending out two signals
simultaneously, one travelling at three times the speed of the
other.  Anyhow, I give below the states and the state transitions.
Following that is a sample printout showing the situation for the
case where there are 22 soldiers.  This solution has been tested
via a computer simulation for up to 100 soldiers.  Other solutions
are surely possible.  Can you find a more elegant solution or a
solution with fewer states?

The states are:

.	At rest
Att	At attention
Fic	Fictitious state
Rdy	Ready
Aim	Aiming your rifle
Fir	Firing your rifle
->	Nudging guy on your right
<-	Nudging guy on your left
=>	Kicking guy on your right
<=	Kicking guy on your left
S>	Salute to the right
<S	Salute to the left
F>	Face to the right
<F	Face to the left

Notation: We say someone is in authority if he is at attention,
	  aiming, ready, or fictitious.

The transitions can be summarized as follows:
Do the first one that applies.  If none apply, remain in the same state.

If you are at rest, then
	If both your neighbors are in authority, then become ready.
	If one is ready, then nudge the other neighbor.
	If one neighbor nudges you and the other kicks you, then
		go to attention.
	If one nieghbor is nudging you, then nudge the other neighbor.
	If one nieghbor is kicking you, then salute the other neighbor.

If you are nudging a neighbor, then
	If he is in authority, then nudge your other neighbor instead,
		but if they are both in authority, then become ready.
	If he is facing you, then go to attention.
	If the guy you weren't nudging is ready then salute
		the guy you were nudging.
	Otherwise, go back to rest.

If you are at attention, then become ready.

If you are ready, then aim.

If you are saluting a neighbor, then face him.

If you are facing a neighbor,
	and he is nudging you, then go to attention,
	otherwise kick him.

If you are kicking a neighbor, then go back to rest.

If you are aiming and both your neighbors are aiming (or fictitious),
	then fire!

Explanation:

Basically, a person at attention sends out two signals (actually
2 signals in each direction for a total of 4 signals).
One signal travels very fast and consists of a person nudging the next
guy in line.  A second signal travels at one third this speed and ends
up with a guy kicking the next guy in line every third time period.
(The sequence goes: salute, face, kick.) The signals bounce off the ends or
off other people already in the aim position.
When the two signals meet, we have found the center of
the sequence of soldiers and we put the center guy (or guys) into
the attention state and reiterate on each half. The attention state sends
out the fast signal and the ready state sends out the slow signal.
A binary tree is formed, and eventually all the leaves go to the fire state.

[The remainder of this reply is 132 columns wide.]

 Att  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Rdy  ->  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  S>  ->  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  F>  .   ->  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  =>  .   .   ->  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  .   S>  .   .   ->  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  .   F>  .   .   .   ->  .   .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  .   =>  .   .   .   .   ->  .   .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  .   .   S>  .   .   .   .   ->  .   .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  .   .   F>  .   .   .   .   .   ->  .   .   .   .   .   .   .   .   .   .   .   . 
 Aim  .   .   =>  .   .   .   .   .   .   ->  .   .   .   .   .   .   .   .   .   .   . 
 Aim  .   .   .   S>  .   .   .   .   .   .   ->  .   .   .   .   .   .   .   .   .   . 
 Aim  .   .   .   F>  .   .   .   .   .   .   .   ->  .   .   .   .   .   .   .   .   . 
 Aim  .   .   .   =>  .   .   .   .   .   .   .   .   ->  .   .   .   .   .   .   .   . 
 Aim  .   .   .   .   S>  .   .   .   .   .   .   .   .   ->  .   .   .   .   .   .   . 
 Aim  .   .   .   .   F>  .   .   .   .   .   .   .   .   .   ->  .   .   .   .   .   . 
 Aim  .   .   .   .   =>  .   .   .   .   .   .   .   .   .   .   ->  .   .   .   .   . 
 Aim  .   .   .   .   .   S>  .   .   .   .   .   .   .   .   .   .   ->  .   .   .   . 
 Aim  .   .   .   .   .   F>  .   .   .   .   .   .   .   .   .   .   .   ->  .   .   . 
 Aim  .   .   .   .   .   =>  .   .   .   .   .   .   .   .   .   .   .   .   ->  .   . 
 Aim  .   .   .   .   .   .   S>  .   .   .   .   .   .   .   .   .   .   .   .   ->  . 
 Aim  .   .   .   .   .   .   F>  .   .   .   .   .   .   .   .   .   .   .   .   .   ->
 Aim  .   .   .   .   .   .   =>  .   .   .   .   .   .   .   .   .   .   .   .   .  <- 
 Aim  .   .   .   .   .   .   .   S>  .   .   .   .   .   .   .   .   .   .   .  <-   . 
 Aim  .   .   .   .   .   .   .   F>  .   .   .   .   .   .   .   .   .   .  <-   .   . 
 Aim  .   .   .   .   .   .   .   =>  .   .   .   .   .   .   .   .   .  <-   .   .   . 
 Aim  .   .   .   .   .   .   .   .   S>  .   .   .   .   .   .   .  <-   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .   F>  .   .   .   .   .   .  <-   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .   =>  .   .   .   .   .  <-   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .   .   S>  .   .   .  <-   .   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .   .   F>  .   .  <-   .   .   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .   .   =>  .  <-   .   .   .   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .   .   .  Att  .   .   .   .   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .   .  <-  Rdy  ->  .   .   .   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .   .  <-  <S  Aim  S>  ->  .   .   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .   .  <-   .  <F  Aim  F>  .   ->  .   .   .   .   .   .   . 
 Aim  .   .   .   .   .   .  <-   .   .  <=  Aim  =>  .   .   ->  .   .   .   .   .   . 
 Aim  .   .   .   .   .  <-   .   .  <S   .  Aim  .   S>  .   .   ->  .   .   .   .   . 
 Aim  .   .   .   .  <-   .   .   .  <F   .  Aim  .   F>  .   .   .   ->  .   .   .   . 
 Aim  .   .   .  <-   .   .   .   .  <=   .  Aim  .   =>  .   .   .   .   ->  .   .   . 
 Aim  .   .  <-   .   .   .   .  <S   .   .  Aim  .   .   S>  .   .   .   .   ->  .   . 
 Aim  .  <-   .   .   .   .   .  <F   .   .  Aim  .   .   F>  .   .   .   .   .   ->  . 
 Aim <-   .   .   .   .   .   .  <=   .   .  Aim  .   .   =>  .   .   .   .   .   .   ->
 Aim  ->  .   .   .   .   .  <S   .   .   .  Aim  .   .   .   S>  .   .   .   .   .  <- 
 Aim  .   ->  .   .   .   .  <F   .   .   .  Aim  .   .   .   F>  .   .   .   .  <-   . 
 Aim  .   .   ->  .   .   .  <=   .   .   .  Aim  .   .   .   =>  .   .   .  <-   .   . 
 Aim  .   .   .   ->  .  <S   .   .   .   .  Aim  .   .   .   .   S>  .  <-   .   .   . 
 Aim  .   .   .   .   -> <F   .   .   .   .  Aim  .   .   .   .   F> <-   .   .   .   . 
 Aim  .   .   .   .  Att Att  .   .   .   .  Aim  .   .   .   .  Att Att  .   .   .   . 
 Aim  .   .   .  <-  Rdy Rdy  ->  .   .   .  Aim  .   .   .  <-  Rdy Rdy  ->  .   .   . 
 Aim  .   .  <-  <S  Aim Aim  S>  ->  .   .  Aim  .   .  <-  <S  Aim Aim  S>  ->  .   . 
 Aim  .  <-   .  <F  Aim Aim  F>  .   ->  .  Aim  .  <-   .  <F  Aim Aim  F>  .   ->  . 
 Aim <-   .   .  <=  Aim Aim  =>  .   .   -> Aim <-   .   .  <=  Aim Aim  =>  .   .   ->
 Aim  ->  .  <S   .  Aim Aim  .   S>  .  <-  Aim  ->  .  <S   .  Aim Aim  .   S>  .  <- 
 Aim  .   -> <F   .  Aim Aim  .   F> <-   .  Aim  .   -> <F   .  Aim Aim  .   F> <-   . 
 Aim  .  Att Att  .  Aim Aim  .  Att Att  .  Aim  .  Att Att  .  Aim Aim  .  Att Att  . 
 Aim Rdy Rdy Rdy Rdy Aim Aim Rdy Rdy Rdy Rdy Aim Rdy Rdy Rdy Rdy Aim Aim Rdy Rdy Rdy Rdy
 Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim Aim
 Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir Fir

          22 soldiers fire simultaneously after          58 steps.
69.2RANI::LEICHTERJFri May 25 1984 01:1328
This problem is most commonly known as the "firing squad synchronization
problem".  It appears as a problem in Marvin Minsky's "Computation - Finite and
Infinite Machines", Prentice Hall 1967; he has a long discussion of the
history of the problems, which appears to have been devised by Myhill in 1957.
Minsky and John McCarthy were the first to solve it.  (It arose in work on self-
reproducing automata, in trying to devise means to turn on all the parts of
a machine at once.)  The "quality" of solutions has traditionally been measured
by the time complexity of the solution as a function of n, the number of sol-
diers.  The two-wave method that is proposed in .1 - the most-commonly dis-
covered method - takes about 3n time.  (When I first solved the problem I came
up with an n^2 or so solution.  Rather than using waves of different rates, I
had each soldier successively send waves to each neighbor; for the middle man,
the two are reflected and arrive back within one unit of time of each other.
(Well, I WAS in high school at the time!))

It is easy to see that you need at least 2n-2 time units.  Amazingly enough,
a solution in exactly this time - due to E. Goto - is possible; it is very
complex, and has thousands of states!  There is a solution knonw with 8 states
and 8 kinds of signals that takes 2n time.

A paper with further information is "Generation of Primes by a one-dimensional
real-time iterative array", P.C. Fischer, JACM 12,388-394 (July 1965)

The problem is 2.7-5, should you dig up the book.

It's also ammusing to generalize to n dimensional arrays of soldiers.  It's
easy for n-parallelepipeds, harder - probably impossible - in general.
							-- Jerry
69.3HARE::STANSat May 26 1984 15:5227
From:	RHEA::DECWRL::"decvax!ulysses!mcnc!unc!mhuxl!sfjec!jss" 26-MAY-1984 14:49
To:	mhuxl!ulysses!unc!mcnc!decvax!decwrl!dec-rhea!dec-hare!stan
Subj:	RE: The British Soldiers Problem

Received: from DECWRL by DEC-RHEA with SMTP; Sat, 26 May 84 11:41-PDT
Received: by decwrl.ARPA (4.22.01/4.7.31)
	id AA00732; Sat, 26 May 84 11:47:19 pdt
Received: by decvax.UUCP (4.12/1.0)
	id AA21249; Sat, 26 May 84 12:06:59 edt
Received: by unc (4.12/4.7) id AA01630; Sat, 26 May 84 06:31:35 edt
Received: by ulysses.UUCP (4.12/4.7)
	id AA24635; Sat, 26 May 84 06:24:41 edt
Date: Sat, 26 May 84 06:24:41 edt
Original-From: <mhuxl!sfjec!jss@ulysses>
Message-Id: <[email protected]>
References: <[email protected]>

I have seen this problem called the "Firing Squad Problem".
I vaguely recall an article in Information and Control
sometime between 1964 and 1968. (Those were the years
I was an undergraduate and I am pretty sure of them, 
although less sure of the Journal and have a total
blank for the author.)

Jerry Schwarz
69.4HARE::STANWed Jun 06 1984 20:5220
From:	RHEA::DECWRL::"allegra!rabbit!jbk"  6-JUN-1984 17:12
To:	hare::stan
Subj:	

Received: from DECWRL by DEC-RHEA with SMTP; Wed,  6 Jun 84 14:10-PDT
Received: by decwrl.ARPA (4.22.01/4.7.31)
	id AA18771; Wed, 6 Jun 84 14:10:55 pdt
Received: by allegra.UUCP (4.12/4.7)
	id AA03453; Wed, 6 Jun 84 16:45:54 edt
Date: Wed, 6 Jun 84 16:45:54 edt
Message-Id: <[email protected]>
Re: British Soldiers problem
Apparently-To: decwrl!rhea!hare!stan

In the early sixties, this problem enjoyed considerable prominence, though
I remember the name as a bit different: no "British", and some other words were
used, but it did involve soldiers.
Ed F Moore, then at Bell Labs and now, I believe, at University of Wisconsin
Math Dept, did considerable work on it in the early sixties (or possibly a bit
earlier).   Joseph B Kruskal - Bell Labs, Murray Hill
69.5HARE::STANMon Dec 31 1984 19:589
I made up a related problem which I call the Hora Synchronization
problem.  Suppse you have n people in a circle (dancing the Hora).
Each person's state depends only upon his previous state and the
previous state of the person to his right.  Can you now assign
states and transitions so that everone ends the dance simultaneously
(and no one ends prematurely)?  [Everyone starts at rest and then one
person begins by kicking his right foot in the air.]

I have no solution to this problem.
69.6SPRITE::OSMANTue Jun 18 1985 10:5212
It sounds like more constraints are needed in order to rule out the following
trivial solution (or others almost as trivial but slightly disguised):

	States are ATTENTION, FACETIOUS, AT REST.

	If you or your neighbor on the right or the neighbor on the left
	are at ATTENTION or are FACETIOUS or are AT REST, then FIRE !

What have I violated ?

/Eric
69.7METOO::YARBROUGHTue Jun 18 1985 14:122
re .6: You overlooked the condition "no gun may fire prior to...". In your
case the soldiers will fire continuously.
69.8ORPHAN::BRETTTue Jun 18 1985 19:294
The initial state is "all at ease", then an act of god (all sargent-majors
are gods), places the first at attention...

/Bevin
69.9ALIEN::POSTPISCHILWed Jun 19 1985 10:235
To be more specific, the soldiers might be at ease for several periods before
one of them is ordered to attention.


				-- edp
69.10SPRITE::OSMANWed Jun 19 1985 14:559
O.K., I see now that my solution is invalid because of the stipulation that
until the sargent has commanded the first soldier to attention, nobody may
fire.

However, the other objection to my solution, namely that the soldiers will
continuously fire, is easily remedied.  Just add a rule "if you are firing,
run out of bullets!" (yes, new state: "out of bullets")

/Eric
69.11TOOLS::STANWed Jun 19 1985 15:341
Remember: they must all fire exactly once and simultaneously.
69.12RANI::LEICHTERJSun Jun 30 1985 23:3435
This problem has recently come back to life in a new form:  Suppose some
number of the soldiers may be "faulty", so that they make unpredictable state
transitions - perhaps even conspiring with each other to confuse everyone
else.  Can you get the non-faulty soldiers to fire correctly?  Obviously,
you need to change the problem somewhat - if the communication remains as
in the original - strictly linear - even a single soldier who is faulty in
that he is asleep and ignores all orders makes a solution impossible.
The published papers assume any soldier may send a message to any other
soldier.  (This is a variation on another "classic" - i.e., 4 or-so-year-
old problem in fault-resistant computation, the "Byzantine generals" problem,
AKA te distributed agreement problem, AKA the reliable broadcast problem:
There are n finite state machines, up to k of which may be faulty, where
again "faulty" generally means "can do anything at all, even something not
computable by a Turing machine, and in perfect secret communication with
each other".  All he machines are connected to each other by (failure-proof)
point-to-point links - so they can send each oher messages, and a machine
can determine with certainty the IMMEDIATE sender of a message - but not
necessarily if a message forwarded to it really came from where it claims
to have come from.  One machine, say M, is given a single bit B.  We require
an algorithm with the following properties:

	- Eventually, all the non-faulty machines print a single bit Bi.

	- If M is non-faulty, all the Bi's are equal and are equal to B.

("Eventually" means "after a fixed (expected) time depending only on n and k"
for deterministic (probabilistic) algorithms.)

It turns out that a solution exists if and only if n > 3k.  However, this
assumes a synchronous system - either a fixed clock available to all machines,
or, at least, a maximum bound on how long a message will take to be delivered,
including computation time at the sender.  (I'm grossly oversimplifying here.)
In the asynchronous case, even a single failure by a node that just stops
responding cannot be dealt with!)
							-- Jerry
69.13TOOLS::STANMon Jul 01 1985 01:421
That all sounds neat.  Can you give us some references to these problems?
69.14RANI::LEICHTERJWed Jul 24 1985 00:289
The only reference I could find quickly is in the May 1984 TOCS - "Byzantine
Generals in Action:  Implementing Fail-Stop Processors", by Fred Schneider,
page 145 (V2#2).  It has a good list of references.

The stuff on impossibility of finding a solution in the asynchronous case, and
on the firing squad problem, is all recent.  I don't remember exactly where I
saw the papers - probably JACM.  There are a couple of IBM Watson Labs tech
reports on this, too.
							-- Jerry
69.15RANI::LEICHTERJWed Jul 24 1985 02:1813
I just discovered that I have one of the IBM research reports here.  It is:

"On the Minimal Synchronism Needed For Distributed Concensus", by Dolev, Dwork,
and Stockmeyer; IBM Research Report RJ 4292 (46990) 5/8/84.  They provide a
reference to the article on the need for synchronization - "Impossibility of
Distributed Concensus With One Faulty Process", by Fisher, Lynch, and Paterson
(Proc. 2nd Annual Symp. on Principles of Database Systems, 1983).  I think
an updated version of this paper was in the JACM recently.

Looking through the reference list, I find following easy-to-get-hold-of
article:  "The Byzantine Generals Problem", by Lamport, Shostak, and Pease.
(TOPLAS 4(1982), pg. 382-401).
							-- Jerry