Please use this identifier to cite or link to this item: https://doi.org/10.1109/ICDCS.2011.71
Title: Confidential gossip
Authors: Georgiou, C.
Gilbert, S. 
Kowalski, D.R.
Keywords: Collusion
Confidentiality
Dynamic rumor injection
Fault-tolerance
Message complexity
Randomized gossip
Issue Date: 2011
Source: Georgiou, C., Gilbert, S., Kowalski, D.R. (2011). Confidential gossip. Proceedings - International Conference on Distributed Computing Systems : 603-612. ScholarBank@NUS Repository. https://doi.org/10.1109/ICDCS.2011.71
Abstract: Epidemic gossip has proven a reliable and efficient technique for sharing information in a distributed network. Much of the reliability and efficiency derives from processes collaborating, sharing the work of distributing information. As a result of this collaboration, processes may receive information that was not originally intended for them. For example, a process may act as an intermediary, aggregating and forwarding messages from some set of sources to some set of destinations. But what if rumors are confidential? In that case, only processes that were originally intended to receive a rumor should be allowed to learn the rumor. This blatantly contradicts the basic premise of epidemic gossip, which assumes that processes can collaborate. In fact, if only processes in a rumor's "destination set" participate in gossiping that rumor, we show that high message complexity is unavoidable. In this paper, we propose a scheme in which each rumor is broken into multiple fragments using a very simple coding scheme: any given fragment provides no information about the rumor, while together, the fragments can be reassembled into the original rumor. The processes collaborate in disseminating the rumor fragments in such a way that no process outside of a rumor's destination set ever receives all the fragments of a rumor, while every process in the destination set eventually learns all the fragments. Notably, our solution operates in an environment where rumors are dynamically and continuously injected into the system and processes are subject to crashes and restarts. In addition, the scheme presented can tolerate a moderate amount of collusion among curious processes without too large an increase in cost. © 2011 IEEE.
Source Title: Proceedings - International Conference on Distributed Computing Systems
URI: http://scholarbank.nus.edu.sg/handle/10635/40521
ISBN: 9780769543642
DOI: 10.1109/ICDCS.2011.71
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

53
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.