Parallel and distributed incremental attribute evaluation algorithms for multiuser software development environments

• Published in: ACM transactions on software engineering and methodology 1993-01, Vol.2 (1), p.47-92
• Main Authors: Kaiser, Gail E., Kaplan, Simon M.
• Format: Article
• Language: English
• Subjects: Computing methodologies; Concurrent computing methodologies; Concurrent programming languages; Designing software; Development frameworks and environments; Formal language definitions; General programming languages; Language features; Language types; Modules / packages; Program semantics; Semantics; Semantics and reasoning; Software and its engineering; Software creation and management; Software design techniques; Software development methods; Software development process management; Software implementation planning; Software notations and tools; Theory of computation
• ISSN: 1049-331X; 1557-7392
• DOI: 10.1145/151299.151312

The problem of change propagation in multiuser software development environments distributed across a local-area network is addressed. The program is modeled as an attributed parse tree segmented among multiple user processes and changes are modeled as subtree replacements requested asynchronously by individual users. Change propagation is then implemented using decentralized incremental evaluation of an attribute grammar that defines the static semantic properties of the programming language. Building up to our primary result, we first present algorithms that support parallel evaluation on a centralized tree in response to single edits using a singe editing cursor and multiple edits with multiple editing cursors. Then we present our algorithm for parallel evaluation on a decentralized tree. We also present a protocol to guarantee reliability of the evaluation algorithm as components of the decentralized tree become unavailable due to failures and return to availability.