---
_id: '1116'
abstract:
- lang: eng
  text: "Time-triggered switched networks are a deterministic communication infrastructure
    used by real-time distributed embedded systems. Due to the criticality of the
    applications running over them, developers need to ensure that end-to-end communication
    is dependable and predictable. Traditional approaches assume static networks that
    are not flexible to changes caused by reconfigurations or, more importantly, faults,
    which are dealt with in the application using redundancy. We adopt the concept
    of handling faults in the switches from non-real-time networks while maintaining
    the required predictability. \r\n\r\nWe study a class of forwarding schemes that
    can handle various types of failures. We consider probabilistic failures. We study
    a class of forwarding schemes that can handle various types of failures. We consider
    probabilistic failures. For a given network with a forwarding scheme and a constant
    ℓ, we compute the {\\em score} of the scheme, namely the probability (induced
    by faults) that at least ℓ messages arrive on time. We reduce the scoring problem
    to a reachability problem on a Markov chain with a &quot;product-like&quot; structure.
    Its special structure allows us to reason about it symbolically, and reduce the
    scoring problem to #SAT. Our solution is generic and can be adapted to different
    networks and other contexts. Also, we show the computational complexity of the
    scoring problem is #P-complete, and we study methods to estimate the score. We
    evaluate the effectiveness of our techniques with an implementation. "
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Shubham
  full_name: Goel, Shubham
  last_name: Goel
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Guillermo
  full_name: Rodríguez Navas, Guillermo
  last_name: Rodríguez Navas
citation:
  ama: 'Avni G, Goel S, Henzinger TA, Rodríguez Navas G. Computing scores of forwarding
    schemes in switched networks with probabilistic faults. In: Vol 10206. Springer;
    2017:169-187. doi:<a href="https://doi.org/10.1007/978-3-662-54580-5_10">10.1007/978-3-662-54580-5_10</a>'
  apa: 'Avni, G., Goel, S., Henzinger, T. A., &#38; Rodríguez Navas, G. (2017). Computing
    scores of forwarding schemes in switched networks with probabilistic faults (Vol.
    10206, pp. 169–187). Presented at the TACAS: Tools and Algorithms for the Construction
    and Analysis of Systems, Uppsala, Sweden: Springer. <a href="https://doi.org/10.1007/978-3-662-54580-5_10">https://doi.org/10.1007/978-3-662-54580-5_10</a>'
  chicago: Avni, Guy, Shubham Goel, Thomas A Henzinger, and Guillermo Rodríguez Navas.
    “Computing Scores of Forwarding Schemes in Switched Networks with Probabilistic
    Faults,” 10206:169–87. Springer, 2017. <a href="https://doi.org/10.1007/978-3-662-54580-5_10">https://doi.org/10.1007/978-3-662-54580-5_10</a>.
  ieee: 'G. Avni, S. Goel, T. A. Henzinger, and G. Rodríguez Navas, “Computing scores
    of forwarding schemes in switched networks with probabilistic faults,” presented
    at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems,
    Uppsala, Sweden, 2017, vol. 10206, pp. 169–187.'
  ista: 'Avni G, Goel S, Henzinger TA, Rodríguez Navas G. 2017. Computing scores of
    forwarding schemes in switched networks with probabilistic faults. TACAS: Tools
    and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10206,
    169–187.'
  mla: Avni, Guy, et al. <i>Computing Scores of Forwarding Schemes in Switched Networks
    with Probabilistic Faults</i>. Vol. 10206, Springer, 2017, pp. 169–87, doi:<a
    href="https://doi.org/10.1007/978-3-662-54580-5_10">10.1007/978-3-662-54580-5_10</a>.
  short: G. Avni, S. Goel, T.A. Henzinger, G. Rodríguez Navas, in:, Springer, 2017,
    pp. 169–187.
conference:
  end_date: 2017-04-29
  location: Uppsala, Sweden
  name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
  start_date: 2017-04-22
corr_author: '1'
date_created: 2018-12-11T11:50:14Z
date_published: 2017-03-31T00:00:00Z
date_updated: 2026-04-16T09:56:24Z
day: '31'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-662-54580-5_10
external_id:
  isi:
  - '000440733400010'
file:
- access_level: open_access
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:08:37Z
  date_updated: 2018-12-12T10:08:37Z
  file_id: '4698'
  file_name: IST-2017-758-v1+1_tacas-cr.pdf
  file_size: 321800
  relation: main_file
file_date_updated: 2018-12-12T10:08:37Z
fulldoi: https://doi.org/10.1007/978-3-662-54580-5_10
has_accepted_license: '1'
intvolume: '     10206'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 169 - 187
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Moderne Concurrency Paradigms
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: Formal methods for the design and analysis of complex systems
publication_identifier:
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
publist_id: '6246'
pubrep_id: '758'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing scores of forwarding schemes in switched networks with probabilistic
  faults
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 10206
year: '2017'
...
