## 1 Introduction

In a study of computational models in distributed systems [1] the following problem concerning communicating processors was posed. Initially each processor has its own input data item, . Nature selects a series of tournaments on vertex set , and communication proceeds in rounds. For every each processor communicates in round every data item that has reached him so far to every processor with . By an old theorem of Landau [2], if then after two rounds a King emerges. Namely, a processor , such that has reached all processors. Here we address the question how many rounds are required for a King to emerge if in each round an arbitrary tournament is selected. Surprisingly the answer is still .

## 2 Two rounds suffice

Let be two tournaments. The condition that data item reaches processor after two rounds of communication is denoted by . Clearly, this is equivalent to

It is useful to note that the negation of this condition is equivalent to

(1) |

where is the set of out-neighbors of in tournament .

###### Theorem 1.

Let be two tournaments. Then there is such that for every .

###### Proof.

By induction on . The statement is easily verified for . Let be the smallest integer for which the theorem does not hold and let be a counterexample. By minimality of , for every there is some such that for every , where indicates that the relation is defined with respect to tournaments and . When this happens we say that is singled out by . Clearly , or else the theorem holds with , since clearly implies . Consequently, no vertex is singled out more than once. We denote and conclude that is a permutation on , since is defined for every and is an injective mapping.

However, this is impossible. By Condition (1), every satisfies . But , since is a permutation. This contradiction completes the proof. ∎

The same proof yields as well

###### Corollary 2.

Let be two tournaments. Then there is , such that for every .

###### Proof.

The same proof works. Just switch between and reverse all edges in the two tournaments.

∎

## 3 A weaker corollary with a simpler proof

A simpler proof for a weaker corollary of Theorem 1 was suggested by an anonymous referee. This corollary is a generalization of [2], and is as follows:

###### Corollary 3.

Let be a red and a blue tournaments. Then there is , called king, such that for every , is reachable from with a rainbow directed path of length at most .

The critical difference is that in Theorem 1 must be reachable by either a blue edge, or by a red edge, or by a red edge followed by a blue edge (but a blue edge followed by a red edge does not count). In Corollary 3 on the other hand, must be reachable by eiter of the above or by a blue edge followed by a red edge. This weaker corollary is not strong enough for our application [1], where corresponds to a first round of message delivery and to a second round, where and are selected by an adversary. And by Theorem 1 regardless of the adversary choices there is a node whose information becomes known to everyone in two rounds. This does not follow from Corollary 3.

###### Proof.

While it is a straightforward corollary of Theorem 1 here is a simpler proof of Corollary 3. Let be of the largest in-degree in either or . Assume, that the largest in-degree is realized in . Then delete and use induction. Let the resulting king be . As the blue in-degree of is no larger than the red in-degree of (by the definition of ), there is a path of length from to or a blue-red path of length from to . ∎

## References

- [1] Y. Afek and E. Gafni: A simple characterization of asynchronous computations. Theor. Comput. Sci. 561: 88-95 (2015) Also in Asynchrony from Synchrony. Arxiv, http://arxiv.org/abs/1203.6096 , Janurary 2012
- [2] H. Landau. On dominance relations and the structure of animal societies, III: The condition for score structure. Bulletin of Mathematical Biophysics, 15(2):143 148, 1953.

Comments

There are no comments yet.