CaltechTHESIS
  A Caltech Library Service

Applying formal methods to distributed algorithms using local-global relations

Citation

White, Jerome (2011) Applying formal methods to distributed algorithms using local-global relations. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:05312011-123940546

Abstract

This thesis deals with the design and analysis of distributed systems in which homogeneous, autonomous agents collaborate to achieve a common goal. The class of problems studied includes consensus algorithms in which all agents eventually come to an agreement about a specific action. The thesis proposes a framework, called local-global, for analyzing these systems. A local interaction is an interaction among subsets of agents, while a global interaction is one among all agents in the system. Global interactions, in practice, are rare, yet they are the basis by which correctness of a system is measured. For example, if the problem is to compute the average of a measurement made separately by each agent, and all the agents in the system could exchange values in a single action, then the solution is straightforward: each agent gets the values of all others and computes the average independently. However, if the system consists of a large number of agents with unreliable communication, this scenario is highly unlikely. Thus, the design challenge is to ensure that sequences of local interactions lead, or converge, to the same state as a global interaction.

The local-global framework addresses this challenge by describing each local interaction as if were a global one, encompassing all agents within the system. This thesis outlines the concept in detail, using it to design algorithms, prove their correctness, and ultimately develop executable implementations that are reliable. To this end, the tools of formal methods are employed: algorithms are modeled, and mechanically checked, within the PVS theorem prover; programs are also verified using the Spin model checker; and interface specification languages are used to ensure local-global properties are still maintained within Java and C# implementations. The thesis presents example applications of the framework and discusses a class of problems to which the framework can be applied.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:local-global relations; distributed systems; formal methods
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Chandy, K. Mani
Thesis Committee:
  • Murray, Richard M. (chair)
  • Doyle, John Comstock
  • Martin, Alain J.
  • Holzmann, Gerard J.
  • Chandy, K. Mani
Defense Date:6 December 2010
Record Number:CaltechTHESIS:05312011-123940546
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:05312011-123940546
Related URLs:
URLURL TypeDescription
http://www.infospheres.caltech.edu/OrganizationUNSPECIFIED
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6481
Collection:CaltechTHESIS
Deposited By: Jerome White
Deposited On:06 Jun 2011 23:35
Last Modified:26 Dec 2012 04:36

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

1412Kb

Repository Staff Only: item control page