LUNCHBUNCH! Grad Student Presentations

Fault-Localization in Distributed Resource Allocation

Scott M. Pike
OSU Graduate Student

Thurs., Mar. 11th
11:30am; 480 Dreese Labs
All interested parties are invited.
Pizza lunch will be served.

Ideally, faults should be isolated within small, local neighborhoods
of impact. Failure locality measures this impact as the radius of the
largest set of processes disrupted by a given fault. The locality
radius of a distributed algorithm demarcates a halo beyond which
faults are masked. As such, fault-local algorithms are central to
engineering survivable distributed systems, because they protect
against cascading and epidemic failures.

We present practical and theoretical results on fault-localization for
distributed resource allocation. Specifically, we address the locality
of generalized dining philosophers, subject to crash failures. The
optimal crash locality for synchronous dining is 0, but this metric
degrades to 2 for asynchronous dining. We resolve the apparent
complexity gap by constructing the first known dining algorithms
to achieve crash locality 1 under partial synchrony.

Our approach is based on augmenting existing dining algorithms with
unreliable failure detectors. We extend our results by characterizing
optimal locality bounds for every failure detector in the Chandra-Toueg
hierarchy with respect to four practical models of mutual exclusion.
Our analysis of the resulting lattice identifies the weakest detector
for solving each dining problem, and discovers two points of
discontinuity indicating unresolved complexity gaps.
~~~~~~~
Scott Pike is a Doctoral Candidate in Computer Science & Engineering
at Ohio State University. He received his M.S. in Computer Science
from Ohio State in 2000, and his B.A. in Philosophy from Yale
University in 1996. His research interests focus on software
engineering and distributed computing, and, more concretely, on
scalable approaches to building agile, adaptive, and survivable
components for distributed systems.