Cellection Framework

Contents:

Download the Source Code from The Page of Downloads

Introduction:

What is cellection framework?

Cellection framework is a way of programing the programmable 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 a proposal as 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.

The 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;
}

Conclusion:

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

1. 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.
2. 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.
3. 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.

References:

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

By   

P.GopalaKrishna

[email protected]

Index.html    The Page of Articles