A self-stabilizing randomized algorithm for mending maximal matching (MM) in synchronous networks is presented. Starting from a legal MM configuration and assuming that the network undergoes k faults or topology changes (that may occur in multiple batches), the algorithm is guaranteed to stabilize back to a legal MM configuration in time O(log k) in expectation and with high probability (in k), using constant size messages. The algorithm is simple to implement and is uniform in the sense that it does not assume unique identifiers, nor does it assume any global knowledge of the communication graph including its size. It relies on a generic probabilistic phase synchronization technique that may be useful for other self-stabilizing problems. The algorithm compares favorably with the existing self-stabilizing MM algorithms in terms of the dependence of its run-time on k, a.k.a. fully adaptive run-time. In fact, this dependence is asymptotically optimal for uniform algorithms that use constant size messages.

A new spanner construction algorithm is presented, working under the LOCAL model assuming unique edge IDs. Given an n-node communication graph, a spanner with a constant stretch and Õ(n1 + c) edges (for any small constant c > 0) is constructed efficiently --- i.e., in a constant number of rounds and a message complexity of Õ (n1 + 2c) whp.

A new \emph{spanner} construction algorithm is presented, working under the \emph{LOCAL} model with unique edge IDs. Given an $n$-node communication graph, a spanner with a constant stretch and $O (n^{1 + \varepsilon})$ edges (for an arbitrarily small constant $\varepsilon > 0$) is constructed in a constant number of rounds sending $O (n^{1 + \varepsilon})$ messages whp. Consequently, we conclude that every $t$-round LOCAL algorithm can be transformed into an $O (t)$-round LOCAL algorithm that sends $O (t \cdot n^{1 + \varepsilon})$ messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a $\log^{Ω(1)} n$ blow-up of the round complexity.

This study was carried in the context of the development of technologies for a cloud that uses an optical network for internal communication. The problem addressed in this paper deals with dispatching jobs - units of work, to be performed by machines on the cloud. Sending (or migrating) a job to a machine involves establishing a lightpath (a la circuit switching); this incurs a significant setup cost, but while it exists, the lightpath's capacity is very high. Hence, moving one job is about as expensive as moving a set of jobs over the same lightpath. Our goal is to develop online network dispatching algorithms for a work conserving job scheduling. That is, consider a set of jobs the dispatcher is responsible for their executions on some set SM of machines. Any machine in the network may join or (when not executing a job) leave SM according to decisions made outside the scope of this paper. Whenever a machine joins the set or is in the set and has just finished executing a job, it issues a request for a new job to perform and the dispatcher must send this machine a job that has not been executed yet (if such exists). Every machine can perform any of the jobs, and each job is performed on a single machine. The main algorithmic challenge in this context boils down to the following questions: How many jobs should we send to a requesting machine (or to some intermediate storage to be distributed from there)? From the storage on which machine should these jobs be taken? The algorithms developed here are shown to be efficient in reducing the costs of establishing lightpaths. As opposed to related algorithms for delivering consumable resources (in other contexts), we prove that our online algorithms are fully competitive. We present randomized online algorithms for two different settings: in the first it is assumed that each message requires establishing a lightpath and thus, incurs a setup cost; in the second, we distinguish between messages that carry job sets and small control messages sent by the algorithm, where the latter type of messages is assumed to be sent over a designated (non-optical) control plane at a negligible cost. Our algorithms are quite simple, though the analysis turns out to be rather involved. They are designed (and rigorously analyzed) for a general architecture, but would be especially efficient in fat tree architectures - the common choice in many data centers.