PODC Archives

ACM PODC Participants List

PODC@LISTSERV.ACM.ORG

Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Subject:
From:
Marc Shapiro -- at work <[log in to unmask]>
Reply To:
Marc Shapiro -- at work <[log in to unmask]>
Date:
Wed, 25 Mar 2015 10:24:16 +0100
Content-Type:
text/plain
Parts/Attachments:
text/plain (52 lines)
Dear PODC list members,

A PhD grant for the topic described below may be available in a competition organized by Inria.  The deadline is 30 April.  Please forward to interested students.  Thank you.

						Marc Shapiro

-------------------------------------------------------------------------------
Marc Shapiro, INRIA & LIP6, BC 169                  mailto:[log in to unmask]
UPMC, 26-00/211, 4 place Jussieu                   http://lip6.fr/Marc.Shapiro/
75252 Paris Cedex 05, France                               tél: +33 1 4427 7093
-------------------------------------------------------------------------------

	JUST-RIGHT CONSISTENCY

Scalability is a top consideration in the design of a cloud database, replicated over different geographies. In previous work, our group explored the inherent trade-off between, on the one hand, consistency, and availability and performance on the other. 

A strongly-consistent system, for instance Google’s Spanner, facilitates developing correct applications. It also supports elasticity and has small metadata overhead. However, it requires synchronisation in the clients’ critical path; therefore, it penalises availability, responsiveness and scalability. 

In contrast, when updates are asynchronous, they do not slow down the application’s critical path; this ensures availability and responsiveness. However, it exposes the application to unfamiliar behaviours. We focus on causal consistency, which both is asynchronous and guarantees that clients do not observe updates in anomalous order. Examples include COPS, Eiger or GentleRain. Causal consistency generally requires substantial metadata; our recent SwiftCloud design is the first to scale to thousands of partial replicas with small metadata.

Designers of a geo-replicated database face a vexing choice between strong consistency, which is required to ensure certain application invariants but is slow and fragile, and asynchronous replication, which is responsive and scalable, but exposes the programmer to unfamiliar behaviours. To bypass this conundrum, we propose a new approach: Just-Right Consistency. Under JRC, the database supports asynchronous updates by default, but synchronisation is available when necessary; static and dynamic analysis tools help to identify sufficient synchronisation and optimise synchronisation placement. 

The proposed research includes the following components: 

	• Analyse application requirements. Identify and classify common classes of invariants; for each class, describe appropriate synchronisation protocol. 
 
	• Design a tool or language for expressing invariants at a high level, and for helping application programmers to identify all important invariants of their application. 
 
	• Design and implement a static analysis tool for detecting concurrent transactions that are unsafe with respect to the above invariants, and for thus identifying points where the developer should insert synchronisation to ensure safety. 
	• Noting that safety is not enough (different safe synchronisation patterns will exist, with differing performance depending on the workload; some may even be prone to deadlock), design and implement a dynamic analysis tool to analyse synchronisation performance, and to optimise by comparing alternative synchronisation placements. 
 
	• To support the above tools, design and implement a geo-replicated cloud database whose transactions are asynchronous by default, but optionally may specify synchronisation for its reads, its writes, or both. The challenge is ensuring that synchronous operations do not slow down the asynchronous ones, and designing compact and uniform metadata for both types of operations. Apply the above analysis tools to applications running above this database. 


We do not expect to discover a one-size-fits-all silver bullet, but are prepared to explore the trade-offs, in order to provide guidance to system and application designers and administrators. 
In addition to consistency, the system should scale out and remain cost- efficient under varying conditions. Therefore, in addition to consistency itelf, this work should also pay attention to the cost-vs.-expressivity trade-offs of the metadata design, reducing storage and bandwith requirements, thanks to partial replication, and variability of load and of availability of resources, by making partial replication elastic.

 
Requirements:
	• Masters’ in Computer Science / Informatics or related field 
	• Excellent academic record. 
	• Highly motivated by research in distributed systems and/or programming languages and verification. 
	• Excellent implementation and experimentation skills.

 
Please provide a CV, the list of your Masters or PhD courses and your marks, an essay relevant to the topic (1 to 4 pages), and at least two references (whom we will contact ourselves for a recommendation). 

Advisors: Marc Shapiro, Pierre-Evariste Dagand.

To apply, use this link: http://www.inria.fr/en/institute/recruitment/offers/phd/campaign-2015/(view)/details.html?nPostingTargetID=15253
############################

To unsubscribe from the PODC list:
write to: mailto:[log in to unmask]
or click the following link:
http://listserv.acm.org/SCRIPTS/WA-ACMLPX.CGI?SUBED1=PODC&A=1

ATOM RSS1 RSS2