NDLI: A model for distributed systems based on graph rewriting

Content Provider	ACM Digital Library
Author	Degano, Pierpaolo Montanari, Ugo
Copyright Year	1987
Abstract	In our model, a graph describes a net of processes communicating through ports and, at the same time, its computation history consisting of a partial ordering of events. Stand-alone evolution of processes is specified by context-free productions. From productions and a basic synchronization mechanism, a set of context-sensitive rewriting rules that models the evolution of processes connected to the same ports can be derived. A computation is a sequence of graphs obtained by successive rewritings. The result of a finite computation is its last graph, whereas the result of an infinite computation is the limit, infinite graph defined through a completion technique based on metric spaces. A result characterizes a concurrent computation, since it abstracts from any particular interleaving of concurrent events, while in the meantime providing information about termination, partial or complete deadlocks, and fairness. Not every result is acceptable, however, but only the computations that produce a result no longer rewritable are successful. Infinite successful computations are shown to coincide with weakly fair computations, and a scheduler yielding all and only such computations is defined.
Starting Page	411
Ending Page	449
Page Count	39
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/23005.24038
Journal	Journal of the ACM (JACM)
Volume Number	34
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Graph Structures

Eavesdropping games: a graph-theoretic approach to privacy in distributed systems

Distributed bisimulations

A methodology for hardware verification based on logic simulation

Graph Problems on a Mesh-Connected Processor Array

An algebraic theory of graph reduction

On the Church-Rosser property for the direct sum of term rewriting systems

An Efficient Algorithm for Graph Isomorphism

Graph Algorithms for Functional Dependency Manipulation

A model for distributed systems based on graph rewriting

Similar Documents

Graph Structures

Eavesdropping games: a graph-theoretic approach to privacy in distributed systems

Distributed bisimulations

A methodology for hardware verification based on logic simulation

Graph Problems on a Mesh-Connected Processor Array

An algebraic theory of graph reduction

On the Church-Rosser property for the direct sum of term rewriting systems

An Efficient Algorithm for Graph Isomorphism

Graph Algorithms for Functional Dependency Manipulation

A model for distributed systems based on graph rewriting