eCommons

 

Symmetry in Distributed Systems

Other Titles

Abstract

A distributed computing system can be considered to be symmetric because of its topology or because of its behavior. Unfortunately, these different definitions can categorize the same system differently. The choice of definition becomes important when one is trying to prove that certain problems, such as the Dining Philosophers problem, cannot be solved on symmetric distributed computing systems. Since the behavioral definitions are based on the possible patterns of computation, it is much easier to use them for these proofs. However, behavioral definitions admit straightforward decision procedures. This thesis presents a new definition for symmetry, called similarity, that, while based on behavior of processes, is decidable given the initial configuration of the system. The decision procedure for similarity depends partly on the model of computation being used, but a way to discover these decision procedures is given and is used to find decision procedures for a wide range of models of distributed computation. Distributed versions of these decision procedures form the basis of solutions to the problem of selecting a process as the leader. The thesis also shows how to use similarity to compare the relative power of different models of computation, including models with shared variables with and without locking, models using synchronous and asynchronous message-passing, models making different assumptions about fairness, and models based on probabilistic techniques.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1987-08

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-855

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record