My Math Forum How can set of computers agree if set size is even or odd?

 Applied Math Applied Math Forum

 July 17th, 2013, 11:29 PM #1 Senior Member   Joined: Jan 2013 Posts: 209 Thanks: 3 How can set of computers agree if set size is even or odd? How can a set of computers agree with eachother if the set size is even or odd? I'm not sure how to prove it, but I think that to solve this reliably is an NP-Complete problem and practically is useful for new kinds of routing protocols and a foundation for decentralized global democracy more similar to how Wikipedia allows billions of people to agree on many things instead of top down ways of organizing things. How can a set of computers agree with eachother if the set size is even or odd? How do you scale this up?
 July 18th, 2013, 04:13 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: How can set of computers agree if set size is even or od How is the set defined?
 July 18th, 2013, 08:05 AM #3 Senior Member   Joined: Jan 2013 Posts: 209 Thanks: 3 Re: How can set of computers agree if set size is even or od Since the definition of every set includes its size which is even or odd, the question is how such a set of computers would agree on any such set in the first place. Its similar Max Clique. I can't just define the clique as a set then you tell me if its even or odd. Its a subset of all computers, some of which are directly connected and others have to communicate on longer paths to eachother. I'll make it even easier... Tell me any such set that has ever, in the real world, been counted (as even or odd, to make it easier than counting), and how was it proven the count is accurate? Whats the biggest set of computers that has ever been done for? I think this is more than a mathematical abstraction. I think they really don't know how to count large groups of computers.
July 18th, 2013, 08:09 AM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: How can set of computers agree if set size is even or od

Quote:
 Originally Posted by BenFRayfield the question is how such a set of computers would agree on any such set in the first place.
So you're looking for a Byzantine agreement scheme, then.

 July 18th, 2013, 08:23 AM #5 Senior Member   Joined: Jan 2013 Posts: 209 Thanks: 3 Re: How can set of computers agree if set size is even or od Hardware failures can be abstracted out of the question by representing a set of computers as a network within one Turing Complete cellular automata, like Conway's Game Of Life or Rule 110.
 July 18th, 2013, 09:56 AM #6 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: How can set of computers agree if set size is even or od You need a bunch of computers to agree on something. You can use the Byzantine generals scheme to get them to do that, even if there are no hardware failures.
July 18th, 2013, 04:34 PM   #7
Senior Member

Joined: Aug 2012

Posts: 2,385
Thanks: 745

Re: How can set of computers agree if set size is even or od

Quote:
 Originally Posted by BenFRayfield I'll make it even easier... Tell me any such set that has ever, in the real world, been counted (as even or odd, to make it easier than counting), and how was it proven the count is accurate? Whats the biggest set of computers that has ever been done for? I think this is more than a mathematical abstraction. I think they really don't know how to count large groups of computers.
Not following at all. If the set has a size, and if that size can be represented in binary, the computer need only look at the low-order bit to determine if the set is even or odd. And your bank counts the set of dollars in your checking account, right down to the penny, every month. And they're never wrong. Just try convincing them they've made a mistake.

As CRG noted, there are a lot of algorithms related to fault-tolerant computing in which a network of computers can determine which of them are malfunctioning. There's computer science literature on multiprocessor voting schemes going back to the 1970's.

 Tags agree, computers, odd, set, size

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post BenFRayfield Applied Math 4 December 21st, 2013 10:58 PM yogazen2013 Algebra 2 October 5th, 2013 03:26 AM dervast Real Analysis 8 January 17th, 2011 09:40 AM johnny Computer Science 5 August 7th, 2007 05:55 AM johnny Computer Science 3 July 31st, 2007 06:35 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top