Author name cluster

Roberto Baldoni

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2013 Journal Article

A protocol for implementing byzantine storage in churn-prone distributed systems

Roberto Baldoni
Silvia Bonomi
Amir Soltani Nezhad

Distributed storage service is one of the main abstractions provided to the developers of distributed applications due to its capability to hide the complexity generated by the messages exchanged between processes. Many protocols have been proposed to build byzantine-fault-tolerant storage services on top of a message-passing system, but they do not consider the possibility to have servers joining and leaving the computation (churn phenomenon). This phenomenon, if not properly mastered, can either block protocols or violate the safety of the storage. In this paper, we address the problem of building a safe register storage resilient to byzantine failures in a distributed system affected from churn. A protocol implementing a safe register in an eventually synchronous system is proposed and some feasibility constraints on the arrival and departure of the processes are given. The protocol is proved to be correct under the assumption that the constraint on the churn is satisfied.

Details DOI

TCS Journal 2009 Journal Article

Investigating the existence and the regularity of Logarithmic Harary Graphs

Roberto Baldoni
Silvia Bonomi
Leonardo Querzoni
Sara Tucci Piergiovanni

This paper studies the existence and the regularity of Logarithmic Harary Graphs (LHGs). This study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in the presence of link and node failures when considering an initial arbitrary number of nodes n. Therefore, the capability to identify graph constraints that allow the construction of LHGs for the largest number of pairs ( n, k ) (where k is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. The paper presents several results in that direction. We introduce a graph constraint, namely K -PASTED-TREE, that allows the construction of a LHG for every pair ( n, k ) such that n ≥ 2 k. Secondly we present another graph constraint for LHG, namely K -DIAMOND, which is equivalent to K -PASTED-TREE in terms of capability to construct LHGs for any pair ( n, k ). The interest of K -DIAMOND lies in the fact that, for a given k, K -DIAMOND allows us to construct more regular graphs than K -PASTED-TREE does. A k -regular graph shows the minimal number of links required by a k -connected graph, leading to minimal flooding cost. The paper formally shows, in particular, that there are an infinite number of pairs ( n, k ), such that there exists a k -regular LHG for the pair ( n, k ) that satisfies K -DIAMOND and does not satisfy K -PASTED-TREE.

Details DOI

I&C Journal 2001 Journal Article

Rollback-Dependency Trackability: A Minimal Characterization and Its Protocol

Roberto Baldoni
Jean-Michel Hélary
Michel Raynal

Considering a checkpoint and communication pattern, the rollback-dependency trackability (RDT) property stipulates that there is no hidden dependency between local checkpoints. In other words, if there is a dependency between two checkpoints due to a noncausal sequence of messages (Z-path), then there exists a causal sequence of messages (C-path) that doubles the noncausal one and that establishes the same dependency. This paper introduces the notion of RDT-compliance. A property defined on Z-paths is RDT-compliant if the causal doubling of Z-paths having this property is sufficient to ensure RDT. Based on this notion, the paper provides examples of such properties. Moreover, these properties are visible, i. e. , they can be tested on the fly. One of these properties is shown to be minimal with respect to visible and RDT-compliant properties. In other words, this property defines a minimal visible set of Z-paths that have to be doubled for the RDT property to be satisfied. Then, a family of communication-induced checkpointing protocols that ensure on-the-fly RDT properties is considered. Assuming processes take local checkpoints independently (called basic checkpoints), protocols of this family direct them to take on-the-fly additional local checkpoints (called forced checkpoints) in order that the resulting checkpoint and communication pattern satisfies the RDT property. The second contribution of this paper is a new communication-induced checkpointing protocol P. This protocol, based on a condition derived from the previous characterization, tracks a minimal set of Z-paths and breaks those not perceived as being doubled. Finally, a set of communication-induced checkpointing protocols are derived from P. Each of these derivations considers a particular weakening of the general condition used by P. It is interesting to note that some of these derivations produce communication-induced checkpointing protocols that have already been proposed in the literature.

Details DOI

TCS Journal 1998 Journal Article

k-Arbiter: A safe and general scheme for h-out of-k mutual exclusion

Yoshifumi Manabe
Roberto Baldoni
Michel Raynal
Shigemi Aoyagi

Mutual exclusion is a well-known problem that arises when multiple processes compete, in an uncoordinated way, for the acquisition of shared resources over a distributed system. In particular, k-mutual exclusion allows at most k processes to get one unit of the same resource simultaneously. These paradigms do not cover all the cases in which resource accesses must be serialized over a distributed system. There exist cases (e. g. the bandwidth of communication lines) where the amount of shared resource might differ from request to request (for example, audio and video communications). In this paper, we formalize this problem as the h-out of-k mutual exclusion problem, in which each request concerns some number h (1 ⩽ h ⩽ k) of units of shared resource and no unit is allocated to multiple processes at the same time. Former simple and k-mutual algorithms cannot be used to solve this problem. We present a general scheme for a quorum-based h-out of-k mutual exclusion algorithm that relies on a collection of quorums called k-arbiter. Several examples of k-arbiters are discussed, two particular classes of k-arbiters are investigated and a metric to evaluate the resiliency with respect to failures of k-arbiters is also given.

Details DOI