• Decentralized spatial computing

    A distributed system is conventionally defined as a set of:

    multiple information systems that cooperate synchronously in order to complete some computing task — Worboys and Duckham, 2004

    A decentralized system is a special case of a distributed system where:

    no single component knows the entire system state — Lynch 1996

    Decentralization plays a pivotal role in computing somewhere because the constraints to movement of information make it undesirable to collate and centralize information about the entire system state. Instead, individual components of a decentralized system must be able to filter and process information locally accessible to them.

    Thus, decentralized spatial computing can be defined as:

    the study of the decentralized algorithms, data structures, and techniques for computing with spatial information.

    Crowd computing!

    "Crowd!” computing: individuals can cooperate to compute whether a “crowd” of more than 1000 people exists.

    As a very simple example of a decentralized spatial algorithm, imagine the question of whether people at a soccer match constitute a “crowd” (for the sake of argument, 1000 people). We might centrally collect data about the soccer fans (for example, an observer with a camera could take a picture, and then count the people in the picture). However, a decentralized approach would involve the people themselves. An individual fan could start by placing a tally mark on a piece of paper. She can then pass this paper to a randomly selected neighbor, and ask them to add another tally. The paper then continues to be passed to neighbors subject to three rules:

    1. please add a tally to the paper only if you have not already done so;
    2. check the tally to see if it contains 1,000 tally marks;
    3. if it does, shout out “Crowd!”; if not, just pass the paper to another randomly selected neighbor.

    Assuming the individuals in the crowd do as they are instructed, and if the crowd is large enough, sooner or later someone will shout “Crowd!”

    The algorithm is decentralized because there is no single person you can point to who is controlling the procedure (although the individual who starts the process does play a special role). Further, although this algorithm does not involve coordinate positions, it does rely on the spatial constraints to movement of information—in this case the physical limitations of handing a neighbor a piece of paper. These spatial constraints are fundamental to the generation of a sensible answer; if we break these constraints (for example by emailing the message to a random address book “neighbor”), the computation no longer operates correctly.