language: en

Bounds on the Time to Detect Failures Using Bounded-capacity Message Links

Stephen Ponzio *
MIT Laboratory for Computer Science

Abstract We consider a system of distributed processors that communicate by passing messages and that have inexact information about time. Specifically, a processor knows that a single message is delayed by at most time d and the time between any two of its consecutive steps is at least c 1 and at most c 2 ; it has no other way of estimating elapsed time. This simple model is very close to traditional models used in distributed computing theory, and has been studied by Attiya and Lynch [2, 1] among others. We extend the model by making a realistic assumption about how the delay of messages is affected by the rate at which they are sent. We define a model of message links with bounded capacity, which are guaranteed to deliver messages at only a given rate. If a processor sends messages at a greater rate, they may incur greater delay. We quantify the effect of this bounded capacity on the time necessary to detect processor failures. We consider a system of two processors connected by a bi-directional message link of (integral) capacity . First we give two very simple protocols that guarantee any stopping failure will be detected within time 2Cd + d and C 2 d= + Cd + d respectively, where C = c 2 =c 1 . The main result is an almost-matching lower bound of 2Cd+d= or C 2 d=+Cd+d, whichever is less. If the link is uni-directional, our result specializes to give a matching upper and lower bound of C 2 d= + Cd + d.

[Supported by an NSF Graduate Fellowship]

1 Introduction