Semi-local Model of Computations on Graphs to Break the Local Symmetry | Zendy

Dobiesław Wróblewski | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Semi-local Model of Computations on Graphs to Break the Local Symmetry

Author(s) -

Dobiesław Wróblewski

Publication year - 2006

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.03.036

Subject(s) - computation , local symmetry , computer science , graph , security token , extension (predicate logic) , undirected graph , theoretical computer science , symmetry (geometry) , leader election , mathematics , discrete mathematics , algorithm , physics , geometry , computer security , quantum mechanics , programming language

We consider finite connected undirected graphs without self-loops as a model of computer networks. The nodes of the graph represent computers or processors, while the edges of the graph correspond to the links between them. We present a model of distributed computations, called semi-local. This extension of the classical local model breaks the local symmetry. As a result, many useful tasks become deterministically solvable in every network assuming a very small initial knowledge about its graph representation. One of these tasks is a creation of a token in an arbitrary anonymous ring – an example of election of a leader. A semi-local solution to this problem is presented

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research