Aigaion: RACTI / RU1 Technical Report Series (Web Based)

[RACTI-RU1-2004-64] Galdi, C. and Giordano, R., Certified E-Mail with Temporal Authentication: An Improved Optimistic Protocol, in: Trust and Privacy in Digital Business, pages 181-190, Springer Berlin / Heidelberg, 2004. [DOI]
Abstract: In this paper we present a protocol for Certified E-Mail that ensures temporal authentication. We first slightly modify a previously known three-message optimistic protocol in order to obtain a building block that meets some properties. We then extend this basic protocol enhancing it with the temporal authentication by adding a single message, improving the message complexity of known protocols. The fairness of the protocol is ensured by an off-line Trusted third party that joins the protocol only in case one of the players misbehaves. In order to guarantee temporal authentication we assume the existance of an on-line time stamping server.
[RACTI-RU1-2006-75] Mavronicolas, Marios, Michael, Loizos and Spirakis, Paul, Computing on a Partially Eponymous Ring, in: Principles of Distributed Systems (OPODIS 2006), pages 595-613, 2006.
Abstract: We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all identical (as in the anonymous model) nor necessarily unique (as in the eponymous model). In a decision problem formalized as a relation, processors receive inputs and seek to reach outputs respecting the relation. We focus on the partially eponymous ring, and we shall consider the computation of circularly symmetric relations on it. We consider sets of rings where all rings in the set have the same multiset of identity multiplicities. We distinguish between solvability and computability: in solvability, processors are required to always reach outputs respecting the relation; in computability, they must do so whenever this is possible, and must otherwise report impossibility. We present a topological characterization of solvability for a relation on a set of rings, which can be expressed as an efficiently checkable, number-theoretic predicate. We present a universal distributed algorithm for computing a relation on a set of rings; it runs any distributed algorithm for constructing views, followed by local steps. We derive, as our main result, a universal upper bound on the message complexity to compute a relation on a set of rings; this bound demonstrates a graceful degradation with the Least Minimum Base, a parameter indicating the degree of least possible eponymity for a set of rings. Thereafter, we identify two cases where a relation can be computed on a set of rings, with rings of size n, with an efficient number of O .n lg n/ messages.