Download the Source Code from The Page of Downloads

Cellection Framework is a cellular automata based problem solving framework. Cellular Automata are discrete dynamical systems capable of modeling highly complex physical phenomenon. The principles oflocalityanduniformitygives these automata an edge over the conventional computational mechanisms, which is very hard to perceive unless we actually use them in our daily computations. However, there are hardly any problems in our computational field (compared to physical phenomenon) that can fully utilize the power of cellular automata. Hence building a cellular framework for solving computational functions is nothing but reducing thedoseof cellular automata. However, here we dare to make this step - not with the interest of solving the computational problems in cellular automated way - but rather with the intention of demonstrating the power, atleast partially, of cellular automata.

Cellection framework is a way of programing theprogrammable matter. Just the way one solves complex functions with the mechanisms of structured programming methods, cellection framework provides mechanisms for solving the problems using programmable matter methods. What distinguishes the programmable matter is the availability of a massive amount of fine-grained parallelism [1].

In cellular automated worlds it is common for cells to communicate among themselves. Cells that form close neighborhoods undergo the process of communication - affecting each other's state and there byy triggering the state changes among themselves. This framework hardly deviates any length from this convention. We use what we call aproposalas the basic unit of communication among the cells. Typically a proposal would be a group of similar objects that share some common property or have agreed upon some common condition. And it is this common condition by which we control the behavior of this framework.

Class _Proposal { Vector<int> indices; Public: _Proposal() {} _Proposal(_Proposal &p) { *this = p; } Bool IsOk(int index, bool Table[n][n]) { For(int i = 0; i < indices.size(); i++) If(Table[indices[i]][index] == false) Return false; Return true; } _Proposal &CreateAValidProposal(int index, bool Table[n][n]) { _Proposal Prop; for (int i = 0; i < indices.size(); i++) if (Table[indices[i]][index]) Prop.indices.push_back(indices[i]); If(Prop.IsIndexPresent(index) == false) Prop.indices.push_back(index); Return Prop; } Bool operator== (_Proposal &p) { if (indices.size() != p.indices.size()) return false; for (int i = 0; i < indices.size(); i++) if (indices[i] != p.indices[i]) Return false; Return true; } _Proposal &operator= (_Proposal &p) { indices.clear(); For(int i = 0; i < p.indices.size(); i++) indices.push_back(p.indices[i]); Return *this; } Void AppendIndex(int index) { indices.push_back(index); } bool IsIndexPresent(int index) { for (int i = 0; i < indices.size(); i++) if (indices[i] == index) return true; return false; } void ConditionalAssign(_Proposal &p) { if (indices.size() < p.indices.size()) *this = p; } bool CompletedATurn(int index) { if (indices.size() <= 0) return false; return indices[indices.size() - 1] == index; } }; Class _Cell { Int index; Int NextBackProposal; Vector<_proposal> BackProposals; Public: Bool valid; _Proposal proposal; _Cell() { Valid = false; NextBackProposal = 0; } Bool AgreesWith(_Proposal &p, bool Table[n][n]) { Return p.IsOk(index, Table); } Void JoinTheProposal(_Proposal &p) { if (p.IsIndexPresent(index) == false) p.AppendIndex(index); } Bool PickABackProposal() { if (NextBackProposal >= BackProposals.size()) Return false; Proposal = BackProposals[NextBackProposal++]; Return true; } void CreateBackProposal(bool Table[n][n]) { _Proposal backProp; backProp = proposal.CreateAValidProposal(index, Table); for (int i = 0; i < BackProposals.size(); i++) if (BackProposals[i] == backProp) return; BackProposals.push_back(backProp); } }; Algorithm([input] Boolean Table[n][n]) { int ElectionTimer = 0; _Cell cells[MAX][2]; _Proposal ElectedProposal; cell[n - 1][1].valid = true; cell[n - 1][1].proposal.AppendIndex(n - 1); for (int tick = 0;; tick = (tick + 1) % 2, ElectionTimer++) { for (int i = 0; i < n; i++) { cell[i][tick].valid = false; if (cell[(i + 1) % n][(tick + 1) % 2].valid == false) { Cell[i][tick].valid = cell[i][tick].PickABackProposal(); Continue; } cell[i][tick].proposal = cell[(i + 1) % n][(tick + 1) % 2].proposal; if (cell[i][tick].proposal.CompletedATurn(i)) { ElectionTimer = 0; ElectedProposal.ConditionalAssign(cell[i][tick].proposal); Cell[i][tick].valid = cell[i][tick].PickABackProposal(); continue; } if (true == cell[i][tick].AgreesWith(cell[i][tick].proposal, Table)) cell[i][tick].JoinTheProposal(cell[i][tick].proposal); else cell[i][tick].CreateBackProposal(Table); cell[i][tick].valid = true; } if (ElectionTimer > MAX_ELECTION_TIMER) break; } Return ElectedProposal; }

The typical advantages that we can gain by using this framework can be stated as:

- The first and foremost reason is that this would allow a common framework for all computational problems to operate upon and so maintenance is easy.
- We do not need to solve the new problems entirely ourselves. We can just find a way of porting them onto this framework and then can see them being solved automatically.
- We could, in course of time, establish a relationship among the problems themselves by studying the relations among the arguments that we are establishing as part of this process. After all, two instances of the same function calls could differ only in its arguments.

- Tommaso Toffoli,
*Programmable Matter Methods*, http://pm1.bu.edu/~tt/publ/pmm.pdf , Future Generation Computer Systems, June 98.

By

P.GopalaKrishna

Index.html The Page of Articles