Unbounded Nondeterminism - Hewitt's Analysis of Fairness

Hewitt's Analysis of Fairness

Hewitt argued that issues in fairness derive in part from the global state point of view. The oldest models of computation (e.g.. Turing machines, Post productions, the lambda calculus, etc.) are based on mathematics that makes use of a global state to represent a computational step. Each computational step is from one global state of the computation to the next global state. The global state approach was continued in automata theory for finite state machines and push down stack machines including their nondeterministic versions. All of these models have the property of bounded nondeterminism: if a machine always halts when started in its initial state, then there is a bound on the number of states in which it can halt.

Hewitt argued that there is a fundamental difference between choices in global state nondeterminism and the arrival order indeterminacy (nondeterminism) of his Actor model. In global state nondeterminism, a "choice" is made for the "next" global state. In arrival order indeterminacy, arbitration locally decides each arrival order in an unbounded amount of time. While a local arbitration is proceeding, unbounded activity can take place elsewhere. There is no global state and consequently no "choice" to be made as to the "next" global state.

Read more about this topic:  Unbounded Nondeterminism

Famous quotes containing the words hewitt, analysis and/or fairness:

    “The decision to have a child is both a private and a public decision, for children are our collective future.”
    —Sylvia Ann Hewitt (20th century)

    “Whatever else American thinkers do, they psychologize, often brilliantly. The trouble is that psychology only takes us so far. The new interest in families has its merits, but it will have done us all a disservice if it turns us away from public issues to private matters. A vision of things that has no room for the inner life is bankrupt, but a psychology without social analysis or politics is both powerless and very lonely.”
    —Joseph Featherstone (20th century)

    “These men ask for just the same thing—fairness, and fairness only. This, so far as in my power, they, and all others, shall have.”
    —Abraham Lincoln (1809–1865)