text: A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. This paper introduces several classes of distributed decision problems, proves separation among them and presents some complete problems. More specifically, we consider the standard LOCAL model of computation and define LD (for local decision) as the class of decision problems that can be solved in constant number of communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD, and ask whether LD=BPLD. We provide a partial answer to this question by showing that in many cases, randomization does not help for deciding hereditary languages. In addition, we define the notion of local many-one reductions, and introduce the (nondeterministic) class NLD of decision problems for which there exists a certificate that can be verified in constant number of communication rounds. We prove that there exists an NLD-complete problem. We also show that there exist problems not in NLD. On the other hand, we prove that the class NLD#n, which is NLD assuming that each processor can access an oracle that provides the number of nodes in the network, contains all (decidable) languages. For this class we provide a natural complete problem as well.
  @cite_18: A stabilizing algorithm is silent if starting from an arbitrary state it converges to a global state after which the values stored in the communication registers are fixed. Many silent stabilizing algorithms have appeared in the literature. In this paper we show that there cannot exist constant memory silent stabilizing algorithms for finding the centers of a graph, electing a leader, and constructing a spanning tree. We demonstrate a lower bound of Ω(log n) bits per communication register for each of the above tasks.
  @cite_36: 
  @cite_5: The first self-stabilizing end-to-end communication protocol and the most efficient known self-stabilizing network reset protocol are introduced. A simple method of local checking and correction, by which distributed protocols can be made self-stabilizing without the use of unbounded counters, is used. The self-stabilization model distinguishes between catastrophic faults that abstract arbitrary corruption of global state, and other restricted kinds of anticipated faults. It is assumed that after the execution starts there are no further catastrophic faults, but the anticipated faults may continue to occur. >
  @cite_15: This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as “how expensive is local verification?” and more specifically, “how expensive is local verification compared to computation?” A suitable model is introduced in which these questions are studied in terms of the number of bits a vertex needs to communicate. The model includes the definition of a proof labeling scheme (a pair of algorithms- one to assign the labels, and one to use them to verify that the global property holds). In addition, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the bit complexity of schemes for multiple basic problems. The paper also studies the role and cost of unique identities in terms of impossibility and complexity, in the context of proof labeling schemes. Previous studies on related questions deal with distributed algorithms that simultaneously compute a configuration and verify that this configuration has a certain desired property. It turns out that this combined approach enables the verification to be less costly sometimes, since the configuration is typically generated so as to be easily verifiable. In contrast, our approach separates the configuration design from the verification. That is, it first generates the desired configuration without bothering with the need to verify it, and then handles the task of constructing a suitable verification scheme. Our approach thus allows for a more modular design of algorithms, and has the potential to aid in verifying properties even when the original design of the structures for maintaining them was done without verification in mind.
  @cite_25: Abstract A new paradigm for the design of self-stabilizing distributed algorithms, called local detection , is introduced. The essence of the paradigm is in defining a local condition based on the state of a processor and its immediate neighborhood such that the system is in a globally legal state if and only if the local condition is satisfied at all the nodes. In this work we also extend the model of self-stabilizing networks traditionally assuming memory failure to include the model of dynamic networks (assuming edge failures and recoveries). We apply the paradigm to the extended model which we call “dynamic self-stabilizing networks”. Without loss of generality, we present the results in the least restrictive shared memory model of read write atomicity, to which end we construct basic information transfer primitives. Using local detection, we develop deterministic and randomized self-stabilizing algorithms that maintain a rooted spanning tree in a general network whose topology changes dynamically. The deterministic algorithm assumes unique identities while the randomized assumes an anonymous network. The algorithms use a constant number of memory words per edge in each node; and both the size of memory words and of messages is the number of bits necessary to represent a node identity (typically O (log n ) bits where n is the size of the network). These algorithms provide for the easy construction of self-stabilizing protocols for numerous tasks: reset, routing, topology-update and self-stabilization transformers that automatically self-stabilize existing protocols for which local detection conditions can be defined.
  @cite_17: 
summary: The theory of @cite_17 @cite_15 was designed to tackle the issue of locally verifying (with the aid of a proof , i.e., a certificate, at each node) solutions to problems that cannot be decided locally (e.g., is the given subgraph a spanning tree of the network?'', or, is it an MST?''). In fact, the model of proof-labeling schemes has some resemblance to our definition of the class @math . Investigations in the framework of proof-labeling schemes mostly focus on the minimum size of the certificate necessary so that verification can be performed in a single round. The notion of proof-labeling schemes also has interesting similarities with the notions of local detection @cite_25 , local checking @cite_5 , or silent stabilization @cite_18 , which were introduced in the context of self-stabilization @cite_36 .