Publications

Moreno CB, Moura F.  1998.  Improving causality logging in mobile computing networks. Mobile Computing and Communications Review. 2:62–66. Abstract10.1.1.41.8136.pdf

This paper builds on previous techniques for efficient causality logging in mobile networks and presents a lighter logging mechanism. The technique is based on a particular partial order that is generated by the interleaving of events on mobile hosts that are mediated by the same support station. I. Introduction Mobile computing systems are frequently designed as a network of fixed nodes, mobile support stations (MSS), that give connectivity to a set of mobile hosts (MH) [1]. The MSSs are interconnected by a high bandwidth wire-line network where communication costs are inexpensive. In contrast, the MHs always communicate with the mediation of a hosting MSS using a low-bandwidth wireless or phone channel where costs are at issue. This class of mobile computing systems, although excluding direct communication among MHs, models a vast range of existing systems that include wireless networks of MHs bound to local cells, and nomadic MHs that bind to different MSSs as access points to a wide area network. Distributed applications that build on this class of mobile computing systems are often modeled as a set of concurrent activities distributed among different MHs. Tracking the causal relationships among these concurrent activities is a basic mechanism for the analysis and debugging of distributed applications and a step towards the design of message delivery and replica consistency policies. It is well established [7] that in a distributed system the causal dependency can be fully characterized by the use of vector clocks [7, 2, 5]. However vector clocks are very sensitive to scalability issues since the vector size is bound to the number of activities, which are here bound to the number of MHs. Clearly, a dependency tracking mechanism that is bound to the number of MSSs an.

Moreno CB, Moura F.  1994.  Concurrency annotations in C++. ACM SigPlan Notices. 29:61–67. Abstract10.1.1.41.4693.pdf

This paper describes CA/C++, Concurrency Annotations in C++, a language extension that regulates method invocations from multiple threads of execution in a shared-memory multiprocessor system. This system provides threads as an orthogonal element to the language, allowing them to travel through more than one object. Statically type-ckecked synchronous and asynchronous method invocations are supported, with return values from asynchronous invocations accessed through first class future-like objects. Method invocations are regulated with synchronization code defined in a separate class hierarchy, allowing separate definition and inheritance of synchronization mechanisms. Each method is protected by an access flag that can be switched in pre and post-actions, and by a predicate. Both must evaluate to true in order to enable a thread to animate the method code. Flags and method predicates are independently redefinable along the inheritance chain, thus avoiding the inheritance anomaly.

Gonçalves R, Almeida PS, Moreno CB, Fonte V, Preguiça N.  2012.  Dotted Version Vectors: Efficient Causality Tracking for Distributed Key-Value Stores. DAIS - IFIP International Conference on Distributed Applications and Interoperable Systems.. poster_dais.pdf
Jesus P, Moreno CB, Almeida PS.  2007.  A Study on Aggregation by Averaging Algorithms. Abstractjesus-eurosys2007b.pdf

With the advent of multihop ad-hoc networks, sensor networks and large scale overlay networks, there is a demand for tools that can abstract meaningful system properties from given assemblies of nodes. Distributed aggregation algorithms allow the evaluation of properties such as: network size; total storage capacity; average load; and majorities. A useful class of aggregation algorithms is based on averaging techniques. Such algorithms start from a set of input values spread across the nodes, and iteratively average the values in neighbour nodes that are able to communicate. Eventually all nodes will converge to the same value and can estimate some useful metric. For instance, if one node starts with input 1 and all other nodes with input 0, eventually all nodes will end up with the same value and the aggregate property network size can be estimated by the fraction 1.

Moreno CB.  1996.  Indirect Calls: Remote invocations on loosely coupled systems. Abstract10.1.1.40.9706.pdf

Integration of Mobile computers into Worldwide networks is traditionally managed by hosting them into the fixed network. We argue that this approach excludes some important forms of interaction. We present a communication mechanism, suitable for developing applications that take advantage of transient connections. These communications can be supported by several transport mechanisms, including Email and plain file copying between non networked computers. 1 Introduction Future applications can be expected to follow two major trends, Mobility and Worldwideness. These two issues are strongly interrelated as Worldwide systems often experience disconnected operation under network partitions and Mobile computers are partially integrated (possibly hosted) into worldwide networks. A common scenario for the integration of mobile hosts (MHs) is based on a fixed worldwide network to which MHs connect from time to time, either by fixed or wireless links.

Moreno CB.  1995.  Synergetic state evolution under mobile computing. Abstract10.1.1.40.6574.pdf

The recent trend towards mobility and ubiquitous computing issued a new perspective over the traditional models of distributed computation. Observation of Human behavior, in particular the study of Human information interchange techniques and protocols presents a simple, yet fruitful, mean of gathering insight on the possible protocols for interaction among mobile hosts.This work will try to go one step further on the study of mobile interactions by leaving the usual semi-centralized approach to mobile computing. Instead of focusing on the reconciliation of mobile hosts with the networked support stations, we will study the possibility of progressive adjustments, both by a mobile host and a support station and between mobile hosts. 1 Introduction The recent trend towards mobility and ubiquitous computing issued a new perspective over the traditional models of distributed computation.

Almeida PS, Shoker A, Moreno CB.  2015.  Efficient State-based CRDTs by Delta-Mutation. CoRR. abs/1410.2803:1-19. Abstractdelta-tr.pdf

CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs achieve this by sharing local state changes through shipping the entire state, that is then merged to other replicas with an idempotent, associative, and commutative join operation, ensuring convergence. This imposes a large communication overhead as the state size becomes larger. We introduce Delta State Conflict-Free Replicated Datatypes ({\delta}-CRDT), which make use of {\delta}-mutators, defined in such a way to return a delta-state, typically, with a much smaller size than the full state. Delta-states are joined to the local state as well as to the remote states (after being shipped). This can achieve the best of both worlds: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. We introduce the {\delta}-CRDT framework, and we explain it through establishing a correspondence to current state- based CRDTs. In addition, we present two anti-entropy algorithms: a basic one that provides eventual convergence, and another one that ensures both convergence and causal consistency. We also introduce two {\delta}-CRDT specifications of well-known replicated datatypes.

Moreno CB, Almeida PS, Cunha A, Ferreira C.  2015.  Composition of State-based CRDTs. Abstractcrdtcompositionreport.pdf

State-based CRDTs are rooted in mathematical structures called join-semilattices (more simply lattices, in this context). These order structures ensure that the replicated states of the defined data types evolve and increase in a partial order in a sufficiently defined way, so as to ensure that all concurrent evolutions can be merged deterministically. In order to build, or understand the building principles, of state-based CRDTs it is necessary to understand the basic building blocks of the support lattices and how lattices can be composed.

Jin D, Yang B, Moreno CB, Liu D, He D, Liu J.  2013.  Markov random walk under constraint for discovering overlapping communities in complex networks. :21. Abstract1303.5675.pdf

The detection of overlapping communities in complex networks has motivated recent research in relevant fields. Aiming to address this problem, we propose a Markov-dynamics-based algorithm, called UEOC, which means 'unfold and extract overlapping communities'. In UEOC, when identifying each natural community that overlaps, a Markov random walk method combined with a constraint strategy, which is based on the corresponding annealed network (degree conserving random network), is performed to unfold the community. Then, a cutoff criterion with the aid of a local community function, called conductance, which can be thought of as the ratio between the number of edges inside the community and those leaving it, is presented to extract this emerged community from the entire network. The UEOC algorithm depends on only one parameter whose value can be easily set, and it requires no prior knowledge of the hidden community structures. The proposed UEOC has been evaluated both on synthetic benchmarks and on some real-world networks, and has been compared with a set of competing algorithms. The experimental result has shown that UEOC is highly effective and efficient for discovering overlapping communities.

Zawirsky M, Bieniusa A, Balegas V, Duarte S, Moreno CB, Shapiro M, Preguiça N.  2013.  SwiftCloud: Fault-tolerant geo-replication integrated all the way to the client machine. :24. Abstract1310.3107v1.pdf

Client-side logic and storage are increasingly used in web and mobile applications to improve response time and availability. Current approaches tend to be ad-hoc and poorly integrated with the server-side logic. We present a principled approach to integrate client- and server-side storage. We support mergeable and strongly consistent transactions that target either client or server replicas and provide access to causally-consistent snapshots efficiently. In the presence of infrastructure faults, a client-assisted failover solution allows client execution to resume immediately and seamlessly access consistent snapshots without waiting. We implement this approach in SwiftCloud, the first transactional system to bring geo-replication all the way to the client machine. Example applications show that our programming model is useful across a range of application areas. Our experimental evaluation shows that SwiftCloud provides better fault tolerance and at the same time can improve both latency and throughput by up to an order of magnitude, compared to classical geo-replication techniques.

Almeida PS, Moreno CB.  2013.  Scalable eventually consistent counters over unreliable networks. :1-32. Abstract1307.3207v1_1.pdf

Counters are an important abstraction in distributed computing, and play a central role in large scale geo-replicated systems, counting events such as web page impressions or social network "likes". Classic distributed counters, strongly consistent, cannot be made both available and partition-tolerant, due to the CAP Theorem, being unsuitable to large scale scenarios. This paper defines Eventually Consistent Distributed Counters (ECDC) and presents an implementation of the concept, Handoff Counters, that is scalable and works over unreliable networks. By giving up the sequencer aspect of classic distributed counters, ECDC implementations can be made AP in the CAP design space, while retaining the essence of counting. Handoff Counters are the first CRDT (Conflict-free Replicated Data Type) based mechanism that overcomes the identity explosion problem in naive CRDTs, such as G-Counters (where state size is linear in the number of independent actors that ever incremented the counter), by managing identities towards avoiding global propagation and garbage collecting temporary entries. The approach used in Handoff Counters is not restricted to counters, being more generally applicable to other data types with associative and commutative operations.