<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T00:14:23Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/9596" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/9596</identifier><datestamp>2017-03-21T15:11:03Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="2c15fdb3-b615-417b-bb04-982cbbb325a1" confidence="600">Aflaki, Saba</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-08-26T16:13:51Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2015-08-26T16:13:51Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-08-26</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2015-08-17</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/9596</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Self-stabilization [2] is a versatile technique for recovery from erroneous behavior due to transient&#xd;
faults or wrong initialization. A system is self-stabilizing if (1) starting from an arbitrary&#xd;
initial state it can automatically reach a set of legitimate states in a finite number of steps and (2)&#xd;
it remains in legitimate states in the absence of faults. Weak-stabilization [3] and probabilistic-stabilization&#xd;
[4] were later introduced in the literature to deal with resource consumption of&#xd;
self-stabilizing algorithms and impossibility results. Since the system perturbed by fault may&#xd;
deviate from correct behavior for a finite amount of time, it is paramount to minimize this time&#xd;
as much as possible, especially in the domain of robotics and networking. This type of fault&#xd;
tolerance is called non-masking because the faulty behavior is not completely masked from the&#xd;
user [1].&#xd;
Designing correct stabilizing algorithms can be tedious. Designing such algorithms that&#xd;
satisfy certain average recovery time constraints (e.g., for performance guarantees) adds further&#xd;
complications to this process. Therefore, developing an automatic technique that takes as input&#xd;
the specification of the desired system, and synthesizes as output a stabilizing algorithm with&#xd;
minimum (or other upper bound) average recovery time is useful and challenging. In this thesis,&#xd;
our main focus is on designing automated techniques to optimize the average recovery time of&#xd;
stabilizing systems using model checking and synthesis techniques.&#xd;
First, we prove that synthesizing weak-stabilizing distributed programs from scratch and repairing&#xd;
stabilizing algorithms with average recovery time constraints are NP-complete in the&#xd;
state-space of the program. To cope with this complexity, we propose a polynomial-time heuristic&#xd;
that compared to existing stabilizing algorithms, provides lower average recovery time for&#xd;
many of our case studies.&#xd;
Second, we study the problem of fine tuning of probabilistic-stabilizing systems to improve&#xd;
their performance. We take advantage of the two properties of self-stabilizing algorithms to&#xd;
model them as absorbing discrete-time Markov chains. This will reduce the computation of&#xd;
average recovery time to finding the weighted sum of elements in the inverse of a matrix.&#xd;
Finally, we study the impact of scheduling policies on recovery time of stabilizing systems.&#xd;
We, in particular, propose a method to augment self-stabilizing programs with k-central and k-bounded&#xd;
schedulers to study dierent factors, such as geographical distance of processes and the&#xd;
achievable level of parallelism.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Automated Analysis and Optimization of Distributed Self-Stabilizing Algorithms</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Computer Science (David R. Cheriton School of)</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>