Conference rusure::math

303.0. "Hora Synchronization" by LATOUR::JMUNZER () Wed Jun 12 1985 14:18

Response 5 to note 69 poses the Hora Synchronization problem:

	n finite state automata are dancing

	one kicks his foot in the air

	the automata make state transitions based only on their own states
		and the state of their left hand neighbor

	they come to a synchronized stop

Below is a partial solution...for n equal to a power of two.

It is heavily dependent on Stan's and Peter's ideas.

Five "signals" are used.  The kicker sends signals 1 and 2 at different speeds.
They are relayed by the nonkickers, and arrive at the kicker at different
times.  When they do, he sends signals 4 and 5, which meet halfway around
the circle from the kicker.  Where they meet, a nonkicker turns into a kicker.

Signal 3 is also sent by the old kicker to himself, timed so that he sees
it just when the new kicker becomes a kicker.  They both start over again
with signals 1 and 2.

A remarkable thing about this approach is that two kickers, opposite to
each other on a circle, can appear to the dancers/automata in the middle
to be only one kicker on a circle of half the circumference.  This is one
of the ideas of the aforementioned dependency (thanks).

I have an automaton and a simulator for the Hora Synchronization.  Below is
its output for 8 dancers.

	*	Kicker states are -xxxxx

	*	Nonkicker states are +xxxxx

	*	Asterisked states mean the dancers stop

	*	xxxxx are counters to govern the existence/speed of the
		five signals

		-	Count signal 1 from 1 to 2, then pass it to the
			right and reset to 0; e.g.
			o	-10000  -00000		count = 1
			o	-20000  -00000		count = 2
			o	-00000  -10000		pass to the right
		-	Count signal 2 from 1 to 3, etc.
		-	Count signal 3 from 1 to 2, etc.
		-	Count signal 4 from 1 to 4, etc.
		-	Count signal 5 from 1 to 2, etc.

	*	When a kicker sees signal 1, start signals 3 and 4

	*	When a kicker sees signal 2, start signal 5 

	*	When a kicker sees signal 3, start signal 1 and 2 

	*	When a nonkicker sees signals 4 and 5, become a kicker and
		start signals 1 and 2

	*	The initial kicker starts signals 1 and 2 at the top left;
		each following horizontal line is a new set of states for
		the 8 dancers.  Note the rightmost column is the starter's
		left-hand neighbor.
                                                                         
-11000  +00000  +00000  +00000  +00000  +00000  +00000  +00000  
-22000  +00000  +00000  +00000  +00000  +00000  +00000  +00000  
-03000  +10000  +00000  +00000  +00000  +00000  +00000  +00000
-00000  +21000  +00000  +00000  +00000  +00000  +00000  +00000  
-00000  +02000  +10000  +00000  +00000  +00000  +00000  +00000  
-00000  +03000  +20000  +00000  +00000  +00000  +00000  +00000  
-00000  +00000  +01000  +10000  +00000  +00000  +00000  +00000  
-00000  +00000  +02000  +20000  +00000  +00000  +00000  +00000  
-00000  +00000  +03000  +00000  +10000  +00000  +00000  +00000  
-00000  +00000  +00000  +01000  +20000  +00000  +00000  +00000  
-00000  +00000  +00000  +02000  +00000  +10000  +00000  +00000  
-00000  +00000  +00000  +03000  +00000  +20000  +00000  +00000  
-00000  +00000  +00000  +00000  +01000  +00000  +10000  +00000  
-00000  +00000  +00000  +00000  +02000  +00000  +20000  +00000  
-00000  +00000  +00000  +00000  +03000  +00000  +00000  +10000  
-00000  +00000  +00000  +00000  +00000  +01000  +00000  +20000  
-00110  +00000  +00000  +00000  +00000  +02000  +00000  +00000  
-00220  +00000  +00000  +00000  +00000  +03000  +00000  +00000  
-00030  +00100  +00000  +00000  +00000  +00000  +01000  +00000  
-00040  +00200  +00000  +00000  +00000  +00000  +02000  +00000  
-00000  +00010  +00100  +00000  +00000  +00000  +03000  +00000  
-00000  +00020  +00200  +00000  +00000  +00000  +00000  +01000  
-00000  +00030  +00000  +00100  +00000  +00000  +00000  +02000  
-00000  +00040  +00000  +00200  +00000  +00000  +00000  +03000  
-00001  +00000  +00010  +00000  +00100  +00000  +00000  +00000  
-00002  +00000  +00020  +00000  +00200  +00000  +00000  +00000  
-00000  +00001  +00030  +00000  +00000  +00100  +00000  +00000  
-00000  +00002  +00040  +00000  +00000  +00200  +00000  +00000  
-00000  +00000  +00001  +00010  +00000  +00000  +00100  +00000  
-00000  +00000  +00002  +00020  +00000  +00000  +00200  +00000  
-00000  +00000  +00000  +00031  +00000  +00000  +00000  +00100  
-00000  +00000  +00000  +00042  +00000  +00000  +00000  +00200  
-11000  +00000  +00000  +00000  -11000  +00000  +00000  +00000  
-22000  +00000  +00000  +00000  -22000  +00000  +00000  +00000  
-03000  +10000  +00000  +00000  -03000  +10000  +00000  +00000  
-00000  +21000  +00000  +00000  -00000  +21000  +00000  +00000  
-00000  +02000  +10000  +00000  -00000  +02000  +10000  +00000  
-00000  +03000  +20000  +00000  -00000  +03000  +20000  +00000  
-00000  +00000  +01000  +10000  -00000  +00000  +01000  +10000  
-00000  +00000  +02000  +20000  -00000  +00000  +02000  +20000  
-00110  +00000  +03000  +00000  -00110  +00000  +03000  +00000  
-00220  +00000  +00000  +01000  -00220  +00000  +00000  +01000  
-00030  +00100  +00000  +02000  -00030  +00100  +00000  +02000  
-00040  +00200  +00000  +03000  -00040  +00200  +00000  +03000  
-00001  +00010  +00100  +00000  -00001  +00010  +00100  +00000  
-00002  +00020  +00200  +00000  -00002  +00020  +00200  +00000  
-00000  +00031  +00000  +00100  -00000  +00031  +00000  +00100  
-00000  +00042  +00000  +00200  -00000  +00042  +00000  +00200  
-11000  +00000  -11000  +00000  -11000  +00000  -11000  +00000  
-22000  +00000  -22000  +00000  -22000  +00000  -22000  +00000  
-03000  +10000  -03000  +10000  -03000  +10000  -03000  +10000  
-00000  +21000  -00000  +21000  -00000  +21000  -00000  +21000  
-00110  +02000  -00110  +02000  -00110  +02000  -00110  +02000  
-00220  +03000  -00220  +03000  -00220  +03000  -00220  +03000  
-00031  +00100  -00031  +00100  -00031  +00100  -00031  +00100  
-00042  +00200  -00042  +00200  -00042  +00200  -00042  +00200  
-11000  -11000  -11000  -11000  -11000  -11000  -11000  -11000  
*22000  *22000  *22000  *22000  *22000  *22000  *22000  *22000  
stop

I suspect your solution only works for N < 2^5, or 32.   Try it with 100
dancers.   Also, try it with non-powers of two.
      
Since I suspect you need LOG2(N) signals, your solution is not independent
of the number of kickers.

/Bevin

Re .1:

The five signals are used to divide the circle into two parts.  These five
signals will accomplish the task whenever the number of dancers is even.  As
soon as the division is accomplished, the circle is symmetric when one kicker
is rotated into the place of another, so it is equivalent to the problem of
a circle which is one-half the size.  Such a circle would also be divided,
provided the original size was a multiple of four.  This continues
indefinitely, so any circle whose size is a power of two will be conquered by
these automata.

Generalization to non-powers of two does not seem to be difficult:

	If a dancer has signal 4 at a count of 2 and signal 5 at a count
	of 1, become a high-kicker and set all counts to 0.

	If the dancer to the left has the signals described above, become
	a kicker and start signals 1 and 2.

	If a dancer is a high-kicker, it should steal signals from the dancer
	on the left one cycle early and go into the final count of the stolen
	signal.  When the dancer on the left does go into the final count, it
	should be ignored.

The effect of the first two rules is to recognize that the 4 and 5 signals are
out of synchronization because the number of dancers is odd and to rectify this
by creating two kickers instead of one.  This divides the circle into two
equal-sized segments.

The effect of the third rule is to pass the signals along a little early, so
that a kicker following a high-kicker receives and emits signals as if the
high-kicker were absent.

Also, the rule for going into a stopped state was not mentioned, but I
believe it can be:

	When a kicker has a kicker on the left, stop.

The new rule would be:

	When a dancer is a kicker or a high-kicker and the dancer on the
	left is a kicker or a high-kicker with signal 1 at count 2, stop.

An example follows, using 5 dancers.  A high-kicker is denoted by "!".

-11000	+00000	+00000	+00000	+00000
-22000	+00000	+00000	+00000	+00000
-03000	+10000	+00000	+00000	+00000
-00000	+21000	+00000	+00000	+00000
-00000	+02000	+10000	+00000	+00000
-00000	+03000	+20000	+00000	+00000
-00000	+00000	+01000	+10000	+00000
-00000	+00000	+02000	+20000	+00000
-00000	+00000	+03000	+00000	+10000
-00000	+00000	+00000	+01000	+20000
-00110	+00000	+00000	+02000	+00000
-00220	+00000	+00000	+03000	+00000
-00030	+00100	+00000	+00000	+01000
-00040	+00200	+00000	+00000	+02000
-00000	+00010	+00100	+00000	+03000
-00001	+00020	+00200	+00000	+00000
-00002	+00030	+00000	+00100	+00000
-00000	+00041	+00000	+00200	+00000
-00000	+00002	+00010	+00000	+00100
-00000	+00000	+00021	+00000	+00200
-11000	+00000	!00000  -11000	+00000
-22000	+00000	!00000	-22000	+00000
-03000	+10000	!00000	-03000	+10000
-00000	+21000	!20000	-00000	+21000	Here, signal 1 is stolen early.
-00110	+02000	!00000	-00110	+02000
-00220	+03000	!03000	-00220	+03000	Here, signal 2 is stolen early.
-00031	+00100	!00000	-00031	+00100
-00042	+00200	!00200	-00042	+00200	Here, signal 3 is stolen early.
-11000	-11000	!00000	-11000	-11000
-22000	-22000	!20000	-22000	-22000	Here, signal 1 is stolen early.
*03110	*03110	*03000	*03110	*03110

By the way, I am sure many people have seen films showing schools of fish
which will suddenly all turn in unison.  Do you think there is any connection
between this problem and the fish?


				-- edp

>  By the way, I am sure many people have seen films showing schools of fish
>  which will suddenly all turn in unison.  Do you think there is any connection
>  between this problem and the fish?

    Sure.  And a connection between faulty solutions and the waves at
    sports events.
    
    John

Given a solution to the firing squad problem, the Hora problem is easy.

The starter just sends two full-speed signals in both directions, then turns
herself into a double endpoint (for two firing squads).  If her own signals hit
her (next move), she is in a 1-member circle, and knows what to do.  Otherwise,
there are two cases depending on whether the circle is even or odd.

If even, someone will get hit by both signals at the same time, and turns
himself into a double endpoint for two firing squads, acting as the starter for
both.  If odd, two people will get hit by signals on consecutive turns; they
turn themselves into starters for a firing squad in the obvious direction.

(The signals are not propagated further once the starter or starters are found.)