Robust-first Computing Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Finding my place in the crowd: Group formation and localization in a virtual environment. ======

Final link of download: http://cs.unm.edu/~afruizc/file.zip

==Graphs:==
{{:people:andres_ruiz:organization.pdf|}}
{{:people:andres_ruiz:localization.pdf|}}
{{:people:andres_ruiz:mixed.pdf|}}
== Final DRAFT of the paper: ==
http://cs.unm.edu/~afruizc/finding-place-crowd.pdf

== Abstract: ==
In the Movable Feast Machine, direct interaction is limited to small regions of space, but many computations could benefit from larger scale structure. This paper presents a simple aggregation and localization strategy allowing individuals to form communicating groups and find their own absolute positions within the group

== Model Description: ==
Figure 1: [[http://cs.unm.edu/~afruizc/ASDF_element.png|External Link]]

In order to understand the model, it is first important to give a couple of definitions that will help in the complete realization of the problem.
The density of the element means the amount of empty spaces that are allowed to exist between any pair of elements.
The state of an element is basically a name that is given to the conditions that describe one element at an specific point of time.
The attractor state is the state in which an ASDF element moves elements that are around and brings them close to where the element is located. The process of how this movement is done is expanded in the next sub-sections.

There is a two stage process that will successfully achieve the desire result of localization of each one of the elements inside their blob.
These self-organization and localization stages are roughly described in section 3.1, and are given a more thorough treatment in section 3.2.

Section 3.1: Model Overview.

As mentioned earlier, the ASDF elements will self-assemble in different blobs that will then start their localization process based on where they consider their global position in the blob is. After several iterations of the localization process, convergence will be achieved and all the elements will then have an idea of where their place in the blob is. This place will be determined by the amount of cells that one element is away from the boundary elements. A boundary element is an element that at a certain coordinate (north, south, west or east) doesn’t have any neighbors towards that direction, i.e. all the neighbouring cells in that direction are empty. After the localization process, if there is some sort of interruption (like a nuke or some elements are moved by dreg), the elements would go back to the self-organization stage and then the localization process will be repeated. 

We now briefly describe what an Event in the MfM architecture is because this will provide us with a useful framework to describe the behavior of the ASDF element in both, the organization and the localization stage. In its most essential case, an event is the means by which the mfm tells an atom that it is their turn to wake up, interact with the environment, change its internal and its neighbors’ state and go back to sleep, An event is assigned at random to each event, and there is no guarantee on the amount of events an atom is receiving however, because of probabilities and calculations it is true in practice that on average, all the elements will get an event after certain period of time. 

Section 3.2. Model detailed description

We now give all the details on how both stages of the operations are performed, and we highlight the relevant points that allow our element to perform as expected.

Section 3.2.1: Self-organization process

The self-organization process is the basis that allows the final result to be achieved. The resulting state in which the elements are at the end of this stage, will determine how good or bad the localization process will turn out to be. The self-organization process occurs as follows, and it is summarized in algorithm 1.

Algorithm 1:

	function self_organization():
		if (I become attractor):
			A[] = empty elements in ew.
			B[] = ASDF elements in ew.
			i = j = 0
			while (empty_spots && elements_to_relocate):
				change pos of element B[i] to A[j]
				turn B[i] into attractor
				increment i and j

In words, what the self-organizing procedure does is: at the beginning of an event, every element has some chances of becoming an attractor, if it turns out that the element does not become an attractor, the normal execution of the behavior function will continue; if on the contrary, the element does become an attractor, then it will gather information from it’s event window, this information includes all the elements that are empty, starting from radius 1 to radius 4, and other ADSF elements starting from radius 4 to radius 1. These two orderings of operations are important because they allow for the elements stay as close as “possible”. After having these two pieces of data, the element will start allocating the ASDF elements that were found on the outer layers into the inner layers of empty spaces, while also turning this elements into attractors creating some sort of a zombie effect.

After this step is done some more work has to be done in the density blahh..

Section 3.2.2: Localization process

In order to carry out the Localization Process (locp from now on), it is important to have the elements as close together as possible, or at least, as least spread as possible, because this will provide a better sense of self-awareness of each element’s position on the blob they belong to.

This second stage assumes that, in addition to determining whether an element is an attractor or not, the elements have to have some state stored in them. Each ASDF element has four counters for north, east, south and west which indicate their distance to the boundary of the enclosing square that is seen in the last lower square of figure 1. Algorithm 2 describes the process of localization.

Algorithm 2

	function self_organization():
		if (has_converged?):
			if (this should check again):
				if (! has_converged?):
					set convergence flag OFF
					alert neighbors of discrepancy
		else:
			this.count_north = north_n.count_south + 1
			this.count_south = north_n.count_north + 1
			this.count_east  = north_n.count_west  + 1
			this.count_west  = north_n.count_east  + 1
			# Now for each direction check the two directions
			# orthogonal to it in order to determine convergence
			# and to fix discrepancies.
			
			# For north I should then check east and west and
			# compare my north counter with them.
			this.count_north = max(this.count_north, east_n.count_north, west_n.count_north)
			
			# and perform this for the other three counts.
			# after all has been done, check for convergence.
			if (has_converged?):
				set convergence flag ON


The locp can get confusing, which is why we will try to cover all the caveats that it brings along. It is helpful to look at figure 1 and understand this as a converge process, meaning all the elements in a blob will eventually have a correct value on each one of their counters, however throughout different iterations the values for some elements might be wrong. In fact, for the first iteration of each element, only the elements that adjoin with the enclosing rectangle will have the right value for only one coordinate, every other element will have their counters tweaked. 

Think about the best way to explain the crap out of this!