Fault-tolerant distributed cyber-physical systems: two case studies

Johnson, Taylor

Permalink

https://hdl.handle.net/2142/16191 Copy

Description

Title

Fault-tolerant distributed cyber-physical systems: two case studies

Author(s)

Johnson, Taylor

Issue Date

2010-05-19T18:40:12Z

Director of Research (if dissertation) or Advisor (if thesis)

Mitra, Sayan

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• fault-tolerance
• Distributed cyber-physical systems (DCPS)
• Cyber-physical systems (CPS)
• distributed systems
• distributed computing systems
• self-stabilization
• failure detector
• dynamical systems

Abstract

Fault-tolerance in distributed computing systems has been investigated extensively in the literature and has a rich history and detailed theory. This thesis studies fault-tolerance for distributed cyber-physical systems (DCPS), where distributed computation is combined with dynamics of physical processes. Due to their interaction with the physical world, DCPS may suffer from failures that are qualitatively different from the types of failures studied in distributed computing. Failures of the components of DCPS which interact with the physical processes---such as actuators and sensors---must be considered. Failures in the cyber domain may interact with failures of sensors and actuators in adverse ways. This thesis takes a first step in analyzing fault-tolerance in DCPS through the presentation of two case studies. In each case study, the DCPS are modeled as distributed algorithms executed by a set of agents, where each agent acts independently based on information obtained from its communication neighbors and agents may suffer from various failures. The first case study is a distributed traffic control problem, where agents control regions of roadway to move vehicles toward a destination, in spite of some agents' computers crashing permanently. The second case study is a distributed flocking problem, where agents form a flock, or a roughly equally spaced distribution in one dimension, and move towards a destination, in spite of some agents' actuators becoming stuck at some value. Each algorithm incorporates self-stabilization in order to solve the problem in spite of failures. The traffic algorithm uses a local signaling mechanism to guarantee safety and a self-stabilizing routing protocol to guarantee progress. The flocking algorithm uses a failure detector combined with an additional control strategy to ensure safety and progress.

Graduation Semester

2010-5

Permalink

http://hdl.handle.net/2142/16191

Copyright and License Information

Copyright 2010 Taylor T. Johnson

Owning Collections