Questions about the challenges of solving problems with multiple cooperating but separate agents.

learn more… | top users | synonyms (1)

-2
votes
1answer
37 views

Both shared-memory and distributed-memory

As you see in the following picture its a shared-memory architecture which has been modeled in a form of complete graph. Why we can consider the following architecture (which is a complete graph) both ...
3
votes
1answer
83 views

Lamport's Bakery algorithm

I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 ...
1
vote
0answers
20 views

Resources to learn about distributed data structures? (DHT, Merkle Tree, etc.)

I'm having a hard time finding comprehensive literature on distributed / p2p data structures... for example, I have found the book "Handbook of Peer-to-Peer Networking", which seems to be what I want (...
0
votes
1answer
54 views

Difference between centralized computing and distributed computing using Client-Server

I already understand that Distributed Computing is the breakup of having multiple clients rely on a single source, and having each client utilize other clients for information. But my confusion comes ...
0
votes
0answers
23 views

What is the consensus algorithm that requires an odd number of nodes?

Last week I stood up and gave a talk on the Raft Consensus Algorithm. The first question I got was: Doesn't it need an odd number of nodes? I answered "During leader election, the first node ...
1
vote
0answers
21 views

Using consensus for atomic commits

I read that consensus algorithms allow you to ensure the atomic commit. That is, in order to save a large amount of data on the disk, as if it is a single object, the article advises a consensus ...
0
votes
1answer
94 views

What is the difference between centralised, decentralised, distributed, fully-distributed?

What is the difference between centralised, decentralised, distributed, fully-distributed, partially-centralised, partially-decentralised system? Which type or topology is the system attached in the ...
3
votes
1answer
27 views

Can we say that Zookeeper updates are ACD (ACID without the I)?

Zookeeper is based on the Zab (which is slightly different to Paxos) system. We can do Atomic locks on top of a Zookeeper cluster. Zookeeper provides eventual consistency. Zookeeper provides ...
0
votes
0answers
28 views

How do you define convergence in the Ant Colony Optimization?

What does convergence mean for an Ant Colony Optimization (ACO)? Is there a settled definition of it? Consider for example, Exhibit A: There are two paths of equal length along which the ants can ...
3
votes
0answers
24 views

How to realize a distributed queue with unreliable participants?

I want to build an application that relies on a distributed queue with participants in a decentralized (peer-to-peer) network. The participants cannot be relied on to correctly follow a protocol. I ...
1
vote
1answer
51 views

Vector clocks: Why is it necessary to increment my clock on receiving a message?

Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes. ...
3
votes
0answers
32 views

Why is the commit phase in PBFT necessary?

I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that PREPARE phase ensures fault-...
1
vote
1answer
25 views

How can a distributed system cooperate to determine rules of its environment?

I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm ...
1
vote
2answers
36 views

Distributed systems according to Lamport?

I need some clarification over the following quotation of Leslie Lamport: A distributed system can be described as a particular sequential state machine that is implemented with a network of ...
0
votes
3answers
37 views

Computing the intersection of N sets over an M-element universe

Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$. 1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$? 2.) I am also looking for a good parallel and a good ...
0
votes
1answer
42 views

Difference between 2f+1, 2f and 3f+1

I am currently reading the Practical Byzantine Fault Tolerance paper. I am unable to completely understand the difference between 2f and ...
1
vote
1answer
42 views

Distributed parallel computing algorithms for content dependent data

I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel ...
3
votes
1answer
65 views

Best data structure for storing an ordered list, where each item is located on a separate server?

I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible. ...
0
votes
0answers
22 views

Who said: you need to send few messages over the network and they need to be as small as possible so that a distributed application scales up?

I wonder if there is a well known law or scientific article to cite for this. I am writing a manuscript and I am looking for the right reference. Is there something like the Amdahl's law saying that? ...
3
votes
6answers
335 views

Parallel vs Distributed Algorithms

Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core ...
1
vote
1answer
42 views

Synchronisation and ordering in distributed systems

I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages ...
2
votes
0answers
40 views

What are the theoretical and practical contributions of Multiagent Systems to science?

Speaking about multiagent systems (MAS) is about as fuzzy as talking about artificial intelligence systems (AI). They are in essence the distributed counterpart of AI. While there are no so-called "...
2
votes
1answer
28 views

Call-by-reference semantics for RPC

Does call-by-reference semantics for remote procedure call (RPC) have a real use case? Why does call-by-reference RPC exist? Is it useful for anything? Is there a scenario where call-by-value can't ...
2
votes
1answer
40 views

Term for shifting work to idle machines

I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks ...
0
votes
0answers
33 views

What differs in the message passing model?

Doing a very basic course in distributed computing. I just went through Dijkstra's self-stabilizing mutual exclusion in the shared memory model. We where encouraged to think about what would change in ...
3
votes
1answer
105 views

Is there a difference between total-ordering consistency and linearizability?

By total-ordering I mean the following definition[0]: Total Event Ordering: Controller replicas should process events in the same order and subsequently all controller application instances ...
1
vote
0answers
59 views

Processes running in Distributed Systems (Advanced Operating System)

I had a test today, there was a question that was a bit confusing. Anyway I am asking the question, from memory, and explaining what I answered. It would be great if someone could explain if I did ...
3
votes
1answer
63 views

Algorithm for executing a command against a million hosts

Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the ...
2
votes
0answers
42 views

Floating output/making a non-self stabilizing algorithm self stabilizing

So we're using this book by Shlomi Dolev on self-stabilization in class. Not being from a theretical CS background, I think the book is rather terse. Most of it is fine but there's this section on "...
1
vote
1answer
41 views

Complexity of calculating average across distributed network?

What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over ...
4
votes
0answers
79 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
1
vote
0answers
67 views

Working of the GHS algorithm

Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found ...
6
votes
0answers
63 views

What is 2g-precedence?

I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much ...
1
vote
0answers
28 views

parallel computation and GPGPU question [closed]

is there a mean of creating a cluster of machines, that can be seen as an entire system, using perhaps mac OS X or mac os x server, and use parallelism and GPGPU optimisation to compute all the tasks ...
1
vote
0answers
105 views

What advantage does Tangaroa offer over PBFT?

Tangaroa is a relatively new project adding Byzantine fault-tolerance to the Raft consensus protocol using techniques that were already used in the PBFT algorithm. What are the advantages, when should ...
1
vote
1answer
70 views

What does atomicity mean in distributed systems?

In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem? Does atomicity have a different meaning in this context?
3
votes
1answer
47 views

Understanding the fundamentals of building an in-Memory Distributed Graph

I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple ...
6
votes
1answer
150 views

Paxos consistency

I'm looking at the paxos family of protocols for solving consensus in a network of unreliable processors. I'm working through scenarios where processors fail, and I know I'm wrong, but I don't know ...
0
votes
1answer
29 views

How can I take advantage of the capabilities of a cluster [closed]

I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that ...
2
votes
0answers
28 views

What are the prerequisites for working on multi agent systems? [closed]

I am starting to study about Multi Agent Systems and I wanted to know which sciences are most used in these systems, I am aware of game theory and Markov statistical relations (Markov Decision Process ...
2
votes
0answers
56 views

Client-Server Architecture /State Model and Process Mode [closed]

how i can define what are Client-Server Architecture for a website that suggestion courses for students after students insert the history of courses. The language will be PHP,mysql and HTML. In this ...
4
votes
1answer
65 views

solving large nonlinear systems in parallel

I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
1
vote
1answer
32 views

In a distributed system is it possible for both parties to simultaneously agree a message exchange was made?

Given that the two generals problema is unsolvable, which means that both parties involved cannot agree that both know something, i ask something simpler. Is it possible for both parties to agree ...
4
votes
1answer
63 views

Symmetric protocols for consensus

All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any ...
5
votes
1answer
314 views

Consensus problem of distributed systems

I just started reading about distributed systems for the first time ever. There is a fairly slick proof of the impossibility of consensus in an asynchronous model using some combinatorial topology. On ...
3
votes
1answer
169 views

What happens when two processes hold an election using bully algorithm simultaneously

A coordinator is used to sychronise the usage of resources in a distributed system. The Bully Algorithm is a method to elect a new coordinator in a distributed system when the current coordinator ...
3
votes
1answer
128 views

Counting the nodes in a network in a distributed way

There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters). One of the nodes, say $s$, wants to know $n$. How can it do ...
2
votes
1answer
73 views

Paxos: Instances, Rounds, Phases

In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a $prepare$ phase, and an $accept$ phase. An instance of Paxos can have multiple rounds. Can a round have multiple ...
3
votes
1answer
41 views

Paxos: Responding to Reordered Prepare Requests

In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a prepare request with: A promise never to again accept a proposal numbered less than n, and the proposal with the ...
3
votes
1answer
78 views

What is the size of a queue associated with a resource when the resource becomes a bottleneck?

In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the ...